[HN Gopher] Galois/Counter Mode and random nonces
___________________________________________________________________
Galois/Counter Mode and random nonces
Author : thunderbong
Score : 59 points
Date : 2024-05-28 05:13 UTC (1 days ago)
(HTM) web link (neilmadden.blog)
(TXT) w3m dump (neilmadden.blog)
| jbosh wrote:
| XSalsa and XChaCha do something extremely similar. In order to
| extend the nonce space by 128 bits you basically run a round of
| ChaCha against 128 bits of your nonce. Those 128 bits represent
| 96 bits of nonce and 32 bits of counter. Because you know you'll
| never encode more than 1 full block of data, the counter won't
| overlap. 256 bits of internal state become the key for the next
| round of ChaCha plus the remaining 64 bits of nonce and you get
| to use the full counter space because nonce just became the key.
|
| The paper is also extremely approachable.
|
| https://cr.yp.to/snuffle/xsalsa-20110204.pdf
|
| I wonder if processes like this extend cryptographically in most
| symmetric ciphers. To add more nonce, encrypt your nonce, output
| becomes key for next round, add more nonce, repeat. Like all
| things crypto though, your search space could absolutely collapse
| if the cipher doesn't have the right properties.
| motohagiography wrote:
| the general problem seems to be when a protocol uses the counter
| as a diversification component, it becomes another secret value
| to manage. I can't think of an example where it is and isn't, but
| only using an authenticated counter (via something like hotp or a
| ratchet) is a subtle design challenge.
| JoachimSchipper wrote:
| The GCM (or XSalsa, or...) nonce is not secret - in almost all
| protocols the nonce goes over the wire in plaintext! - but
| _must_ be a number-used-once. Those are quite distinct
| requirements.
| lazide wrote:
| this is also notably true for pretty much all uses of
| IV/nonces/salts. They are intended to provide randomization
| to an otherwise deterministic process (similar to specific
| types of RSA/DSA padding) to avoid being able to brute
| force/easily determine the contents from known examples. For
| ex: known plaintext attacks being one common example.
|
| It's the same reason salts are used in passwords - there will
| be people using the equivalent of 'password', and without a
| salt it would be trivial to find them with just a lookup
| table (often in nearly O(1) time). With a salt it at least
| requires per-entry hashing of possible values per user, with
| no re-usability between users. So O(n^p) time (worst case)
| where n == number of users, p == number of possible values to
| test. A pretty huge difference.
|
| Without the person on the other end having the value of the
| IV/nonce/salt, you might as well just stuff random bytes into
| the cyphertext field instead of the actual cyphertext, as if
| the algorithms are designed correctly they would be
| indistinguishable anyway.
| kurikuri wrote:
| The counter starts from an initialization value (IV), which
| does not need to be secret. What should be ensured (to prevent
| forgery attacks) is that each possible (key, initialization
| value) pair is never used twice.
|
| There are two standardized ways (from NIST's SP 800-38D) of
| ensuring unique (key,IV) pairs:
|
| 1. Use either a random number generator to make a nonce for the
| entire IV, or 2. Construct an IV by concatenating two fields,
| one field for the most significant bits set it to zero and
| increment it every time the key is used, the other is simply a
| fixed at zero.
|
| With the second option, some new limitations exist to maintain
| the constructed IV's uniqueness. The first being how many
| blocks of data you can encrypt in an operation
| (2^(size(fixedfield)) because you don't want to overflow into
| your key-reuse field. The second is being the number of times
| you can reuse the key is now limited to 2^size(keyreusefield).
| motohagiography wrote:
| reuse in implementations is common, and most protocols need
| to handle an asynchronous "offline" mode which means a
| sliding window of valid counters, and a thread to pull. the
| difference between a single use key and a limited use key is
| significant and has been known to get fudged somewhere
| between approved spec and implementation.
|
| Sure don't reuse the IV and make sure it can't be easily
| derived or guessed, but if I'm looking for problems in an
| implementation, my point was that counter usage is one of the
| low-entropy threads to pull.
| dontdoxxme wrote:
| At the end it mentions a nonce based approach probably being the
| more sensible way. Shay Gueron presented at RWC 2024 about a
| nonce based approach (DNDK-GCM):
| https://www.youtube.com/watch?v=GsFO4ZQlYS8&list=PLeeS-3Ml-r...
| -- they mention Meta are using this as their default in their
| encryption library.
|
| There is also an internet draft on it:
| https://datatracker.ietf.org/doc/draft-gueron-cfrg-dndkgcm/
| throw0101d wrote:
| See also perhaps:
|
| > _AES-GCM-SIV is a mode of operation for the Advanced Encryption
| Standard which provides similar performance to Galois /Counter
| Mode as well as misuse resistance in the event of the reuse of a
| cryptographic nonce. The construction is defined in RFC 8452.[1]_
|
| * https://en.wikipedia.org/wiki/AES-GCM-SIV
| redfast00 wrote:
| In my opinion, the author understates how good AES-GCM-SIV is:
|
| > The solution they designed is described in that linked paper:
| AES-GCM-SIV, which is able to tolerate some number of nonce
| collisions, but under a weaker notion of security that is only
| really applicable to that use-case (where the data being
| encrypted is itself random).
|
| AES-GCM breaks catastrophically if you reuse a nonce; but the
| only thing that happens if you reuse a nonce with AES-GCM-SIV
| for two messages is that an attacker can see if the messages
| are equal (since AES-GCM-SIV is a deterministic algorithm, this
| is pretty much unavoidable). So yes, "weaker notion of
| security", but still applicable to a lot more than just that
| use-case. I wonder why AES-GCM-SIV is not used more, since it's
| so developer-friendly and misuse resistant.
| nmadden wrote:
| (Article author here).
|
| Being able to see if two messages are equal means that it
| doesn't even achieve IND-CPA security (when nonces repeat).
| Although this may seem like a small loss of security, it can
| have significant consequences. For example, when you are
| performing encryption of long messages, you generally want to
| split them into smallish chunks -- otherwise you'll likely
| have to release unverified plaintext during decryption unless
| you buffer the entire message in memory. But now if your AEAD
| reveals message equality, like AES-GCM-SIV does under nonce
| reuse, then an attacker can see when _chunks_ are equal if
| you are not careful. So you can end up vulnerable to the kind
| of chosen plaintext attacks that are devastating against ECB
| encryption.
|
| Phillip Rogaway, co-inventor of the original SIV mode and the
| MRAE security model, discusses BEAST-style chosen plaintext
| attacks against online encryption modes using MRAE schemes in
| https://eprint.iacr.org/2015/189.pdf. As he says in that
| paper: "The paper defining MRAE never suggested that nonce-
| reuse was OK." It leads to security weaknesses, and AES-GCM-
| SIV has increasing likelihood of nonce reuse after 2^32
| messages.
|
| So, yes, AES-GCM-SIV is a lovely piece of work, but if you
| want to encrypt large numbers of messages with a single key,
| then you need to be very aware of the security definitions. I
| wouldn't recommend it for general use.
| Y_Y wrote:
| > "random nonces"
|
| I find it amusing in spite of the various words that have fallen
| out of favour in recent times for political reasons, "nonce"
| continues to soldier on.
| connicpu wrote:
| I would guess that it's because it doesn't have any special
| meaning in American English primarily, most Americans have
| never even heard of its meaning in British slang
| QuesnayJr wrote:
| I in fact only learned the slang meaning five seconds ago
| when this discussion made me google it.
| noodlesUK wrote:
| Agree, most of the Brits I know think it's hilarious that
| it's ended up as a term of art, and Americans are generally
| completely oblivious to its meaning.
|
| I am in no great hurry to change the word though. It's not
| something that comes up much outside of extremely technical
| contexts, and whilst it's a bad word, its regional character
| and multiple meanings kinda make it fine. It's not like it is
| being used for the meaning that's offensive, the meanings
| have unrelated histories (and the offensive one is much
| newer).
|
| I don't think it would be right to change an ordinary English
| word because it sounded similar to an offensive word in a
| foreign language, and I think that's essentially what's
| happened here.
| mjhay wrote:
| There was actually an NFT startup a while back that called
| itself "Nonce Finance." They wound up rebranding.
| cduzz wrote:
| Just googled it... yikes not the cryptography joke I was
| expecting...
| zarzavat wrote:
| Probably because this unfortunate state of affairs is very
| appealing to the British dark sense of humour. Americans seem
| much more inclined to want to replace any term that is even
| obliquely offensive.
|
| See also "Fanny pack" which has made its way into British
| English despite the crudeness.
|
| I do wish there was some alternative word so that I can discuss
| cryptography with my countryfolk.
| multjoy wrote:
| It has not, it remains a term of abuse.
| tommiegannert wrote:
| > If it is not 96 bits, then the value is first hashed with
| GHASH, GCM's universal hash function, and the full 128-bit output
| becomes the initial counter value: [---] However, we can't just
| assume that the output of GHASH is ideal with respect to
| collisions
|
| They already special-cased 96 bits, so couldn't they have
| special-cased 128 bits to be direct addition, without
| concatenation?
| thadt wrote:
| Sure, they _could_ have - but didn 't. Probably because they
| were strongly biased toward nonces being generated by a
| counter, and separating an external 'message counter' from the
| internal 'block counter' is a nice scheme to have essentially
| unlimited, large messages without any concern for nonce reuse.
|
| Except for subsequent experiences showing us that reliably
| keeping track of a counter can be a lot harder than it first
| appears, hence the attractiveness of randomized nonces.
| Simon_ORourke wrote:
| Sorry, but to my UK friends the phrase "random nonces" holds a
| different interpretation to the rest of us. Learned that one from
| sorry experience.
| steelframe wrote:
| In my experience nonce reuse doesn't happen because of a
| probabilistic collision. It happens instead because people who
| don't know the history or context of what they're doing make a
| change to the code base that results in the nonce being reused,
| and there were guardrails missing that should have been there to
| help prevent it.
|
| It stems from hubris I see repeatedly in the software engineering
| industry. "I know the constraints and am capable of engineering
| to them, so don't lecture me about the potential dangers. I'll
| just make sure we do it right, because I'm smart and capable and
| can do it right."
|
| They think the problem they need to solve is to write code that's
| correct today, while the actual problem they need to solve is
| that it remains correct tomorrow, next quarter, next year, and
| next decade. Based on repeated failures in this category I've
| personally witnessed, the majority of software engineers with
| fewer than ~10 years of industry experience lack an intuition
| about how software changes over time as people come and go.
___________________________________________________________________
(page generated 2024-05-29 23:02 UTC)