[Cryptography] Odd bit of security advice

[Peter Fairbrother]

On 05/06/18 01:27, Jerry Leichter wrote:
> In another thread, Jason Cooper quoted the following:
> 
> [1] https://datatracker.ietf.org/doc/rfc7539/?include_text=1
> 	Section 4: Security Considerations
>   "The most important security consideration in implementing this
>    document is the uniqueness of the nonce used in ChaCha20.  Counters
>    and LFSRs are both acceptable ways of generating unique nonces, as is
>    encrypting a counter using a 64-bit cipher such as DES.  Note that it
>    is not acceptable to use a truncation of a counter encrypted with a
>    128-bit or 256-bit cipher, because such a truncation may repeat after
>    a short time."
> 
> It's that last comment - that the bottom 64 bits of a counter encrypted with a 128- or 256-bit cipher may repeat after a short time - that really puzzles me.  Surely any 128- or 256-bit cipher with this property would immediately fail certification, as it would be easily distinguishable from a random permutation.

Well, by a short time they mean once every 2^64 (or whatever the 
truncation is) operations.

Whether a certification test would pick that behaviour up would depend 
on how the certification was done: if by analysis of the code, then yes, 
using a 64-bit truncation would cause certification failure.

However in order for a Monte Carlo type test to detect this behaviour it 
would need to compare > 2^64 outputs and look for duplicates - not 
something done in most certification tests.

Incidentally, if you do use the bottom 64 bits and generate less than 
2^64 messages, you still have unique nonces. After 2^64 messages (with 
the same key...) you start to get into trouble.



Also incidentally, if you have to randomly reset the counter every so 
often, in order to get say 128-bit security you would need a >128-bit 
counter - it depends on how many messages are sent.

Suppose you send 2^64 messages then randomly reset a 128-bit counter, 
rinse, repeat - the chance of a collision is then 1 in 2^64 (= the 
chance that the first 64 bits are the same).

Add more resets however, and you are birthdaying in 2^64, not in 2^128. 
After 2^32 resets or 2^96 messages you would have a collision.

To get 128-bit security you would need 128 bits (for the birthday) plus 
the 64 lower bits. And even that is only good for 2^96 messages.


-- Peter Fairbrother


> 
> What am I missing?
>                                                          -- Jerry
> 
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
>