----- Original Message -----
From: "Pavel Kankovsky"
To: "Hubert Kario" <hkario(a)redhat.com>
Sent: Monday, 5 May, 2014 11:02:18 PM
Subject: Re: Fedora crypto policy vs the real world Was: available crypto policies
On Mon, 5 May 2014, Hubert Kario wrote:
> We can either provide false sense of security to users of those 1.7% of
> sites or provide much better security to users of nearly 18% of sites
> that also support other cipher suites.
IMHO, it is a situation similar to, say, the case when you get an expired
server certificate. The program should refuse to talk to such server by
default but it should explain the problem to the user and make it possible
to override the default policy (*).
Firefox does say that the communication is impossible because the server does
not support the same encryption algorithms as the client.
There is no option to override. The problem is that the server won't tell you
which ciphers it wants (it may be RC4, it may be single DES...). Firefox does
tell you that you should contact the web site owner and tell him about the problem.
> Also note that a service that connects to a site every minute
for a year
> will reach the needed threshold for the easiest attack that recovers
> 3 bytes with 100% accuracy.
You assume the client keeps sending the same secret data for a year.
Who changes passwords for an automated service on frequency higher than once
a year? It's set it and forget it (or are you trying to tell me that you and
all the people you know do change email passwords every 1-3 months?).
Also, perfect 100% accuracy (= zero probability of error) is
(see below) but you can get as close as you desire.
Oh, sure, there is a chance that the attacker will guess AES-128 encryption
key in first try. But I'd guess that the probability of that is not much lower
than the probability of random bit flip occurring during password checking
caused by cosmic radiation and letting you through even though you provided
On the other hand, breaking RC4 has probability closer to winning the National
Lottery than random bit flips. The former is likely, the latter unlikely.
> Now, unless someone has done the maths, I'm going to use
> estimate and assume a one to one ratio for memory-time trade off. That
> means that RC4 has 38 bit computational complexity of attack for a
> capture of just few connections. That's export grade crypto level.
I might have missed something here but I am afraid you are mistaken. As
far I know the attack--or its simple single-byte variant--works as
You are interested in some byte b of plaintext that its transmitted
repeatedly and you know it always corresponds to n-th byte of ciphertext.
You assume some prior probability distribution P(b = x) of possible
values of b.
You observe the interesting byte c of ciphertext and get the probability
distribution P(k_n = y) of the n-th byte of keystream, assuming a randomly
chosen keys. Compute the posterior prob. distribution P' for values of b
assuming ciphertext c by Bayesian inference.
The result would be the same as the original of P(b = x) if P(k_n = y)
were uniform. But it is biased and this makes some values of the unknown
plaintext byte b slightly more probable a posteriori than they were a
priori (at the expense of other values). Repeat (with priors replaced
by posteriors) with more ciphertexts until the probability of one value
grows large enough.
(AlFardan et al. describe a different and possibly somewhat more efficient
approach to find the maximum-likelihood choice of a plaintext byte.)
If you capture "just few" connections you do not collect enough
information to distinguish between the correct value and incorrect values,
and no amount of computing power will help you (that is unless you have
got enough to crack the cipher directly).
That's correct for attack that uses just single byte biases, there are
also double byte biases in RC4 output:
Like I said, the attacks assume random plaintext. While in reality, all
plaintexts have internal structure (the protocol used, be it HTTP, SMTP
or POP3). Coupled with double byte biases you are able to recover
unknown, but unchanging (like passwords or pre shared keys), bytes of
And in case of passwords, just information that a set of characters is
more likely at a given position is of huge advantage.
Quality Engineer, QE BaseOS Security team
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic