Subject: [Cfrg] matching AES security

From: "D. J. Bernstein" <[email-masked]>
Date: 30 Jul 2014 12:33:36 -0000

Blumenthal, Uri - 0668 - MITLL writes:
> IMHO, the logic/reason of matching security levels of the
> cryptographic algorithms employed in a protocol suite is fairly
> obvious and does not need an explicit justification. 

Let's think through what "matching security levels" actually means for
matching elliptic curves with AES.

In the foreseeable future there will be billions of devices that users
are relying on for cryptographic computations, and it's easy to imagine
that a typical device will use at least one new key every minute, i.e.,
a million new keys within two years. That's more than 2^50 keys overall.

There are standard attacks that break _all_ of 2^50 AES-128 keys using a
_total_ of 2^128 easy computations. Even worse, there are standard
attacks that find _at least one_ of the keys using just 2^78 easy
computations, a feasible computation today.

These attacks assume that the attacker sees ciphertext for, e.g., an
all-zero block encrypted under all of the keys. Sometimes protocols
randomize their blocks to try to stop these attacks---but putting
complications into protocols to compensate for a cipher's deficient
security is _not_ a smart way to design a cryptographic system. For the
past decade I've been recommending moving to larger cipher keys,
precisely because of this attack against 128-bit keys.

For comparison, if we're talking about Curve25519 keys rather than
AES-128 keys, the fastest attacks to find one out of 2^50 keys are as
slow as the fastest attack to find a single targeted key. (This isn't
just an observation about known attacks; it's a theorem about _all_
attacks, following easily from the "random self-reducibility" of
Curve25519 DL, a very strong type of "worst-case-to-average-case
reduction".) Exactly the same comment applies to any other curve---I'm
using Curve25519 as a concrete illustration but don't mean to suggest
that it's special in this respect.

A standard batching mechanism (1999 Escott--Sager--Selkirk--Tsapakidis,
also crediting Silverman--Stapleton; for further analysis see 2001
Kuhn--Struik, 2004 Hitchcock--Montague--Carter--Dawson, 2006 Bernstein,
2012 Lee--Cheon--Hong, and 2012 Bernstein--Lange) finds all of the 2^50
Curve25519 keys more quickly than 2^50 separate DL computations, but
still takes time 2^150, millions of times more difficult than breaking
an AES-128 key.

If you scale down to more plausible amounts of future computation, such
as 2^100, then the comparison becomes even more lopsided. The attacker
is going to find millions of the users' AES-128 keys, but has chance
only about 1/2^50 of finding even _one_ of the Curve25519 keys.

> What benefit do you derive from including a stronger
> algorithm in a chain made of weaker algorithms?

Do you realize that you're arguing _against_ mixing AES-256 with a curve
as large as 512 bits?

In a world of 2^50 AES-256 keys, there's an attack that already has a
high probability of finding a key in time "only" 2^206. This is nicely
matched with the cost of breaking Curve41417. (I admit that Curve41417
is slightly more secure when the inner-loop cost is taken into account,
but let's not quibble.) What benefit do you think you're obtaining from
larger curves, such as NIST P-521 or E-521 or Microsoft's 512-bit curve?

The argument that AES-256 "matches" 512-bit ECC is supported only by an
oversimplified analysis of single-key attacks. Multiple-key attacks are
much faster for AES-256, and are obviously preferable for the attacker;
inferior attacks make no sense as a basis for evaluating security. If
you actually want a cipher that doesn't compromise the quantitative
security level of 512-bit ECC then you need to go far beyond 256-bit
cipher keys.

The point I'm making here is orthogonal to

   * Adam's point that comparing 2^200 computation to 2^250 computation
     is meaningless---we'll never do such big computations (see
     https://www.imperialviolet.org/2014/05/25/strengthmatching.html);

   * Mike's point that what actually matters up at this level is the
     risk of breakthroughs---e.g., quantum computers running Shor;
     
   * the point that several people have made about the low cost of
     moving from 192-bit ciphers to 256-bit ciphers (and the high cost
     of supporting an excessive spectrum of options)---so usage of
     256-bit ciphers doesn't imply that users want 2^256 security;

   * the point that it's already common practice to combine, e.g.,
     RSA-2048 with AES-128 and sometimes even AES-256, illustrating that
     the users' performance constraints are the biggest issue;

and various other arguments against the whole concept of "matching
security levels". What I'm saying is that if you _do_ want to "match
security levels"---for example, Joe Salowey wrote

   TLS supports 256-bit symmetric key ciphers and we want to have
   recommended curves to match this key strength

---then it's a huge quantitative error to pair AES-256 with 512-bit ECC.
All of the attack costs that I'm describing are thoroughly established
by the public cryptanalytic literature; I'm not aware of any dispute.

Perhaps CFRG should issue a warning about AES-128 being feasible to
break under plausible assumptions. A reasonable response to this threat
is to move to a 256-bit (or merely 192-bit, but see above regarding
options) cipher with Curve25519 (or Microsoft's 256-bit curve); this
would push all known attacks above 2^120, ample protection for the
foreseeable future. A 256-bit cipher with Curve41417 would push all
known attacks above 2^200.

---Dan

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 30 Jul 2014 10:06:19 -0400

> a million new keys within two years. That's more than 2^50 keys overall.

Dan,

Please explain what typical device will use at least one new key every 
minute?

In the typical devices I work with there will be at best one ECDHE 
exchange per day. Sometimes only once per month. (one message/5min = 312 
short messages/day to protect with AES-CCM or GCM). (we are working on 
changing once per life of sensor)

Now if you look at the server side that is receiving messages from 
10,000 fielded sensors and thus has 10,000 ECDHE exchanges/day (or per 
month), then the risk is a tad different?

thanks

---

From: Natanael <[email-masked]>
Date: Wed, 30 Jul 2014 16:25:12 +0200

minute?
>
> Now if you look at the server side that is receiving messages from 10,000
fielded sensors and thus has 10,000 ECDHE exchanges/day (or per month),
then the risk is a tad different?

It is not inconceivable that all kinds of mobile devices (not just
smartphones, but smartglasses, watches, shoes, your backpack, home
automation devices, electric cars which talk with every other large vehicle
nearby, etc) will be part of traffic anonymization networks like Tor and
I2P which frequently establishes new encrypted tunnels, that they'll be
using instant messengers with various OTR like protocols which rekey often,
so be part of radio mesh networks (see apps like Serval), etc... Then
there's file sharing (Flud is a nice torrent client for Android). And don't
forget randomized cover traffic to disrupt traffic analysis.

That's not even considering home servers which will do all of the above and
much more.

Few devices will only maintain a small set of connections over their
lifetimes, and many will be rekeying often for the sake of PFS (perfect
forward secrecy), etc...

This may be 10 years off before it becomes common (a large fraction of
users doing it), but it's highly likely to happen. The total number of
encrypted links will increase very drastically over time.

Your sensor may not be affected, but the rest of the world will be.

---

From: Tanja Lange <[email-masked]>
Date: Wed, 30 Jul 2014 18:34:09 +0200

Dear Bob,
> month), then the risk is a tad different?
For every ECDHE there is a fresh AES key, so for whatever number 
of key exchanges you assume there is also an AES target. This is on
top of long-term connections that update the AES keys and devices
that use only symmetric keys. If that number is less than 2^50 then
the worry about finding AES-128 keys by chance gets smaller, but 
in any case it's significantly easier than breaking the DLP on an
elliptic curve over a field of ~256 bits (which needs 2^128 group
operations, so more than 2^140 bit operations).
 
All the best
	Tanja

---

From: Paul Lambert <[email-masked]>
Date: Wed, 30 Jul 2014 10:19:18 -0700

On 7/30/14, 5:33 AM, "D. J. Bernstein" <[email-masked]> wrote:

>all-zero block encrypted under all of the keys.

So, would this attack be mitigated by a change in algorithm mode?
In particular, if this is true for AES-CCM or AES-GCM, it does
not look like it would apply to AES-SIV.

Paul

>Sometimes protocols
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>http://www.irtf.org/mailman/listinfo/cfrg

---

From: Benjamin Black <[email-masked]>
Date: Wed, 30 Jul 2014 10:39:46 -0700

AES is not the only symmetric cipher in use today and we can expect new
ciphers to supersede it during the service life of the new curves under
discussion. The goal is matching security levels of the suite components as
designed, not adjusting things based on attacks that emerge against a given
component over its service life.

b

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Wed, 30 Jul 2014 17:49:02 +0000

>matching elliptic curves with AES.

Sure.

>computations, a feasible computation today.

Could you please point me at a decent reference/description of this attack?

>These attacks assume that the attacker sees

[And can identify as such]

>ciphertext for, e.g., an all-zero block encrypted under all of the keys.

You are saying that there has to be _the same_ known plaintext pair for
_all_ of these 2^50 keys in order for the attack to work? And it takes
2^128 computations?

What happens if there's fewer keys than 2^50? What happens if you only
have probable plaintext? What happens if you have known plaintext pairs
but they differ across the 2^N keys?

>Sometimes protocols randomize their blocks to try to stop these
>attacks---but putting

You have a point. But let's evaluate/discuss this attack (its basics,
costs, applicability, etc) before figuring out costs of defending against
it.

>oversimplified analysis of single-key attacks.

Which is what most people are concerned about, and IMHO justly so. But
let's discuss.

>Multiple-key attacks are
>.......................

The question is whether they are plausible and/or feasible.

>by the public cryptanalytic literature; I'm not aware of any dispute.

"Multiple-key attacks" reference please?

>break under plausible assumptions.

I'd like to get a better understanding of both the attacks and the
assumptions. Probably the entire group (CFRG) should evaluate their
plausibility.

TNX!

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 30 Jul 2014 14:08:28 -0400

> operations, so more than 2^140 bit operations).

I am not keen on rekeying for the sake of it. There are security costs
as well as benefits. In particular a lot of systems have the property
that they are break once, run anywhere. Just as we now think 50
ciphers give less security than 5 as the strength is determined by the
weakest one an attacker can get the parties to use, rekeying for the
sake of it is probably a bad thing.

Forward Secrecy is a good thing of course, but generating ephemeral
keys or mix ins is not what I think of when someone says rekey. To me,
rekey implies rebuilding the authentication relationship between the
end points. Thats a lot more work.

I am working on making it possible to rekey PPE once a week because I
want to create a forcing function for usability. Security people often
think they can get users to do silly things every 90, 60 or even 30
days. But even security folk get fed up of hoops when its once a week.
But LOTS of folk got very worried about that suggestion and I agree
that it would be bad operationally. I doubt rekey more than once a
quarter is desirable, even if the whole process is transparent.

The only reason I rekey at all is because people read their mail on
mobile devices and those get lost. So rekeying is a good way to limit
exposure to that risk. But I don't plan to ever roll per device
credentials or keys. If a public key algorithm isn't good for a
billion uses without security concern, then don't use it.

AES does have slightly different concerns. But really, if you are
worried about the need to rekey then you should go to a 256 bit key
first and then think about rekeying AES.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 30 Jul 2014 11:12:32 -0700

Is the attack DJB mentioned an attack on AES?  No: AES matches the PRP
security definition. Is it an attack on Salsa20? No: it meets the security
claim.

Rather it's the obvious point that a man who strains half a lake has half
the fish.

This has been pointed out before on this list, and is really on the level
of an exercise in probability.

Sincerely,
Watson Ladd

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Wed, 30 Jul 2014 18:24:36 +0000

> Rather it's the obvious point that a man who strains half a lake has half the
> fish.
> 
> This has been pointed out before on this list, and is really on the level of
> an exercise in probability.

In that case (probability game) this attack does not seem realistic, let
alone plausible. 

How many plaintext pairs can you store (alternatively, which one "master"
plaintext would you use)? For how many keys? How do various encryption modes
impact your ability to search your tables (i.e., might using IV interfere
with it)? How are you planning to identify that magic plaintext encryption
in the traffic stream? What do your resulting probabilities look like in
real world, after all of this has been taken into account?

I won't dump my AES-128 just yet. :-)

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 30 Jul 2014 11:47:50 -0700

Thanks, DJB, for advancing this argument for non-512-bit curves.  As the other guy with a 400-and-something-bit curve, I was going to have to do it sometime this week as well, and you made the argument more coherently than I would have.

On Jul 30, 2014, at 11:12 AM, Watson Ladd <[email-masked]> wrote:

> > AES is not the only symmetric cipher in use today and we can expect new ciphers to supersede it during the service life of the new curves under discussion. The goal is matching security levels of the suite components as designed, not adjusting things based on attacks that emerge against a given component over its service life.
> 
> Is the attack DJB mentioned an attack on AES?  No: AES matches the PRP security definition. Is it an attack on Salsa20? No: it meets the security claim.
> 
> Rather it's the obvious point that a man who strains half a lake has half the fish.
> 
> This has been pointed out before on this list, and is really on the level of an exercise in probability.
> 
> Sincerely, 
> Watson Ladd
> 

To answer Uri’s question, yes, this attack requires a shared known plaintext block across all the connections.  This is most likely to happen through the use of CTR mode with a deterministic nonce; or the MAC of the empty string; or explicit key confirmation.

Also, the attack is not realistic for AES-128 in the near future, and we don’t have to warn users about it.  But it’s more realistic than a 128-bit key exhaustion.

But even in a single-target model, you can’t just compare the brute-force security levels of, say, AES-192 and NIST-P384.  Brute force is not a realistic threat to either one.  Instead you have to consider the risk that an attacker with a given budget can hack you.  This risk would encompass things like:

* Value of the keys.  The long-term ECC keys are worth more.
* Protocol tightness.  Time/memory/data attacks are not necessarily limited to multiple-user attacks, and are likely to weaken AES more than ECC.
* Chosen-plaintext are more likely to affect AES.
* Quantum computation.  More bits of AES buys you more resistance, but more bits of ECC does not.
* Mathematical breakthrough.  Hard to quantify.
* Side channels.  More bits don’t buy you much more security.

My conclusions from this would be:

* Past 192 bits of security, brute force security ratings are basically meaningless even with linear time/data tradeoffs.  Stronger ciphers are mostly a hedge against breakthroughs.
* We use 256-bit AES because it’s not much more expensive than 192-bit AES.
* We should consider a more-than-384-bit elliptic curve if and only if it’s not much more expensive than a 384-bit curve.
* There’s not much point to ed-512-mers if it costs twice as much as ed-384-mers.
* The unusual-sized curves Curve41417 and Ed448-Goldilocks should be considered if and only if they’re not much more expensive than the 384-bit alternatives.  This has been demonstrated for Goldilocks, which is 6% slower than ed-384-mers on Sandy Bridge.  I believe that it will also be true for Curve41417, but so far I’ve only heard numbers for Cortex A8 NEON, and none of the alternatives have optimized implementations on that platform.

Cheers,
— Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 30 Jul 2014 12:26:12 -0700

> more bits of ECC does not.

Wouldn't more qubits mean substantially higher cost and it will take 
some time (decades?) to get from 5 (?) to 256 qubits and beyond?

If so, higher bit curves have an advantage, esp. for persistent 
structures like CA certificates that cannot count on fast crypto upgrade.

---

From: Andy Lutomirski <[email-masked]>
Date: Wed, 30 Jul 2014 12:45:50 -0700

> I won't dump my AES-128 just yet. :-)

In my opinion, this approach to crypto has been inappropriate for
quite some time.  Despite the fact that, theoretically, there were
nice attacks against MAC-then-encrypt, people kept using it because
they couldn't imagine how those attacks could work in the "real
world".  That didn't go so well.

If people start using 256-bit keys, then these attacks are a
non-issue.  Or someone could try to find a protocol that is *provably*
immune with 128-bit keys.  But let's stop relying on our own failures
to image how these attacks might work.

--Andy

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 30 Jul 2014 13:26:21 -0700

On Jul 30, 2014, at 12:45 PM, Andy Lutomirski <[email-masked]> wrote:

> —Andy

I’s really hard to get tight security bounds.  To start with, you’ll need something stronger than the standard PRF/PRP assumptions; maybe ideal ciphers would be enough?  Likewise with EC signatures, even in the ROM the bounds are really far from tight.

But yeah, 256-bit symmetric ciphers are cheap.  If the small performance difference doesn’t matter much to you, then just use them everywhere.

— Mike

---

From: Sandy Harris <[email-masked]>
Date: Wed, 30 Jul 2014 16:54:58 -0400

> precisely because of this attack against 128-bit keys.
....
> high probability of finding a key in time "only" 2^206.

Does the construction used in Enchilada solve those problems?
https://aezoo.compute.dtu.dk/doku.php?id=enchilada

It puts a 256-bit key into Chacha, then uses Chacha both to
generate AES round keys (so there is no 128-bit or 256-bit
AES key to attack) and to add whitening that changes for
every block (so common general attacks on block ciphers
all fail).

---

From: James Cloos <[email-masked]>
Date: Wed, 30 Jul 2014 16:55:47 -0400

>>>>> "PH" == Phillip Hallam-Baker <[email-masked]> writes:

PH> To me, rekey implies rebuilding the authentication relationship
PH> between the end points. Thats a lot more work.

I don't think that meshes with what most of the participants in the
tls1.3 discussion think.

My understanding of all of the rekey-instead-of-renegotiate threads
is that everyone who wants that expects to use the same algorithm
initially used to negotiate the symmetric key to negotiate a new one
without any changes to which symmetric algorithm is used, or to any
authentication which took place at the start.

So it seems that there is significant interest in just changing the
symmetric keys every so often for long-running tls sockets.

[Not commenting on whether that change should occur, just on that which
everyone on the tls list seems to write about.]

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Wed, 30 Jul 2014 21:28:16 +0000

> To answer Uri’s question, yes, this attack requires a shared known plaintext
> block across all the connections.  This is most likely to happen through the
> use of CTR mode with a deterministic nonce; or the MAC of the empty string; or
> explicit key confirmation.
> 
> Also, the attack is not realistic for AES-128 in the near future, and we don’t
> have to warn users about it.  But it’s more realistic than a 128-bit key
> exhaustion.

Good points! I concur.

> But even in a single-target model, you can’t just compare the brute-force
> security levels of, say, AES-192 and NIST-P384.  Brute force is not a
> realistic threat to either one.

Again, I concur. But still, we need some ways to compare, e.g., NIST-P384
with NIST-P521. You cannot say "beyond bit-length X they're just all the
same".

> Instead you have to consider the risk that an attacker with a given budget can
> hack you.  This risk would encompass things like:
> 

Yes.

> * Protocol tightness.  Time/memory/data attacks are not necessarily limited to
> multiple-user attacks, and are likely to weaken AES more than ECC.

Don't know. Maybe.

> * Chosen-plaintext are more likely to affect AES.

Probably the opposite. Easier to mount against AES, but AES is more immune
against them.

> * Quantum computation.  More bits of AES buys you more resistance, but more

Yes.

> * Mathematical breakthrough.  Hard to quantify.

Yes. :-)

> * Side channels.  More bits don’t buy you much more security.

Yes. :-)

> * Past 192 bits of security, brute force security ratings are basically
> meaningless even with linear time/data tradeoffs.  Stronger ciphers are mostly
> a hedge against breakthroughs.

OK, agree.

> * We use 256-bit AES because it’s not much more expensive than 192-bit AES.

Actually I don't know why we don't use 192-bit AES. Maybe you're right.

> * We should consider a more-than-384-bit elliptic curve if and only if it’s
> not much more expensive than a 384-bit curve.

See your point about "a hedge against breakthroughs". We don't know if a
breakthrough would be made against ECC, and if it would – whether it would
be hampered "enough" by more bits, and how many more bits would be needed to
stay "safe".

So while a scalable quantum computer (probably) obliterates ECC, there could
be mathematical advances that are less drastic. I.e., there could still be
reasons for larger curves to stay around.

> * The unusual-sized curves Curve41417 and Ed448-Goldilocks should be
> considered if and only if they’re not much more expensive than the 384-bit
> alternatives.  This has been demonstrated for Goldilocks, which is 6% slower
> than ed-384-mers on Sandy Bridge.  I believe that it will also be true for
> Curve41417, but so far I’ve only heard numbers for Cortex A8 NEON, and none of
> the alternatives have optimized implementations on that platform.

Don't know.

---

From: Nico Williams <[email-masked]>
Date: Wed, 30 Jul 2014 17:37:54 -0500

> Please explain what typical device will use at least one new key every

Er, well, smartphone apps might well poll/get pushed to that
frequently, altogether, with a new key per-poll/push.  Sure, the
protocol involved might not generate a new key per-event, but if the
protocol is TLS, then it will.

DJB's point is that we should permit "odd" match-ups like AES-256 and
Curve25519 _because_ AES-128 is weak in plausible scenarios.

I'm having a hard time objecting to that!

(BTW, that's a much more serious problem for Kerberos than for TLS w/
session resumption.)

Nico
--

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Wed, 30 Jul 2014 23:08:34 +0000

>protocol is TLS, then it will.

Maybe... A good argument to avoid TLS. :-)

>Curve25519 _because_ AES-128 is weak in plausible scenarios.
                                          ^^^^^^^^^ :-)

There already are such "odd" match-ups, and I guess the trend is here to
stay.

But to do it because of attackers "getting _all_ of your 2^50 keys with
2^128 easy (sic!) computations"? (I guess you could convince about half of
the existing atoms in the Universe to do one computation for you, and
maybe store the result. But lookups would have to be extra! :).

>I'm having a hard time objecting to that!

:-)

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 30 Jul 2014 19:47:22 -0400

> I'm having a hard time objecting to that!

I would accept it done right.

i.e. set up the keys with an initial 256 bit exchange and then use the
ephemeral 128 bit key as a mix-in to add PFS.

256 bit secrecy plus 128 bit forward secrecy would be good enough for
most applications.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 30 Jul 2014 20:30:14 -0700

>>Curve25519 _because_ AES-128 is weak in plausible scenarios.

This is what rainbow tables are for. Let's suppose f:S->S, |S|=n. To
find preimages of k points p_1, ... p_k,
I do the following: pick s points q_1, .. q_s, store (q_i,f^r(q_i)) in
a table, and compute f^j(p_t) for each j and t,
checking if I get f^r(q_i) for some q_i. If I do, I calculate the
intermediate iterates of q_i, one of which is likely p_t.

The storage is s, while the number of points is sr, and I win with
probability about srjk/n, doing sr+jk work.
There is a higher-order collision term, but it's negligible.

This isn't new: rainbow tables were used to reverse password hashes in the 90's.

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Johannes Merkle <[email-masked]>
Date: Thu, 31 Jul 2014 11:37:31 +0200

> Could you please point me at a decent reference/description of this attack?

The attack is very simple:
- Gather a list of 2^N cipher texts resulting from the _same_ plain text encrypted under 2^N random keys.
- For 2^(128-N) randomly chosen (different) keys, encrypt the known plain text and check if the resulting cipher text
matches one of the gathered cipher texts

Assuming the cipher to be a random permutation, a collision occurs with probability 1 - (1-2^(-N))^N which approximates
1-1/e. If you have sorted the list of gathered cipher texts, the attack takes 2^(128-N)*log(N) steps (and 2^N space).

-- 
Johannes

---

From: Robert Moskowitz <[email-masked]>
Date: Thu, 31 Jul 2014 09:51:02 -0400

> But yeah, 256-bit symmetric ciphers are cheap.  If the small performance difference doesn’t matter much to you, then just use them everywhere.

Except the cost to change standards where they are 'hardwired' in. I 
have to figure out how to expand the cipher choice for 802.15.4 without 
really breaking the MAC Header.  Only 3 bits for the cipher selector and 
0 - 6 already used...

I should use the September meeting in Athens to socialize how to address 
this...

The whole family of 802.15.N (N={4, 6, 7, maybe8}) are like this. Then 
IEEE 1901.2 basically copied the 802.15.4 MAC.

But this list is about selecting good crypto.  Elsewhere we need to 
think really hard about USING good crypto.

---

From: Brian Smith <[email-masked]>
Date: Thu, 31 Jul 2014 08:57:50 -0700

On Wed, Jul 30, 2014 at 5:33 AM, D. J. Bernstein <[email-masked]> wrote:
> security is _not_ a smart way to design a cryptographic system.

I agree that it would be better to not need to randomize blocks to
avoid the attacks you alluded to. However, it seems like randomizing
the blocks is often easy; for example, I think it would be pretty easy
to define AES-GCM and ChaCaa20-Poly1305 cipher suites for TLS in a way
where the initial nonce is comes from the PRF and then incremented.

Don't you think it is worthwhile to do such randomization anyway,
since the randomization acts as a second line of defense against a
variety of problems? Is doing so harmful in some way?

>      the users' performance constraints are the biggest issue;

I agree with this. I'd also like to point out that I've yet to hear
anybody say that the P-256 curve is too slow for them to use. I've
heard others say that it would be nice to have a faster curve like
Curve25519, and I've heard people say that it is important to replace
P-256 with a curve that we trust more like Curve25519 (for some value
of "we"). Curve25519 has kind of become the default choice since it
seems to meet both the "nice to have" performance criteria and the
"must-have" security criteria for many people.

However, as a thought experiment, imagine that we had a proof that
P-256 was secure (including a proof that the mysterious constant is
not a security issue). I think a lot of the urges to replace P-256
would vanish because P-256 performance isn't that bad and almost
everybody has an implementation. That, combined with the common sense
that computations per second will increase and attacks will improve,
makes me think that it makes more sense to standardize on a curve with
roughly the same performance of P-256 but with better security,
particularly if such a curve could cover multiple security levels
(128-bit and 192-bit) so that there is less need to rely on
negotiation mechanisms in protocols to select an acceptable curve.

I think it would make a lot more sense to standardize one
~192-bit-security-level curve than to standardize one 128-bit curve
AND one 192-bit curve AND one 256-bit curve just so we can say we've
"matched" security levels. I don't think "matching" is useful for many
applications, including in particular the use of TLS in web browsers
and similar applications.

It would be interesting to hear from people who could not use P-256,
Curve41417, or other curves of around the same performance level for
*performance* reasons.

Cheers,
Brian