# Simple designs for provable security in cryptographic primitives

We can say that a cryptographic primitive has $n$ bits security against a type of attack if it cannot break it in less than $2^n$ time (time-area product in some cases). The cryptographic primitive could be said to be $n$ bits secure if the fastest possible attack (theoretical and future attacks of the same type included) takes at least $2^n$ time.

To make such security proofs, we need to analyze our crypto primitive. If we have more complex design, we may have more security (and performance, whatever else is desired) out of the box, but we won't be able to prove it.

Examples:

• Salsa20/15 according to Wikipedia is 128-bit secure against differential cryptanalysis, and uses only add, rotate, xor with nonlinearity from add
• SHA3 has 24 rounds and for $n$ output bits is $\frac{n}{2}$-bit secure against collisions with some reasonable assumptions, and uses only rotate, xor, not, and with nonlinearity from and

So we could use a simpler design, and thus make it easier enough to cryptanalyze that we can make a security proof. With that, we can know exactly how many rounds are needed and use only that many. In contrast:

• AES-128 was 128-bit secure against all attacks with 6 rounds at the time of creation, 4 rounds were added as a security margin, for total of 10 rounds, uses s-box, xor, shift, add with nonlinearity mostly from s-box
• SHA-256 has 64 rounds (no reason?) and is 128-bit secure against collisions for 47 rounds, uses add, rotate, xor, and (for Choose/Majority) with nonlinearity from add, and

We expect that with their more elaborate design, they are more efficient, needing less rounds for the same security and offering better performance. Their complexity makes designing an attack against them much harder.

What is better practice now, to design something simply so it can be proved secure, or design something more complex and rely on it not being broken in its lifetime?

There is always the possibility that a new attack can come up in the future and break something that was proven secure against every type of attack known at the time. But nothing can defend against that really.

Also, the comparison here is of the designs - it wouldn't be fair to put a 256-bit stream cipher up against a 128-bit block cipher, and a sponge hash against a Merkle-Damgard hash. It also happens to be that Salsa20 and SHA3 are newer than AES and SHA2.

• "hope" means you're not doing cryptography any more, so the complex route seems like a non-option. – Ella Rose Oct 7 '17 at 20:31
• How are you defining cryptographic efficiency when you say whatever efficiency? – Paul Uszak Oct 7 '17 at 20:35

to design something simply so it can be proved secure

We currently cannot prove the security of anything (well, other than informational secure things such as OTP), without making some assumptions. The best we can do is:

• This is secure, assuming that this abstract problem is hard (but that says nothing about whether the abstract problem is actually hard). Public key cryptosystems tend to be in this category.

• This is secure against these classes of attacks (but that says nothing about other types of attacks). AES is in this category, as we have a proof of security against linear and differential cryptanalysis.

and hope that it's not broken in its lifetime?

We don't know how that can be avoided, either in simple or in complex systems.

• However, if you can build upon existing algorithm(s) and prove them secure if the premise of the other algorithm(s) hold, you should definitely go that way, of course. E.g. OAEP being secure if RSA and (certain aspects of) the hash are secure. – Maarten Bodewes Oct 7 '17 at 22:30
• @MaartenBodewes Although as poncho states in his opening paragraph, OAEP <- RSA <- hash could be a house of cards built on sand... – Paul Uszak Oct 7 '17 at 23:58
• @PaulUszak Which opening paragraph would that be? – Maarten Bodewes Oct 8 '17 at 20:01
• @MaartenBodewes That would be the first one. If there is no proof for the underlying hash, constructs making use of it may be likewise unsound. It's not important... – Paul Uszak Oct 8 '17 at 20:22