In a recent paper with Daniel J. Bernstein, we introduce a new security notion for cryptographic hash functions called decisional second-preimage resistance (DSPR) that asks to decide if a given domain element has a colliding value within the domain of the hash function. It turns out that DSPR and conventional second-preimage resistance (SPR) together imply one-wayness (PRE). This fills a gap in the theory of hash functions showing when SPR implies PRE. Moreover, it has applications in achieving tight proofs for hash-based signatures (which was the reason for us to start looking into this). The paper will appear at ASIACRYPT 2019.

Our work on the indistinguishability of the sponge construction even in the presence of quantum adversaries appears at this years CRYPTO. The paper demonstrates that there are ways to secretly key a sponge such that it becomes a secure PRF and thereby a secure MAC.

Our paper on the quantum security of the sponge construction will be presented at PQCrypto 2018. We prove collision resistance and collapsing for the sponge construction under the assumption that the internal block function is a random one-way permutation or a random function. Sadly, this does not cover SHA3 as the block function in SHA3 is an invertible permutation. However, we are already working on new results to cover this case.

Hunting season is open (for submissions to the NIST post-quantum project). After our PhD student Lorenz Panny already broke “Guess Again” within three hours, the next hit took a moment. Actually, it didn’t. We (Lorenz, Tanja Lange, Daniel J. Bernstein and me) already found three vulnerabilities in RaCoSS within one hour. Only problem: One of them was a low complexity second-preimage attack against the internal hash function. Low complexity means about 2^31 hashes and the input consists not only of the message but also a 2400 bit vector and the serialization of a 2400 x 340 binary matrix. This took the night to finish and we wanted to demonstrate the attack before publishing. Also, everyone was on their way to spent the holidays somewhere, so coordination was a mess (Deutsche Bahn and Wifi…. grrr). But now the attack is online.

Briefly, we first found an implementation flaw that made the first KAT signature a valid signature for about 65% of the messages we tried. The problem was essentially using a byte array to represent a bit string, using one byte per bit but using the length of a classical byte representation of the bit string (8 bits per byte).

This happened when we were trying to exploit the low-complexity second-preimage attack. The latter exists as RaCoSS maps messages — together with some other stuff — to 2400 bit strings of weight 3. Problem: The image of this function only has ~2^31 elements. Kind of small for the cryptographic setting.

At this point we started to look closer and Tanja observed that one can actually comparatively easy compute valid signatures just given the public key. Sadly it seems really hard to fix this as a straight forward fix would work towards making the second-preimage attack even easier. Hence, it seems as if a fix would have to solve this connection between the two attacks.

It took a moment (not to say virtually forever) but we launched the SPHINCS+ website at https://sphincs.org. You can now find the full submission package as well as code and specification separately. In addition, we started to collect the most relevant papers to for our design and plan to collect all results related to SPHINCS+ on that page. So, if you do an attack against or an implementation of SPHINCS+ — please let us know.

The year seems to end well, two of my papers got accepted for PKC 2018! The first paper presents rounded Gaussians as an alternative to discrete Gaussians in rejection sampling based lattice-based signature schemes (like BLISS). The advantage is that sampling from a rounded Gaussian can be easily done in constant time. The second paper is about SOFIA, a signature scheme with a security reduction from the MQ-problem in the quantum-accessible random oracle model. So far there was essentially only one signature scheme with a security reduction from the MQ-problem and this reduction was in the classical ROM.

After quite some time without writing any news (too busy) I want to take a moment to announce our submission to the NIST “not-a-competition”. While I am involved in three submissions, I took lead for the hash-based signature submission which I will talk about here.

Over the two years since we published SPHINCS, we collected a lot of nice ideas to reduce the signature size and to speed up the scheme.  So, for the NIST submission we reviewed all of them and built SPHINCS+ in the process. SPHINCS+ is SPHINCS in terms of high level scheme design but we tweaked some of the internals — especially the few-times signature scheme. Let me summarize the changes we made:

• Multi-target attack protection: We added the mitigation techniques which we
  proposed in our PKC 2016 paper (Mitigating Multi-Target Attacks in Hash-Based Signatures). This was already the plan when publishing that paper. We just discussed it in terms of XMSS there as that was the smaller example. The basic concept is to use a different hash function for each call. Each hash function call is
  keyed with a different key and applies different bitmasks. Keys and bitmasks are
  pseudorandomly generated from an address specifying the context of the call, and
  a public seed. To get an abstraction we now introduced the notion of tweakable hash functions which in addition to the input value takes a public seed and an address.
• Tree-less WOTS+ public key compression: The last nodes of the WOTS+ chains
  are not compressed using an L-tree but using a single tweakable hash function
  call. This call again receives an address and a public seed to key this call and to
  generate a bitmask as long as the input. This was not possible before without blowing up the public key. Now, as we generate bitmasks pseudorandomly, this has no influence on public key size.
• FORS: We replace the few-time signature scheme (FTS) HORST by FORS — Forest Of Random Subsets. A FORS key pair does not consist of a single
  monolithic tree but of k trees of height log t. The leaves of these trees are the hashes of t secret key elements making a total secret key of kt elements.
  The public key is the tweakable hash of the concatenation of all the root
  nodes as for the WOTS+ public key.  The big difference to HORST is that we now got a dedicated set of secret key values per index derived from the message. While it first might look as if the key size goes up and speed goes down, this only applies when using the same parameters as for HORST. The advantage is that we can now use much smaller parameters and thereby in the end gain in signature size and speed.
• Verifiable index selection: In SPHINCS the HORST key pair used to sign the message was selected generating an index in a pseudorandom manner. As a secret seed value was involved, a verifier was unable to check if that index was actually generated that way.  This had the disadvantage that an adversary targeting HORST was able to mount a multi-target attack, using one hash computation to target all HORST instances at once.
  This is not possible anymore. We now compute the index together with the message
  digest as
  ( md || idx ) = H ( R, PK, M )
  where PK is the SPHINCS+ public key and R is a (pseudo-)randomly generated value which becomes part of the signature. Hence, every message that an adversary tries becomes now directly linked to a FORS instance and is unusable for any other instance. In addition, this allows us to omit the index in the SPHINCS+ signature.

We were discussing a lot of other ideas including a trade-off between secret key and signature size using a higher top tree and storing intermediate layers in that tree as well as short-term state (STS) versions. The former we discarded as it massively slows down key generation and complicates implementation at only a minimal size reduction (about one WOTS+ signature). The latter seems incompatible to the verifiable index selection (and would not have fit the NIST API anyway).

These changes allowed us to define parameter sets with signature sizes of as little as 8kb! Admittedly, at NIST security level 1 and a few seconds for signing. However, the implementation is unoptimized and for many use-cases like certificate or code signing about one second actually seems fine. Even at the highest security level (NIST 5) we get down to 30kb at about the same speed. This is compared to SPHINCS with 41kb. Moreover, NIST asked to assume a key pair is used for 2^{64] signatures. For the old SPHINCS we assumed 2^{50} signatures. This number of signatures has a huge impact on SPHINCS(+) signature size. Hence, if we are willing to make less conservative assumptions on the number of signatures (I personally find 2^{50} already pretty conservative) we could get even smaller signatures. Of course, the parameters we proposed are just what we consider well balanced. At the same level of security there exists a magnitude of possible parameters (one can still get smaller at the cost of speed). We deliver a script that allows to enumerate those parameters so you can optimize for any metric of your choosing.

Finally, we present three different incarnations of SPHINCS+:

• SPHINCS+-SHA3 (using SHAKE256)
• SPHINCS+-SHA2 (using SHA2)
• SPHINCS+-Haraka (using the Haraka short-input hash function)

We are currently setting up a website for the submission and will publish all material also there. I will add the link here as soon as we are done.

We got two papers (on hash-based signatures!) into this years PKC! One is on an implementation of SPHINCS on an ARM Cortex M3. While the result is surely no practical implementation (the signatures are simply too big) it shows that it is in general doable. Besides, we give a comparison with XMSS on the same platform. The result shows that if you are able to allow for a state, you can get away with a pretty efficient implementation.

The other paper started as a security analysis of our recent Internet-Draft. On the way, we figured we had to analyse what we call multi-target security properties for hash functions under generic quantum attacks. In this context we present new matching lower and upper bounds on the quantum query complexity against such properties (incl. traditional one-wayness, second-preimage resistance and extended target-collision resistance).

I recently helped Moritz Horsch to develope a nice password tool called PALPAS. It is a password-store-like tool but the nice thing about this tool is that it synchronizes passwords between several devices without storing the passwords in any form on a central server. The tool only stores  some information that alone is completely independent of the passwords. Think this is not possible? See the project page or the paper. The tool is open source and the code will be available on the project page soon.

We got an Internet-Draft on XMSS out! The first version was published in Spring and presented at the IETF 92 meeting in Dallas. We also had an accompanying report at the NIST workshop on post-quantum cryptography. Our draft was now accepted as a CFRG working group draft. Currently we are working on an update that is planned to be published before the IETF meeting in Prague this July.