Minutes for CFRG at interim-2016-cfrg-1

Meeting Minutes Crypto Forum (cfrg) RG
Title Minutes for CFRG at interim-2016-cfrg-1
State Active
Other versions plain text
Last updated 2016-05-16

Meeting Minutes

Draft minutes from CFRG Interim Meeting, May 12th 2016, Eurocrypt 2016, Vienna

Where the minutes refer to slides X-Y.pdf, they can be found at
Presented by Kenny Paterson (Royal Holloway, co-chair of CFRG)
Slides: slides-interim-2016-cfrg-1-2.pdf

     AES-GCM-SIV                             (30min + 10min discussion)
Presented by Shay Gueron (Intel, University of Haifa)
Slides: slides-interim-2016-cfrg-1-7.pdf
Draft: https://tools.ietf.org/html/draft-irtf-cfrg-gcmsiv-01

Atul Luykx (KU Leuven):
I tried to understand your security claim. You say the bound is better than
using random-IV GCM [in the nonce-respecting case]? Shay: In the case of long
messages (ie close to 2^32 blocks) our security bound is equivalent to AES-GCM.
However, for shorter messages, we can do better because we do not initialise
the counter bytes to zero. For example, if messages are less than 2^20 blocks,
the remaining 12 bits increase the length of the random IV, giving another 12
bits of security. Atul: Is this for Integrity or Privacy? Shay: Integrity,
although counter modes should just do this anyway.

Gaetan Leurent (INRIA): As the CAESAR competition is going on, why is this
being proposed along side? Why not use the CAESAR recommendation? Shay: Why
didn't we submit to CAESAR? We were a year too late! We are not trying to
compete with CAESAR. GCM is now ubiquitous, and here we show how to quickly
achieve stronger security using what we already have.

Philipp Jovanovic (EPFL): TLS1.3 ensures you never repeat a nonce. Good
implementations will always have a good nonce. So why do we need this? Shay:
Sure, but you can never assume that all implementations will be good. But yes,
we agree: if you're sure that nonces will never repeat, stick to GCM.

Kenny: This is MAC-then-Encrypt (MtE). How do you deal with the premature
release of plaintext during decryption? Again, it shouldn't happen, but there
will be bad implementations out there. Shay: If implemented correctly, then
there shouldn't be an issue. But if not, well then yes: our hope is that this
will never happen. Kenny: I think this needs to be made clear in the draft.
Shay: Yes, we will add a disclaimer or something.

Bertram Poettering (HGI, Ruhr University Bochum): You do key expansion for each
query, could you comment on that.  Perhaps you could you use a Tweakable Block
Cipher rather than a blockcipher to avoid this? Shay: Starting with the second
point, there are many ways to do this, I can't comment on which is the best
one.  As far as the cost of key expansion, its not too bad: about 15 cycles. In
our code we interleave this with the first blockcipher call to reduce the
overall cost. So, its not too much even for short messages, and irrelevant for
long messages.

Jean Paul Degabriele (Royal Holloway): On Smart Cards, the coprocessor can
sometimes do AES at similar costs to a simple xor. Can you comment on how AES
compares to Polynomial multiplication on these? Shay: On modern processors
there exists a polynomial multiplication instruction. In fact, for Intel
processors I can give you a rough comparison. [Returning to table of costs for
AES-GCM-SIV encryption and decryption, ] we can see it costs roughly 0.3 cycles
per byte for the multiplication. JP: So, roughly half the cost of an AES call?
Shay: More accurately, the polynomial multiplication has roughly twice the
throughput of the AES calls: you'd never do just one of these at a time.

Kenny: You only support 96-bit nonces? This is seems like a difference from the
AES-GCM specification. Shay: The inclusion of non-96-bit nonces has led to
problems (such as a correction in the NIST standard, and a bug in the security
proofs), and so 96-bit is already recommended.  What we do provides equivalent
security to GCM with a random 96 bit nonce. Kenny: Your hash key is
independent, rather than derived. How will this affect the API? Shay: AES-GCM
begins by deriving its hash key with a single AES call, at the cost of reducing
its range of counter values to a rather ugly range. We felt the API cost was
worth this. As for performance, this reduced call is a big help for short
messages, but irrelevant for long ones. Kenny: So what would be your API? Would
you take in an extra key? Shay: We take pointers to the Associated Data and
message, their lengths, a nonce and two keys. Kenny: So its not the same as for
GCM? Shay: Same but with another key, as does ChaCha+Poly1305 Kenny: Sure, but
this isn't a drop-in replacement then. Shay: Ok, so we could take in a single
longer key and split it inside the function. Kenny: Yes. These sorts of details
matter when defining a standard.

Bart Preneel (KU Leuven): What happens if I put the same key for both the hash
and encryption? Again, I'm thinking of an implementation error. Shay: Oh wow,
wonderful question. In the real world it would probably be fine, but one would
have to carefully check.

Bertram: So, what is the target security? You mentioned using AES-256, but only
a 128 polynomial hash. Shay: The Authentication key would be 128 bits (because
the authentication uses an information theoretic security proof), and
confidentiality key is 128 or 256 bits. Bertram: This limits the maximum
message length then? Shay: Yes, you are always limited by the number of roots
of the polynomial. Bertram: A longer hash key H would help with this. Shay:
Yes, but then a different field would be required.

    Memory-Hard Functions                          (30min + 10min discussion)
Presented by: Joel Alwen (IST Austria)
Slides: slides-interim-2016-cfrg-1-1.pdf
Draft: --
Kenny: Thanks for the talk. Do you think the CFRG should pause the
standardisation of Argon2i? Joel: Yes. I hesitate to say it, but yes. The
theory has really grown, and in the near future I think we can do much much
better, Kenny: Would you rerun the password-hashing competition? Joel: That
would be good. Our improved theory tells us there's a basic design error in
almost all the candidates, that we only really learnt about during or after the
competition. We should also have more practitioners involved.

Bart: There exists work from Wiener on the Total Cost of cryptanalytic attacks.
Have you considered the memory access costs, because often these are the
dominating factor? [Note to add, the paper in question is
DOI:10.1007/s00145-003-0213-5] Joel: For memory-bound functions (eg cache
misses), as I understand this is more to do with L1,L2 cache behaviour. I'm not
sure how relevant this would be for ASICs. In the dynamic memory access cases,
each look-up address is random, so you can't load it into a cache anyway, so we
will keep getting cache misses. Bart: Yes, with random queries, a cache would
worsen things.

Bart: At the end, you gave an example with a certain number of cores. How was
this chosen? Joel: We took our generic attack, and then targeted it for the
particular, realistic, parameter set.

    XMSS                                            (10min + 10min discussion)
Presented by: Andreas Hulsing (TU Eindhoven)
Slides: slides-interim-2016-cfrg-1-3.pdf
Draft: https://www.ietf.org/id/draft-irtf-cfrg-xmss-hash-based-signatures-03.txt
Phillipp: You said you've removed ChaCha from the construction because it
wasn't adequate for your masks. Have you considered replacing it with something
like Blake2? Andreas: No. We decided to instead remove that design element
completely, to keep the code size down. We were packaging an entire stream
cipher, and overall couldn't justify it.

Bertram: It seems there is still open and active research on hash-based
signatures at the moment. When would be the right time to standardise? Andreas:
Our last change was precisely towards standardising. XMSS itself was designed
and secure, but there were small costs in our security proof that meant the
appropriate versions didn't quite achieve the classic security targets (for
example our 128-bit candidate is a few bits short). So, we these modifications
from 2011 to the 2016 version were slightly increase the security bounds and
provide the target levels requested.

Bertram: Right, but I was thinking more in terms of Quantum Resistance?
Andreas: By the time we finish standardising this, it will have been about two
years (so about one year more I think). Then, to deploy we're looking at 5 to
10 years after that. It's not impossible we'll have a quantum computer by then,
so we need to start now. Because we're hash not lattice based our security
estimates are pretty sound, they're not changing around all over the place. As
for Encryption, we need solutions for that much sooner!

    Any Other Business                                                  
    (<10min discussion)
Kenny: Has this been useful? Would you like more of these in future, perhaps
co-located with Crypto or Eurocrypt again next year? Perhaps a quick show of

Kenny: And is anyone here against doing this again?

Kenny: I guess you wouldn't be here if you thought that.
Kenny: Right, thank you all for coming, and have a safe journey.