Subject: [saag] A case against algorithm agility (long)

From: ianG <[email-masked]>
Date: Sat, 03 May 2014 16:45:43 +0100

I've jotted down some notes on the case against agility, as mooted.
Sorry, long.

It should be called "algorithm agility considered harmful" but I've
found that some people are irrationally offended by words.  Offense
doesn't worry me, but distraction helps nobody.

By algorithm agility, I mean the ability to swap AES for TDES for
ChaCha20 or MD5 for SHA1 for SHA256 or GCM for CBC for CTR or RSA for EC
for DSA for ... and including small groupings of same such as
AES+HMAC+SHA+CBC.  The ability to select the entire suite is another
issue, maybe discussed later.

1.  Black boxes they ain't.  Algorithms are sometimes characterised as
black boxes that can be substituted at will.  Unfortunately it's only a
hope, it's not met in practice.

Consider (a) the emerging sense of sponge constructions, (b) emerging
calls for 32 byte block sizes and a past of 8 bytes, (c) tendency for
stream ciphers to be blocks underneath, (d) the whole stream v. block
debate, (e) the shift to AE, (f) changing keylength goals over time.

It's simply not the case that you can reliably blackbox the cipher, the
hash, the mac, the mode or any other component.  Yes, you can design
something that substitutes in various black boxes according to this
vision, and you can force all your algorithms to work as black boxes but
the result is inelegant, klunky and undesirable.  Hard to maintain, and
new models cause contortions leading to weakness.

2.  Strength.  Universal substitution is bad, strength alignment is
needed at a minimum, and this is not a casual endeavour for mindless
tweaking.

Draft section 2.4 makes it pretty clear that just switching black boxes
back and forth is not sufficient, as the algorithms should be matched in
strength.  So, if we've decided to allow algorithm agility, we have in
effect outsourced strength alignment to the public, which is someone who
isn't capable of doing it.  e.g., we are negligent by charter, we've
squandered our chance to actually do what we ourselves are capable of
doing:  designing a matched suite.

3.  Config.  The choice of agility is a claim that the user population
can make good choices.  Yet, this isn't met by experience:  Nobody
(approximately) has confidence in user-land config strings, e.g.,
OpenSSL.  They are so complicated and there are so many traps that only
a real expert has confidence in own work, and that's not actually seen
often enough to justify talking about it.  Everyone (approximately)
relies on defaults delivered, and so does everyone upstream, until you
discover that your experts are also relying on other defaults from other
experts who were relying...  c.f. Android debacle.

Over at the BetterCrypto group that publishes a guide on how to
configure and use safer stronger algorithms, they seem (by my
observation) to spend about half their time on one thing:  OpenSSL
config strings.

What a waste.  For what?

4.  Marginality.  Any benefits from tweaking/swapping/improving blackbox
algorithms are marginal and/or esoteric.  For the most part, any cipher
gets you 99.999% of the grade.  Same with any HMAC, any mode properly
implemented.  The only people who can or will crack weaker algorithms
(DES?  RC4) are people who will also bypass the crypto, and are already
doing it.

So if we were doing risk analysis (which is the only scientifically
founded method, albeit weak) anything above DES is a waste.  Now, it so
happens that for next to no cost, we can do much better than DES, e.g.,
AES or better even.  *So we might as well* and thus I fall also to
hubristic desire for more algorithmic delight.

But the /difference/ between is not going to effect the user public.  It
certainly doesn't justify enabling a difference.

5.  Negotiation between software agents is a crock.  Software agents
don't negotiate, people do, and that's by definition.  The complicated
matching of ordered preferences that is called agent negotiation is a
minefield of errors, bad user experience, and opportunity to attack.
The complication ensures that implementations will not have an easy ride
together, and even one implementation negotiating against itself is no
easy thing.

6.  Attacks.  The existence of algorithm agility opens up the
possibility of the downgrade attack.  E.g., trick the config string
(below) to default to the NULL cipher.  Or trick the negotiation to
choose the weakest cipher.  Etc.

It also opens up the possibility for bugs (benign) and lousy user
experience.

7.  Need.  We still have no evidence that any attacker ever has attacked
the crypto algorithms in TLS or other properly designed protocols (iii).
 The closest we've got (to my knowledge) is the 512RSA phishing attacks
in the far east (yes, take that choice away, why on earth do we let
users choose key sizes?).

We simply have no reason to believe that any of the well-designed
algorithms will be cracked in the next 10 years.  Our expectation that
they could, derived from WWII warstories and thrilling self-serving
media headlines, is not a foundation to say there is any expectation at
all.  It seems that we expect them to fail, and we act as if they will
fail, *because we can*.  Not because it is likely.

Meanwhile, our actual record of security is rock-bottom because while we
put exorbitant attention on the next-to-impossible case of algorithm
failure, we ignore the actual, measurable and costly failure that bad
protocols contribute to in userland:  phishing, server breaches etc.
"Out of scope" means we aren't professionally doing risk analysis.

8.  Speed.  In contrast, ciphers are so slick these days that the best
today competes with the best of 20 years ago, CPU cycle-wise.  And
99.99% of the users have so much CPU that they can never notice the
difference.

(This is not to be confused with those who work at the sharp end, with
heavily loaded and balanced machines.  These are the people who can pay
for performance, and do.  They can also pay their suppliers and
suppliers' suppliers to influence standards orgs, so it's probably wise
to remember that these people can deal with any sub-optimal performance
by two ways:  buy influence here, or buy bigger boxes at the shop.)

(Same applies to all HMACs, modes, etc.)

9.  Problems.  In contrast, there are plenty of problems in the
protocol, the layouts, the interactions, the features.  Check the
evidence:  as far as I am aware, all failures were outside the algorithms.

10.  Track record.  Historically, no record of agility saving us.  The
one time it might have saved us was in switching to RC4.  That might be
called a save, but it wasn't really;  it was really a switch in protocol
to use stream ciphers, and we switched back to arguably the worst cipher
available.  There was no designed agility to switch from block to stream...

So if we think RC4 saved us, then we can (e.g.) no longer argue for
stronger ciphers...

11.  MD5.  And then there is MD5 in TLS;  why did it take so long to get
rid of it?  It turns out that algorithm agility wasn't universally
deployed all the way through.  Why not?  Because it wasn't easy to put
algorithm agility into all the places.

So the one time we really needed it ... it wasn't there for us?

12.  Distros rule!  Actually getting a live switch *in algorithms* out
to userland is very difficult.  It's harder to get people to change
their config strings than it is to send out a new distribution.  Every
Linux sysadm understands apt-get.  Every apple user understands Security
Update, click to restart.  Every MS admin understands backup & re-install.

Relatively few of them understand how to tweak the settings.  Indeed,
few of them have the first clue about algorithms.  Indeed, it's really
bad advice to say "switch to RC4" because we have little idea as to
whether they'll get it right, or whether it'll trigger some other problems.

13.  Arrogance.  There's something of a hubristic bias in algorithm
agility.  We do it because we can, because its cool, and we're happy to
ignore the downstream noise.  We invent rationales as to why we should
do it.  We talk about how we optimised our implementation to get 5%
better than the other guy.  We pontificate on how CTR is better than
GCM, because because, we enjoy poking our thumb at the NSA.

I once knew a guy who said "it is my right to use odd-length RSA keys."
 I lost a couple of days debugging before I figured out why his keys
would not communicate with mine.  It is fine to do this in isolation,
pushing rights and beliefs, but really, are we in the business of
religion, exporting democracy, motherhood and apple pie?

Or are we in the software business?  Trying to get the maximum
protection across to an Internet of users?

What this doesn't argue against:

A.  the past.  E.g., TLS is what it is, here and now, this is not an
argument to suggest that TLS WG should drop everything and stop doing
algorithm agility.  They're stuck with their legacy, and the good thing
is that we now have a good solid historical example to prove or disprove
the hypothesis.

B.  this ID shouldn't be written.  Regardless of the hypothesis, there
are many protocols that use the technique.  Documentation of it is a
good thing.  However, it is better to encourage them to use better
practices than to laud the best practices of the past, once past their
sell date.

Notes.

(i) where above I mostly write about ciphers, the arguments extend to
other components and choices such as HMACs, modes, public key, lengths etc.

(ii) this is just today's effort.  I'll keep refining it, fire away!

(iii) by properly designed protocols, I generally exclude wireless which
are designed to be weak and breachable.  By attack, I mean an aggressive
breach including measurable damages.  I accept rework as measurable
damages, typically, but academic demos and reputation thefts don't cut it.

---

From: Benjamin Kaduk <[email-masked]>
Date: Sat, 3 May 2014 23:10:49 -0400 (EDT)

> (DES?  RC4) are people who will also bypass the crypto, and are already

My apologies for cherry-picking just a single point, but commercial DES 
crackers are in the $200, 1-day range these days.  That there is even a 
commercial market for it suggests that they are in use, and not just by 
people who could by pass the crypto.

-Ben Kaduk

---

From: ianG <[email-masked]>
Date: Sun, 04 May 2014 12:46:32 +0100

On 4/05/2014 04:10 am, Benjamin Kaduk wrote:
> crackers are in the $200, 1-day range these days.

Ah very true, perhaps t-DES.  And one can buy machines for crunching
SHA256, albeit the first N digits in 10 minutes.  I guess some of the
programmable ones could be put to MD5 and SHA1 efforts.

> That there is even a

Yes, this is fascinating.  There's also the SSL-interceptor boxes which
allegedly will take your commercially provided sub-Root.  Who uses those
machines and why?

Information like that would be really useful to tell us what matters.

iang

---

From: Yoav Nir <[email-masked]>
Date: Sun, 4 May 2014 15:35:30 +0300

> allegedly will take your commercially provided sub-Root.  Who uses those

These boxes are used for whatever purpose people want access to the plaintext for. Uses range from running so-called "next generation firewall”([1]) policy on them, to looking for dissidents in certain countries.

Commercial CAs rarely give sub-root certificates, and when they do, they have  name constraints ([2]), so they can’t be used for generating fake certificates for mail.google.com.  These boxes generally either generate their own self-signed CA, or get a corporate sub-CA. Either way, it requires clients to be configured with the interception CA.

Yoav 

[1] “next generation firewall” is a marketing term, but in general classic firewall can block addresses, protocols and ports, whereas “next generation” looks at higher layers as well. So a classic firewall can block your access to Facebook, a next-generation firewall can block your access to Farmville.
[2] Yes, there were cases where this was not followed.

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 04 May 2014 22:30:58 -0400

> doesn't worry me, but distraction helps nobody.
...

It is a good idea to limit the number of possible permutations of 
allowed algorithms.

However, the pros for the algorithm agility are:
* compliance with standards (unless all standards in the world specify 
the same suite)
* upgrade to new algorithms (the time-line of the "old" and the "new" 
algorithms typically overlap)
* easier system maintenance (it's easier to add only a new algorithm to 
an old product that is only maintained as opposed to actively developed)
* there might be no single algorithm that is perfect for everybody

---

From: S Moonesamy <[email-masked]>
Date: Mon, 05 May 2014 02:35:43 -0700

Hi Andrey,
At 19:30 04-05-2014, Andrey Jivsov wrote:
>* compliance with standards (unless all standards in the world 
>specify the same suite)

There is an international industry standards group working on a 
reference architecture.  A draft which was published last month 
required compliance with a standard in which there is a security issue.

Is there a possibility that all standards in the world specify the 
same suite?  That sounds unlikely.  However, I looked at standards 
from two countries [1] and I found that they were referencing the 
same standard.

>* there might be no single algorithm that is perfect for everybody

Yes.

Every algorithm does not have to be standardized [2].  That can be a 
mechanism which implementations can use for other algorithms.

Regards,
S. Moonesamy

1. I took a quick look and I found more than two countries.  As I did 
not read the documentation I cannot say that there are more than two countries.

2. What the IETF considers as a standard.

---

From: Yoav Nir <[email-masked]>
Date: Mon, 5 May 2014 13:29:50 +0300

On May 5, 2014, at 12:35 PM, S Moonesamy <[email-masked]> wrote:

>> It is a good idea to limit the number of possible permutations of allowed algorithms.
>> 
>> * compliance with standards (unless all standards in the world specify the same suite)
> 
> There is an international industry standards group working on a reference architecture.  A draft which was published last month required compliance with a standard in which there is a security issue.
> 
> Is there a possibility that all standards in the world specify the same suite?  That sounds unlikely.  However, I looked at standards from two countries [1] and I found that they were referencing the same standard.

You didn’t say which countries, but if your IPsec/TLS/SSH/SMIME is carrying personal information in Russia, it is required to use GOST.  In Japan you can use Camelia, but I don’t know if that would fulfil the legal requirements in Europe.

That’s the beauty of algorithm agility. The same implementation of these protocols can be used with all of these different algorithms.

So I think Andrey meant national standards as well as IETF, IEEE, or ISO standards.

Yoav

---

From: ianG <[email-masked]>
Date: Mon, 05 May 2014 12:12:55 +0100

> It is a good idea to limit the number of possible permutations of

:)

> * compliance with standards (unless all standards in the world specify

Why is this a pro?  What conceivable benefit is there to users in
adopting others' standards, when they already have their own?

We're talking about a single protocol that communicates with its own
agents only;  it's TLS versus SSH, they don't ever talk to each other,
it's not like Esperanto versus German.

Here you are in a standards setting, which means you set standards.  By
outsourcing the setting of standards, that means you are not doing the
job.  I can see the argument that you simply want to use other peoples'
work, but I can't see why you would want to save on work by re-use, and
duplicate with your own as well.  Makes no sense to me.

> * upgrade to new algorithms

Yes, just to set the context, there are three different mechanisms
available.  Algorithm agility is (to me) the substitution of new
algorithms within a protocol connection context.  There is also suite
substitution which sets the whole stack.  Then there is also version
upgrade which changes the whole protocol.  Latter is TLS1.1 => TLS1.2.

> (the time-line of the "old" and the "new"

(a result, not an objective)

> an old product that is only maintained as opposed to actively developed)

Only if you ignore all the other things going on.

> * there might be no single algorithm that is perfect for everybody

The combination of your points 1 & 4 means that every algorithm that has
any single benefit has to be supported by everyone, taken to the extreme.

Again, you have to look hard and deep:  why are you opening the door to
supporting more than one?  Why are you opening the door to many many
algorithms?  Where's the benefit for the user?

iang

---

From: S Moonesamy <[email-masked]>
Date: Mon, 05 May 2014 07:41:24 -0700

Hi Yoav,
At 03:29 05-05-2014, Yoav Nir wrote:
>You didn't say which countries, but if your IPsec/TLS/SSH/SMIME is 
>carrying personal information in Russia, it is required to use 
>GOST.  In Japan you can use Camelia, but I don't know if that would 
>fulfil the legal requirements in Europe.

I did not mention the name countries or the technology as my comments 
were probably off-topic. :-)

Camellia is in the recommended list for Japan since 2013.

>That's the beauty of algorithm agility. The same implementation of 
>these protocols can be used with all of these different algorithms.

I am not disagreeing with what you wrote.  It is worthwhile to 
consider whether there are any valid arguments against algorithm agility.

Yes.

Regards,
S. Moonesamy

---

From: Nico Williams <[email-masked]>
Date: Mon, 5 May 2014 10:15:05 -0500

> issue, maybe discussed later.

That's not what we generally mean by algorithm agility.
> hope, it's not met in practice.

That clarifies: you're against a-la carte negotiation.  (Actually, no,
you appear to be against algorithm agility in general.  See below.)

FYI, SSHv2 has a la carte negotiation of key exchange, host
authentication, and cipher+cipher mode (the last always as atomic
pairs) that since the beginning.  There's a case study for you.
Please demonstrate how it's been a problem.

> calls for 32 byte block sizes and a past of 8 bytes, (c) tendency for

"past"?

> debate, (e) the shift to AE, (f) changing keylength goals over time.

I agree that 3DES is NOT an appropriate substitute for AES, primarily
because 3DES has a very small block size (64 bits), which impacts on
re-keying considerations and authenticated encryption options.

I also agree that cipher and cipher mode MUST be negotiated as
registered pairs, not a la carte.  This is pretty clear, and I don't
know anyone who is arguing otherwise.

> new models cause contortions leading to weakness.

It sounds to me like the only thing you have an argument against is
negotiation of cipher separately from cipher mode.  But no one is
arguing for the other side of that.  It seems to me like you're just
putting up a strawman -- yes, it's easy to knock down!

> [...]

> together, and even one implementation negotiating against itself is no

Bunk.  Software negotiates on behalf of people.

> choose the weakest cipher.  Etc.

We know how to protect against downgrade attacks.  The biggest problem
w.r.t. downgrade attacks is fallback reconnection, a particularly
obnoxious problem for TLS for historical reasons.

> It also opens up the possibility for bugs (benign) and lousy user

This is not really an acceptable argument.  Everything we implement
opens up the possibility of bugs.  It's very difficult to win such an
argument (DJB does this very well when it comes to EC, for example, so
it can be done, but that's a very particular case and not at all
germane to this discussion).

> users choose key sizes?).

Nonsense.  The CBC IV chaining bugs were exploited against SSHv2.  We
were very glad back then to have deployed AES in counter mode as that
saved our butts.

> fail, *because we can*.  Not because it is likely.

I don't buy this.

> "Out of scope" means we aren't professionally doing risk analysis.

Algorithms most definitely have failed us, sometimes spectacularly!
E.g., MD5, CBC w/ IV chaining, RC4, ...

> [...]

> So the one time we really needed it ... it wasn't there for us?

It's very difficult to switch algorithms in PKIX.  I.e., we didn't
have algorithm agility for signature hashes.  You've refuted your own
argument.

> whether they'll get it right, or whether it'll trigger some other problems.

Configuration management is faster than patch application.  Way, way
faster.  In an emergency this is very handy.

> do it.  We talk about how we optimised our implementation to get 5%

Performance matters.  Bad perf -> risk of substantial non-deployment.

> GCM, because because, we enjoy poking our thumb at the NSA.

Huh?  GCM is a counter mode.  Just what the heck are you talking about??

> religion, exporting democracy, motherhood and apple pie?

What has this got to do with alg. agility?

Nico
--

---

From: Paul Lambert <[email-masked]>
Date: Mon, 5 May 2014 09:11:59 -0700

>These boxes are used for whatever purpose people want access to the
>plaintext for. Uses range from running so-called "next generation
>firewall²([1]) policy on them, to looking for dissidents in certain
>countries.
>
>Commercial CAs rarely give sub-root certificates, and when they do, they
>have  name constraints ([2]), so they can¹t be used for generating fake
>certificates for mail.google.com.

No, the intermediate certificates sometimes do not have constraints. There
is a medium sized country that issued unconstrained intermediate
certificates to all of their middle school districts.  Also, revocation
checking for intermediates is typically broken in implementations -
particularly for OCSP stapling.

Paul

>These boxes generally either generate their own self-signed CA, or get a
>corporate sub-CA. Either way, it requires clients to be configured with
>the interception CA.
>
>Yoav 
>
>[1] ³next generation firewall² is a marketing term, but in general
>classic firewall can block addresses, protocols and ports, whereas ³next
>generation² looks at higher layers as well. So a classic firewall can
>block your access to Facebook, a next-generation firewall can block your
>access to Farmville.
>_______________________________________________
>saag mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/saag

---

From: ianG <[email-masked]>
Date: Mon, 05 May 2014 18:26:52 +0100

> know anyone who is arguing otherwise.

Meet the draft:

https://datatracker.ietf.org/doc/draft-iab-crypto-alg-agility/?include_text=1

Especially 2.1:

   Some approaches carry one identifier for each algorithm that is used.
   Other approaches carry one identifier for a suite of algorithms.
   Either approach is acceptable; however, designers are encouraged to
   pick one of these approaches and use it consistently throughout the
   protocol.

Before we go further, can we just agree on what the above says, and what
the draft implies?

I think it says that "a la carte" is acceptable, to use your term.

...

> were very glad back then to have deployed AES in counter mode as that

Any reference to that?

iang

---

From: "Paterson, Kenny" <[email-masked]>
Date: Mon, 5 May 2014 17:32:41 +0000

>> were very glad back then to have deployed AES in counter mode as that

How about these:

http://www.kb.cert.org/vuls/id/958563

http://www.openssh.com/txt/cbc.adv

and

http://www.isg.rhul.ac.uk/~kp/SandPfinal.pdf

(for details of the attack).

Cheers,

Kenny

---

From: Nico Williams <[email-masked]>
Date: Mon, 5 May 2014 12:43:01 -0500

> Before we go further, can we just agree on what the above says, and what

Not really.  It's not clear that the quoted text means that cipher and
cipher mode can be negotiated separately.  I don't think anyone has
proposed such a thing in recent times (years).

> I think it says that "a la carte" is acceptable, to use your term.

As a term or as a concept?

>> were very glad back then to have deployed AES in counter mode as that

I don't have one handy.  I was at a vendor at the time and we had
already shipped AES in counter mode (with HMAC for authentication), so
it was easy for us to tell our customers what configuration changes
needed to be done to address the problem.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Mon, 5 May 2014 13:14:53 -0500

>    pick one of these approaches and use it consistently throughout the

The I-D is a bit barebones at this time -- that tends to be the case
with -00s...  It certainly needs to expand on the details of algorithm
negotiation quite a bit.  In particular it should say that one should
not design protocols to negotiate ciphers and cipher modes separately.
 Text on the pros/cons of a-la-carte vs. cartesian product negotiation
would be handy.

ISTR presentations to SAAG about algorithm agility that could be
leveraged here.  IIRC it was EKR who presented.

Nico

PS: There was no need to post that long screed.  It would have been
better to focus on the cipher-and-mode matter first, especially if you
don't object to a-la-carte negotiation in general.  Long rambling
rants can be a bit of a DoS on the community.  Try to keep it shorter.
 Edit, edit, edit until you have a concise post.

---

From: ianG <[email-masked]>
Date: Mon, 05 May 2014 19:57:38 +0100

>  Text on the pros/cons of a-la-carte vs. cartesian product negotiation

Right.  I suppose it could be read either way, and I read it the other way.

> leveraged here.  IIRC it was EKR who presented.

Hmmm, anyone have the refs?

>  Edit, edit, edit until you have a concise post.

I was briskly told to make the case, get to the back of the queue ;)

iang

---

From: ianG <[email-masked]>
Date: Mon, 05 May 2014 19:59:37 +0100

>>> were very glad back then to have deployed AES in counter mode as that

Thanks!  Excellent.  Was there any fallout, any actual attacks or damages?

> http://www.openssh.com/txt/cbc.adv

     "A future version of OpenSSH may make CTR mode ciphers the default
and/or implement other countermeasures, but at present we do not feel
that this issue is serious enough to make an emergency release."

On the face of those texts, this was a nice exploit of academic note,
but not a likely one, nor a practical one.  Something to be fixed, but
not something to inform our design choices in the future.

I'll let my point 7. stand unless there is some info about attacks and
damages.

(One question:  is Nico's claim that this is an example of "being saved"
more to do with commercial vendors' need to ship product with no
theoretical or known flaws?)

> (for details of the attack).

thanks again,

iang

---

From: Mouse <[email-masked]>
Date: Mon, 5 May 2014 15:23:38 -0400 (EDT)

> http://www.isg.rhul.ac.uk/~kp/SandPfinal.pdf

Fascinating.  Thank you; I'd somehow managed to not hear of that.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		[email-masked]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

---

From: Nico Williams <[email-masked]>
Date: Mon, 5 May 2014 14:25:40 -0500

> theoretical or known flaws?)

We considered the attack realistic in some environments, therefore we
felt we had to fix it.  Since we had shipped AES in counter mode, we
didn't have to hurry all that much, so in a sense we were "saved" some
negative consequences.

Nico
--