[Cryptography] Shortening block cipher length...

[Patrick Chkoreff]

Ray Dillinger wrote on 7/19/21 10:06 PM:

>      I don't think NaCl as it is today is vulnerable - but I do think
> that if and when it gets updated in the future by anyone who isn't DJB,
> it is ten times more likely to be updated in a way that leaves it
> vulnerable.  Everything has to be just so for an XOR-plaintext system to
> be secure.  "bright ideas" are more likely to break them.

The good thing for me is, if anyone "updates" my code, all my 
regressions tests will break.  Every single one of them.  These tests 
use fixed nonces and fixed private keys.  Everything is a deterministic 
function, just like "+" and "ln".  Of course in real life, a 24 byte 
nonce or a 32 byte private key is read from /dev/urandom, but it's all 
deterministic from there.

Now if Theodore Ts'o makes a mistake in the kernel, I might be in 
trouble.  Or if I'm on a virtual machine or a brand new machine whose 
entropy pool is a known pattern right before it hits my code, I'm in 
trouble.  When in doubt, roll a bunch of 16 sided dice and cat that into 
/dev/random -- assuming that works.

Even if /dev/urandom is "perfect" (whatever that might mean), there's 
still a 1 in 2^192 chance that I reuse a nonce -- or you can multiply 
that by the total number of messages I have ever sent with a given 
private key.

(I suppose I could use the private key to derive a deterministic 
permutation on the set 2^192, but then I'd have to maintain a counter as 
mutable state and always increment it.  Guessing a nonce would then be 
roughly equivalent to guessing the private key itself, and no randomness 
would be needed except to generate the private key.)

Although the odds seem to be in my favor, I honestly don't like the 
random nonce requirement one bit.  But DJB had authenticated encryption 
all wrapped up, with nice compact 256 bit keys, and I could not resist, 
because then NO ONE could EVER assail the wisdom of my choice. ;)


>       Like you, I trust DJB. He's good.  He knows why it's secure and
> knows what would poison that security and knows to refuse to do those
> things.  NaCl has withstood several years of use and scrutiny at this
> point.   I'd consider it usable but it's usable because the implementor
> is doing a thing that is in fact fairly hard.  The construction isn't
> insecure because it's based on flawed theory; the theory's sound.  It's
> almost-insecure because most implementors don't manage to implement it
> correctly, or don't manage to implement it in ways their clients can't
> somehow bungle, or don't manage to maintain the invariants that made the
> earlier versions secure while "extending" it later.

If someone is changing the scheme itself in a way that maps the same 
inputs to different outputs, I would be highly suspicious of that new 
scheme, and leave it to the experts to analyze it.  However, if someone 
merely refactored the code, preserving equivalence such that all my 
regressions tests still passed, I would only worry that they might have 
introduced a timing channel.


>       DJB's "never re-use a nonce" rule is one of the most rock-solid
> requirements of such systems. It's not even up for discussion.  But the
> fact that you noticed it means you have experience of systems where
> reusing a nonce is possible.  Any such system is already halfway to broken.

The fact that I noticed it only means that I am obeying Daniel J. 
Bernstein.  If /dev/urandom betrays me, I am sunk.


>   But there are dozens of "bright ideas" that involve reusing
> nonces, and somebody sooner or later will want to add "extra
> functionality" to a working system.  As long as DJB's maintaining it,
> you can trust him to tell them FOAD.  But we don't know how long that'll
> be.  In the base case, the XOR-Plaintext construction means you must be
> on guard against updates.

Nobody updates my code except me.  Even if DJB himself proposed a 
fundamental change and I accepted it, I would be forced to update all my 
regression tests and deal with any already encrypted data at rest.  I am 
likely to reject even a change from DJB unless he said there was some 
really stupid defect in his original scheme.


>>       I would be willing to implement different primitives for
> authenticated encryption, other
>> than DJB's.  I find your "superior counter mode" quite appealing.
> However, I would need a very solid
>> and stable algorithm with plenty of known test cases.
> 
>       I recommend using OCB mode instead of Counter mode.  It's a well
> studied, long standing standard and many freely available well tested
> implementations exist. It's a negligible fraction slower than Counter
> mode, but structurally it's a drop-in replacement.

So you're saying that would fit into DJB's overall elliptic curve 
scheme?  Because I'm not just doing symmetric crypto here, I need the 
authenticated asymmetric aspect as well.


>> Does one have to be a genius to read 24 bytes from /dev/urandom?
> 
> To do that, you first have to know what a nonce is.  Then you have to know why
> it's important.

First of all, it's important because Mr. Bernstein says it's important. 
That is enough for me to do it.  Yes, I have thought it through a bit to 
understand why it's important, but that's neither here nor there -- I do 
it because he says so.

> Then you have to know how to use it and how not to use it.
> Then you have to be able to design and implement something where an attacker
> can't force nonce reuse in some way.  And finally you have to design and
> implement everything 100% flawlessly and perfectly (see my previous comment
> about the expert cryptographer and the 1-character typo).

Well I hope I got this right:

https://github.com/chkoreff/Fexl/blob/1537afb4afef3ef6c3306203a3a6b0ab43112628/src/crypto.c#L30


-- Patrick