Conficker C and Ron Rivest
Timoleon
berserk on April 1st and cause havoc for potentially millions of
computer users/companies. According to a New York Times article, the
authors of the program have been using some "security code" recently
produced by Ron Rivest that enables them to fly under the radar without
being outed, although detected:
http://www.nytimes.com/2009/03/19/technology/19worm.html?_r=1
"The researchers, noting that the Conficker authors were using the most
advanced computer security techniques, said the original version of the
program contained a recent security feature developed by an M.I.T.
computer scientist, Ron Rivest, that had been made public only weeks
before. And when a revision was issued by Dr. Rivest’s group to correct
a flaw, the Conficker authors revised their program to add the correction."
My question is, what is the security feature that Rivest developed? And
is this the fruition of a cryptographic nightmare where the criminals
get to use all the heavy weapons against their creators?
Unruh
>Supposedly, the Conficker C malicious botnet program is going to go
>berserk on April 1st and cause havoc for potentially millions of
>computer users/companies. According to a New York Times article, the
>authors of the program have been using some "security code" recently
>produced by Ron Rivest that enables them to fly under the radar without
>being outed, although detected:
>http://www.nytimes.com/2009/03/19/technology/19worm.html?_r=1
>"The researchers, noting that the Conficker authors were using the most
>advanced computer security techniques, said the original version of the
>program contained a recent security feature developed by an M.I.T.
>computer scientist, Ron Rivest, that had been made public only weeks
>before. And when a revision was issued by Dr. Rivest’s group to correct
>a flaw, the Conficker authors revised their program to add the correction."
An cryptographic hash algorithm called MD6.
>My question is, what is the security feature that Rivest developed? And
>is this the fruition of a cryptographic nightmare where the criminals
>get to use all the heavy weapons against their creators?
Against their creators? Conficher is not being used against Rivest, it is
being used against the world, and yes, it is interesting because it is
using the latest crypto stuff.
Joseph Ashwood
news:Xiixl.1423$6%.728@nwrddc01.gnilink.net...
> According to a New York Times article,
Another article that shows why reporters should never write about security,
they couldn't have gotten much more wrong.
> the
> authors of the program have been using some "security code" recently
> produced by Ron Rivest that enables them to fly under the radar without
> being outed, although detected:
First, the recent one is MD6, just a hash function. The main encryption
appears to be RC4, and honestly, what moron still uses RC4 for something
new? Oh that's right, virus authors.
>
> http://www.nytimes.com/2009/03/19/technology/19worm.html?_r=1
>
> "The researchers, noting that the Conficker authors were using the most
> advanced computer security techniques,
It is important to note that no reputable researcher exists that would
actually say this.
> said the original version of the
> program contained a recent security feature developed by an M.I.T.
> computer scientist, Ron Rivest, that had been made public only weeks
> before.
Several problems with that statement. First it isn't a security feature.
Second it wasn't developed by Rivest, it was developed by a team lead by
Rivest. Third, the process of making it public began months before Conficker
was released (Crutchfield's Thesis June 2008).
> And when a revision was issued by Dr. Rivest’s group to correct
> a flaw, the Conficker authors revised their program to add the
> correction."
At least that much seems to be correct.
> My question is, what is the security feature that Rivest developed?
MD6, not a feature, its a hash algorithm.
> And
> is this the fruition of a cryptographic nightmare where the criminals
> get to use all the heavy weapons against their creators?
Not in any way. It has always been the case in security that the criminals
have access to the state of the art, this applies whether you are talking
about flint knives, lockpicks, or cryptography. Is this a cryptographic
nightmare? No, this is a failure of a company (in this case Microsoft, but
it could be anyone) to secure their software against known vulnerabilities.
It is just that in this case the exploit authors have made use of the exact
technology they should have and the same technology that has been available
in various forms for at least a decade.
As is typical in these cases, blame is placed on anyone other than who it
should be. There have been countless times just in the last few years where
something was "stolen" by the bad guys (pick your bad guys, I can find the
blame) and it turns out that it was entirely different.
This is largely equivalent to blaming Masterlock for making weak locks when
someone tows your car, after all it not only wasn't a failure of the lock,
the lock on your car isn't made by Masterlock either.
Joe
rossum
wrote:
>My question is, what is the security feature that Rivest developed?
A team led by Rivest developed a new hash function, MD6, as an entry
for the SHA-3 competition. See http://ehash.iaik.tugraz.at/wiki/MD6
rossum
mike clark
> "Timoleon" <timoleon...@gmail.com> wrote in message
Why not use RC4? It isn't broken? SSL connections use it quite often
and it is much easier to code than AES. Unless there is something I am
missing, I don't see why using RC4 something new.
Dave -Turner
news:245d62a0-d09a-4235...@p6g2000pre.googlegroups.com...
> and it is much easier to code than AES.
but we're talking security, not ease-of-coding.
mike clark
> "mike clark" <m...@netadv.net> wrote in message
>
> news:245d62a0-d09a-4235...@p6g2000pre.googlegroups.com...
>
> > and it is much easier to code than AES.
>
> but we're talking security, not ease-of-coding.
So RC4 is less secure than AES? Sorry if this is just common
knowledge, I am fairly new to crypto. Where can I read up on RC4
weaknesses?
amzoti
Have you ever read the book "Malicious Cryptography: Exposing
Cryptovirology" by Adam Young and Moti Yung?
The whole subject is rather scary - but it is a very interesting
philosophical dilemma.
Use your strengths against you - wow, what a concept.
rossum
wrote:
>On Mar 22, 11:11 am, "Dave -Turner" <ad...@127.0.0.1> wrote:
>> "mike clark" <m...@netadv.net> wrote in message
>>
>> news:245d62a0-d09a-4235...@p6g2000pre.googlegroups.com...
>>
>> > and it is much easier to code than AES.
>>
>> but we're talking security, not ease-of-coding.
>
>So RC4 is less secure than AES?
Yes.
>Sorry if this is just common
>knowledge, I am fairly new to crypto. Where can I read up on RC4
>weaknesses?
The Wikipedia covers RC4 reasonably well and gives a list and
references for the known weaknesses. See
http://en.wikipedia.org/wiki/RC4
For more modern stream cyphers see the eSTREAM project:
http://www.ecrypt.eu.org/stream/
rossum
Unruh
AFAIK
There are a couple. RC4's first N bytes ( where N is some number like 100)
are decidedly not "random" But all good versions throw away the first 256
bytes.
RC4 has some very slight, but detectable ( after a few GB of output) biases
in the output stream. This is a theoretical weakness. I do not think that
anyone has come up with any way of using this (well, I guess if you sent a
a file with 10GB of the letter a and the attacker wants to differentiate it
from a file with 10GB of the letter b this weakness could be used.
Ie, the file you are encrypting would require massive redundancy for this
weakness to be important. But it is a weakness.) In contrast is its speed
size and ease of encoding.
Note that ease of coding IS part of security. The harder to encode, the
greater the probablility of subtle bugs.
Is RC4 more or less secure than AES? I doubt that any reputable
cryptographer would make a pronouncement.
Paul Rubin
> Why not use RC4? It isn't broken? SSL connections use it quite often
> and it is much easier to code than AES. Unless there is something I am
> missing, I don't see why using RC4 something new.
RC4 has what are called certificational weaknesses, that were
discovered after it was already widely deployed in SSL. Basically
there are known ways to distinguish an RC4 keystream from a random
stream, the usual security criterion for a stream cipher.
The weaknesses don't give rise to immediate exploits (i.e. plaintext
recovery) that anyone has (at least publicly) figured out yet, so
there hasn't been a huge rush to change all those already-deployed SSL
implementations. but for new applications, cryptographers generally
prefer to use primitives (like AES) that haven't shown such
weaknesses.
m...@privacy.net
Joseph Ashwood wrote:
>this is a failure of a company (in this case Microsoft, but
>it could be anyone) to secure their software against known
>vulnerabilities.
It *could* be anyone, but for some reason it is almost always
good old "Windows has no bugs" Microsoft.
http://www.cantrip.org/nobugs.html
http://catless.ncl.ac.uk/Risks/17.43.html#subj5
http://www.staff.uni-mainz.de/pommeren/DSVorlesung/Material/GatesInterview
Antony Clements
<m...@privacy.net> wrote in message
news:1_2dnYIQMZB...@giganews.com...
> It *could* be anyone, but for some reason it is almost always
> good old "Windows has no bugs" Microsoft.
I'll remake a statement since Mr Macon disproved my other one... It is
virtually impossible for any program to be code perfect, the larger the code
base the more likely there will be bugs, if the coder is competent, and
there are no deliberate bugs by design, they will be bugs by oversight. The
same applies for systems (computer systems, manufacturing plants etc etc).
The larger the system the more likely there will be one or many things that
will cause it to collapse in on itself.
Greg Rose
Unruh <unruh...@physics.ubc.ca> wrote:
>Is RC4 more or less secure than AES? I doubt that any reputable
>cryptographer would make a pronouncement.
I don't know if I count as reputable, but I would
certainly make the pronouncement that RC4 is
currently thought to be much weaker than AES. RC4
has distinguishers at about 2^32 bytes of output,
whereas AES has no known weaknesses worse than
generic attacks.
Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au
Unruh
>In article <tGvxl.19085$PH1.296@edtnps82>,
>Unruh <unruh...@physics.ubc.ca> wrote:
>>Is RC4 more or less secure than AES? I doubt that any reputable
>>cryptographer would make a pronouncement.
>I don't know if I count as reputable, but I would
>certainly make the pronouncement that RC4 is
>currently thought to be much weaker than AES. RC4
>has distinguishers at about 2^32 bytes of output,
>whereas AES has no known weaknesses worse than
>generic attacks.
Much weaker? On what basis?
Distingushers do not imply attacks. They may make you worry. AES has
complexity and slow speed, which means it will not be used when it should
be, and thus the security is be 0. Security is NOT just a matter of
technical features, but the whole security apparatus, including the user.
Now you are still going to say that RC4 is less secure than AES?
Your comments sound like "That ford has a chip in the paint while that
chevy does not, and thus the chevy is a better car."
Paul Rubin
> Distingushers do not imply attacks.
If the security criterion is that there are no distinguishers, then
any distinguisher IS an attack and doesn't just imply one.
If you look at any current research on stream ciphers (e.g. the
eSTREAM process), they are always aiming for the absence of
distinguishers.
> They may make you worry.
If a cipher is designed to have no distinguishers, and then
distinguishers are found, that's a concrete demonstration that
the design process has failed, and not a mere "worry".
It is simply not accepted practice in cryptography to assume that
something is secure until the presence of an exploit is shown. We are
seeking the absence of exploits, not a mere lack of proof of their
presence. Mathematically proving the absence of exploits appears
beyond our capability at the moment (that would require showing P!=NP
among other things), so we are stuck (for now) relying on
observational evidence.
The best observational evidence we can give for a crypto primitive
being secure is the failure of concerted effort to discover
distinguishers. Therefore, if a distinguisher is known, we can no
longer say that it presents the best observational evidence of
security. That is a reason not to deploy it.
> AES has complexity and slow speed, which means it will not be used
> when it should be, and thus the security is be 0.
If you're thinking of (say) tiny embedded systems, RC4 is worse in
most of them than AES, because of its higher RAM requirements.
If you're thinking of more typical dektop and server computers of the
type likely to run protocols like SSL, AES is fine in almost every
application where RC4 would be ok. There are occasional exceptions
but they are uncommon.
If you're thinking of systems where very high performance is needed,
AES wins again, because of the easier implementation and wide
availability of AES hardware implementations compared with RC4.
> Your comments sound like "That ford has a chip in the paint while that
> chevy does not, and thus the chevy is a better car."
It's more like the Space Shuttle, which was in danger of explosion if
a certain O-ring in the solid rocket booster burned all the way
through. Numerous launches showed that it sometimes burned up to 30%
of the way through, and this was described as a 3-to-1 safety margin
even though the O-ring was designed to not burn at all. The result
was that they kept flying the design until Challenger exploded.
Joseph Ashwood
news:tGvxl.19085$PH1.296@edtnps82...
> Is RC4 more or less secure than AES? I doubt that any reputable
> cryptographer would make a pronouncement.
You can define reputable however you want, I have consistently commented on
this for several years. I have repeatedly stated that RC4 should have been
retired over a decade ago. I always recommend removing RC4 as an option for
TLS. WEP is broken in part because RC4 is weak. SSL2 had weaknesses with the
use of RC4. The list is quite substantial.
RC4 is weak and should never be used in any design. AES is currently strong.
So yes, RC4 is less secure than AES.
Joe
Guy Macon
I agree 100%. The apparant exceptions are the telephone switching
network, the air traffic control network and the Internet, but on
close examinations it turns out that the telephone switching network
is really a few small systems repeated many many times, the air
traffic control network breaks down all the time and the humans go
to manual control, and the Internet requires a huge effort to keep
it updated as attackers discover new weaknesses.
--
Guy Macon
<http://www.GuyMacon.com/>
Paul Rubin
> The apparant exceptions are the telephone switching network, the air
> traffic control network and the Internet, but on close examinations
> it turns out that the telephone switching network is really a few
> small systems repeated many many times, the air traffic control
> network breaks down all the time and the humans go to manual
> control, and the Internet requires a huge effort to keep it updated
> as attackers discover new weaknesses.
I would say that the air traffic network and the phone network are
designed on the (sometimes incorrect) theory that attackers don't have
access at all, and their security efforts are aimed at keeping
attackers away from the system, rather than being robust against the
activities of attackers who have access. The Internet has a much
bigger attack surface, and as such, quite a bit more effort goes into
securing it than those other networks.
Antony Clements
"Guy Macon" <http://www.GuyMacon.com/> wrote in message
news:gvqdncxOJMx...@giganews.com...
> I agree 100%. The apparant exceptions are the telephone switching
> network, the air traffic control network and the Internet, but on
> close examinations it turns out that the telephone switching network
> is really a few small systems repeated many many times, the air
> traffic control network breaks down all the time and the humans go
> to manual control, and the Internet requires a huge effort to keep
> it updated as attackers discover new weaknesses.
The internet is a very 'apparent' case because, in it's current state it is
broken in many fundamental ways, and i'm not referring to the lack of
network security either. For example, a data packet goes from point A to
point B, everyone knows that. But what the layman doesn't know, is that data
packets can get bogged down, or lost entirely. Even things like emails can
get lost, I myself have waited for hours or even days to recieve an email,
or just plain not recieved it at all. Admittedly lost emails can also
because of server issues, but not always.
There are a number of "internet black holes" that have been mapped as well
(do a google there is a map), for me to consider the internet even partially
unbroken in this respect, there must be some protocol in place for example
that detects the load of any given node, and if it is past a certain point,
to redirect the packet to a different node, similar to how gravity bends and
redirects light, I expect such a thing would be hardware based. Also, within
this protocol there would be provisions that reflects a packet that is
forbidden by a particular node, by that I mean a data packet arrives at a
node, there is some inspection of the packet, and the node either lets the
packet continue on it's path through the network of that particular node, or
it passes it to the next, without ever entering the network of said node.
Having something like this would allow places like China, to no longer act
as a black hole, but as a mirror instead.
I do believe that SPI features of many firewalls already do half of the job,
namely inspecting a packet and deciding if it is allowed to continue to its
destination.
Guy Macon
Antony Clements wrote:
>
>Guy Macon <http://www.GuyMacon.com/> wrote...
Excellent observation/comments. What I find interesting is that this huge
unmanaged network with so many different programs (and humans!) on it all
talking to each other still manages to avoid that "the larger the system
the more likely there will be one or many things that will cause it to
collapse in on itself." fate you described earlier. A lot of things go
wrong, but it mostly works and never collapses in on itself. Many good
engineers put in a lot of ongoing work making that true.
Unruh
>Unruh <unruh...@physics.ubc.ca> writes:
>> Distingushers do not imply attacks.
>If the security criterion is that there are no distinguishers, then
>any distinguisher IS an attack and doesn't just imply one.
Yes, if oranges are defined as yellow, then oranges are yellow.
An attack is the ability to get cleartext from encrypted text without
knowing the key.
>If you look at any current research on stream ciphers (e.g. the
>eSTREAM process), they are always aiming for the absence of
>distinguishers.
Of course. It would be stupid not to do so. It is an easy criterion and
makes a easily measured target to aim for. "Cannot decrypt" is a hard
target.
>> They may make you worry.
>
>If a cipher is designed to have no distinguishers, and then
>distinguishers are found, that's a concrete demonstration that
>the design process has failed, and not a mere "worry".
We are talking about a system to protect communications. That is the
purpose. "No distinguishers" is a means to an end.
>It is simply not accepted practice in cryptography to assume that
>something is secure until the presence of an exploit is shown. We are
>seeking the absence of exploits, not a mere lack of proof of their
>presence. Mathematically proving the absence of exploits appears
>beyond our capability at the moment (that would require showing P!=NP
>among other things), so we are stuck (for now) relying on
>observational evidence.
>The best observational evidence we can give for a crypto primitive
>being secure is the failure of concerted effort to discover
>distinguishers. Therefore, if a distinguisher is known, we can no
>longer say that it presents the best observational evidence of
>security. That is a reason not to deploy it.
All crypto systems have distinguishers. I know with aes that there are only
2^128 different keys. Ie, within 16 bytes of known plaintext I know I can
find the unique key ( well, maybe 20 bytes just to be safe). And I know
with mathematical certainty that 20 bytes will allow me to decrypt the
message, no matter how long it is. But that does
not mean that AES is useless.
If you are going to argue that RC4 having a distinguisher makes it
insecure, you need to have a plausible attack that that could at least
hypotentically help you with. Of course if asked to choose between one that
has some distinguisher and one that does not, and with no other criteria to
make a decision on, I would also choose the one that does not. Does that
mean that it is more secure or stronger? No. Just that if forced to choose
I might as well choose on that criterion.
>> AES has complexity and slow speed, which means it will not be used
>> when it should be, and thus the security is be 0.
>If you're thinking of (say) tiny embedded systems, RC4 is worse in
>most of them than AES, because of its higher RAM requirements.
>If you're thinking of more typical dektop and server computers of the
>type likely to run protocols like SSL, AES is fine in almost every
>application where RC4 would be ok. There are occasional exceptions
>but they are uncommon.
>If you're thinking of systems where very high performance is needed,
>AES wins again, because of the easier implementation and wide
>availability of AES hardware implementations compared with RC4.
>> Your comments sound like "That ford has a chip in the paint while that
>> chevy does not, and thus the chevy is a better car."
>It's more like the Space Shuttle, which was in danger of explosion if
>a certain O-ring in the solid rocket booster burned all the way
>through. Numerous launches showed that it sometimes burned up to 30%
>of the way through, and this was described as a 3-to-1 safety margin
>even though the O-ring was designed to not burn at all. The result
>was that they kept flying the design until Challenger exploded.
If I thought that the bias in RC4 were a 3-1 safety margin, I would
certainly advise everyone not to use it as would you. It is more like a
10^10 to 1. If you can give me some plausible scenario where the
distinguishability from random in output biases at the level RC4 has them
can be used to read the plaintext of an English text, then certainly get
rid of it. But your arguments sound like the arguements in the man pages of
urandom which have caused thousands to not use it, and use /dev/random
instead and screw up their systems.
Guy Macon
Unruh wrote:
>If I thought that the bias in RC4 were a 3-1 safety margin, I would
>certainly advise everyone not to use it as would you. It is more like a
>10^10 to 1. If you can give me some plausible scenario where the
>distinguishability from random in output biases at the level RC4 has them
>can be used to read the plaintext of an English text, then certainly get
>rid of it. But your arguments sound like the arguements in the man pages of
>urandom which have caused thousands to not use it, and use /dev/random
>instead and screw up their systems.
There is another aspect to consider. Consider two algorithms:
Algorithm A was invented last week and has only been examined
tested by the author and a couple of other people, none well-known.
They all say they found no flaw.
Algorithm B was invented by a well known crypto expert and has been
tested and reviewed again and again by some of the best minds in the
crypto community for many years, all of which have only found the
sort of theoretical weaknesses that has been found in RC4 -- none of
which allows an attacker to decrypt an encrypted message.
Which would you choose? The one with no known flaw or the one with
the known flaw?
AES has been tested and examined by some very fine minds, but many
of the same fine minds looked at RC4 for a long time without finding
some of the weaknesses that we now know about. The same argument
works the other way as well; a new attack that completely breaks RC4
or AES may be developed next year, and it could be argued that the
person trying to break RC4 has a better head start because of all the
published research done so far.
And of course, none of these potential future problems are anywhere
near as likely as the likelyhood of some other part of your total
security system having a flaw. Worrying about the actual algorithm
is like having a case-hardened deadbolt on a cardboard box and
worrying about whether the lock is sufficiently resistant to a
carbide drill.
Paul Rubin
> An attack is the ability to get cleartext from encrypted text without
> knowing the key.
Excuse me, but I don't think you get to decide what someone else
considers to be an attack. The crypto research community seems to
universally consider distinguishers to be attacks, which is good
enough for me.
> All crypto systems have distinguishers. I know with aes that there
> are only 2^128 different keys.
We are talking about computationally feasible distinguishers, or
anyway distinguishers with lower complexity than exhaustion of the key
space (that would be considered certificational). RC4 has them.
None have been found for AES as far as I know.
> If you are going to argue that RC4 having a distinguisher makes it
> insecure, you need to have a plausible attack that that could at least
> hypotentically help you with.
1. I follow the criterion I see currently used in the crypto research
community, which is that "secure" means "no distinguisher". So if
there is a distinguisher, it is insecure by definition. RC4 already
has known distinguishers. I realize that you can make up your own
crypto criteria to substitute for the accepted ones, just like I can
make up my own physics, but neither is interesting.
2. I don't need plausible attacks (even plausible distinguishers) to
argue that something is insecure (or at least that it should be
treated as insecure). No matter what definition of security you use,
any crypto primitive should be PRESUMED insecure until, ideally, there
is a mathematical proof that it is secure. Unfortunately nobody has
been able to produce such proofs, yet we still want to deploy crypto
in practice, so we have to settle for a lesser standard of evidence,
which is that the cipher (while lacking a proof) satisfies the
strongest possible tests that we can think of. That means: no
distinguishers (regardless of the actual security goal). RC4 fails.
3. There are certainly applications (SSL is generally not one of them)
where a distinguisher is a security failure. If an attacker can
tell that a captured hard drive is full of ciphertext rather
than full of random data, I'm sure you can see how that might be
a problem for someone.
4. RC4's problems go beyond distinguishers--see for example Mantin's
masters' thesis which had a pretty good roundup of RC4 cryptanalysis.
Paul Rubin
> your arguments sound like the arguements in the man pages of
> urandom which have caused thousands to not use it, and use /dev/random
> instead and screw up their systems.
That isn't similar at all. There was not a body of academic crypto
literature rejecting urandom and using /dev/random. The academic
crypto literature does, however, for the most part treat the presence
or absence of distinguishers as THE security criterion for ciphers.
In both cases, amateurs may have had opinions that differ from what
the researchers do, but so what? I'd consider the researchers'
approaches to be more reliable than the amateurs in either situation.
Phil Carmody
> g...@nope.ucsd.edu (Greg Rose) writes:
>
>>In article <tGvxl.19085$PH1.296@edtnps82>,
>>Unruh <unruh...@physics.ubc.ca> wrote:
>>>Is RC4 more or less secure than AES? I doubt that any reputable
>>>cryptographer would make a pronouncement.
>
>>I don't know if I count as reputable, but I would
>>certainly make the pronouncement that RC4 is
>>currently thought to be much weaker than AES. RC4
>>has distinguishers at about 2^32 bytes of output,
>>whereas AES has no known weaknesses worse than
>>generic attacks.
>
> Much weaker? On what basis?
> Distingushers do not imply attacks. They may make you worry. AES has
> complexity and slow speed, which means it will not be used when it should
> be, and thus the security is be 0. Security is NOT just a matter of
> technical features, but the whole security apparatus, including the user.
> Now you are still going to say that RC4 is less secure than AES?
> Your comments sound like "That ford has a chip in the paint while that
> chevy does not, and thus the chevy is a better car."
Wouldn't "That ford needs refuelling every 2^32 thous, whereas the
chevy needs refuelling every 2^64 thous" be more useful as an analogy?
Phil
--
Marijuana is indeed a dangerous drug.
It causes governments to wage war against their own people.
-- Dave Seaman (sci.math, 19 Mar 2009)
Phil Carmody
>> An attack is the ability to get cleartext from encrypted text without
>> knowing the key.
>
> Excuse me, but I don't think you get to decide what someone else
> considers to be an attack. The crypto research community seems to
> universally consider distinguishers to be attacks, which is good
> enough for me.
In the context of traffic analysis, it clearly is an attack, surely?
It's not the values of the bits, it's the existence of the bits.
Greg Rose
Unruh <unruh...@physics.ubc.ca> wrote:
>g...@nope.ucsd.edu (Greg Rose) writes:
>
>>In article <tGvxl.19085$PH1.296@edtnps82>,
>>Unruh <unruh...@physics.ubc.ca> wrote:
>>>Is RC4 more or less secure than AES? I doubt that any reputable
>>>cryptographer would make a pronouncement.
>
>>I don't know if I count as reputable, but I would
>>certainly make the pronouncement that RC4 is
>>currently thought to be much weaker than AES. RC4
>>has distinguishers at about 2^32 bytes of output,
>>whereas AES has no known weaknesses worse than
>>generic attacks.
>
>Much weaker? On what basis?
Here's a basis, since you don't like the
distinguishing attack: it is a weakness in RC4
that allows an attacker to decrypt traffic and
recover the key in WEP. WEP's design was bad, and
it had other problems, but if AES had been used
instead of RC4, the traffic would have still been
encrypted and the key would not have been
revealed.
The reason I tend to mention the distinguisher
first is that it is absolutely inherent in RC4,
and can't be worked around. Whereas you can always
say things like "hash the nonce and the key before
keying RC4, then drop a couple of hundred bytes,
oh and redesign WEP while you are at it", and RC4
isn't the problem any more.
WTShaw
It is a better idea to learn to appreciate the forrest and the trees,
not one or the other.
Antony Clements
> Excellent observation/comments. What I find interesting is that this huge
> unmanaged network with so many different programs (and humans!) on it all
> talking to each other still manages to avoid that "the larger the system
> the more likely there will be one or many things that will cause it to
> collapse in on itself." fate you described earlier. A lot of things go
> wrong, but it mostly works and never collapses in on itself. Many good
> engineers put in a lot of ongoing work making that true.
There have been many doomsday scenario's proclaiming the end of the
Internet, but that is not the end of everything, only the end of the
internet as it is today. Many times it has come close to the bring of
collapse where it would need to be rebuild and securely amongst other
things. It is ONLY the continual upgrades and patches to the code base that
keeps it alive as it is now and prevents it's inevitable collapse. But the
researchers can only do so much before a scenario of diminishing returns
kicks in. At which point the researchers will have absolutely no choice but
to phase out what currently is, while phasing in the new and improved
Internet, in a sense that is happening already, with Web 2.0 and Web 3.0
(although many of the Web 2.0 and 3.0 "features" are merely work arounds of
Web 1.0). But there does come a point where no amount of upgrades to the
code base will fix the underlying problems.
Creating a "work around" of a bug does not squish the bug, it merely makes
it less likely to occur. In any case it's still an accident waiting to
happen. As a coder yourself, I expect you have been faced with similar
scenarios where the code base needs to be tossed aside and re-written either
in part or in it's entirety.
Thomas Pornin
> But your arguments sound like the arguements in the man pages of
> urandom which have caused thousands to not use it, and use /dev/random
> instead and screw up their systems.
That's the other way round, actually. The requirement of not having
distinguishers is so that the encryption primitive can be safely used in
a variety of contexts, not only the limited basic encryption setup with
a passive eavesdropper. In particular, when implementing a PRNG such as
/dev/urandom, a distinguisher contradicts the very property of
non-predictibility that you expect from a good PRNG. You would not want
to use RC4 for that.
Having a distinguisher does not mean that you automatically have an easy
attack in a particular setup. But if you are the defender, that is not
the proper way to think. Requesting an easy attack is how the attacker
thinks. The defender wants to be sure that there is no possible attack,
either easy or uneasy. Conversely, in most contexts, any attack can be
turned (easily !) into a distinguisher. Thus, if there is no
distinguisher there is no attack. And that is the kind of property that
the defender seeks.
Hence it is customary to consider distinguishers as weaknesses of the
primitive. Cryptographers have done that for a few decades and they are
quite happy with it.
--Thomas Pornin
Unruh
>Unruh <unruh...@physics.ubc.ca> writes:
>> An attack is the ability to get cleartext from encrypted text without
>> knowing the key.
>Excuse me, but I don't think you get to decide what someone else
>considers to be an attack. The crypto research community seems to
>universally consider distinguishers to be attacks, which is good
>enough for me.
Of course I do not, I am defining attack in the above. You might consider
an attack to be that the name of the crypto system contains fewer than 5
letters, and I cannot stop you. I do however dispute your contention that
that "distinguishers" are universally considered attacks.
>> All crypto systems have distinguishers. I know with aes that there
>> are only 2^128 different keys.
>We are talking about computationally feasible distinguishers, or
Exactly what is "computationally feasible"? You start off by saying
distinguishers are attacks and now you backpedal and say "computationally
feasible distinguishers."
>anyway distinguishers with lower complexity than exhaustion of the key
>space (that would be considered certificational). RC4 has them.
>None have been found for AES as far as I know.
>> If you are going to argue that RC4 having a distinguisher makes it
>> insecure, you need to have a plausible attack that that could at least
>> hypotentically help you with.
>1. I follow the criterion I see currently used in the crypto research
>community, which is that "secure" means "no distinguisher". So if
Uh, no, it does not. AES with a 20 bit key space has no distinguishers and
is NOT secure. "distinguisher" is a very weak proxy for secure.
>there is a distinguisher, it is insecure by definition. RC4 already
>has known distinguishers. I realize that you can make up your own
>crypto criteria to substitute for the accepted ones, just like I can
>make up my own physics, but neither is interesting.
>2. I don't need plausible attacks (even plausible distinguishers) to
>argue that something is insecure (or at least that it should be
>treated as insecure). No matter what definition of security you use,
>any crypto primitive should be PRESUMED insecure until, ideally, there
All right, you have just eliminited "secure" as a useful word, and stated
that everything is insecure. Thus as far as security is concerned
everything is equivalent-- ie insecure.
>is a mathematical proof that it is secure. Unfortunately nobody has
>been able to produce such proofs, yet we still want to deploy crypto
>in practice, so we have to settle for a lesser standard of evidence,
>which is that the cipher (while lacking a proof) satisfies the
>strongest possible tests that we can think of. That means: no
>distinguishers (regardless of the actual security goal). RC4 fails.
>3. There are certainly applications (SSL is generally not one of them)
>where a distinguisher is a security failure. If an attacker can
>tell that a captured hard drive is full of ciphertext rather
>than full of random data, I'm sure you can see how that might be
>a problem for someone.
No, an attacker KNOWS the disk is full of non-random data. That is why he
is interested in it.
>4. RC4's problems go beyond distinguishers--see for example Mantin's
>masters' thesis which had a pretty good roundup of RC4 cryptanalysis.
OK, could you list some of them? Or give a link? I am not able to search for some unkown
person's master's thesis at an unknown university to read it.
Stefan Tillich
> Paul Rubin <http://phr...@NOSPAM.invalid> writes:
>
[...]
>
>
>> 4. RC4's problems go beyond distinguishers--see for example Mantin's
>> masters' thesis which had a pretty good roundup of RC4 cryptanalysis.
>
> OK, could you list some of them? Or give a link? I am not able to search for some unkown
> person's master's thesis at an unknown university to read it.
Well it took me about 10 seconds to locate it with Google (entered
search term: Mantin master thesis):
http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Mantin1.zip
Maybe you should at least try before complaining.
Stefan
>
>
Kristian Gjųsteen
>I cannot stop you. I do however dispute your contention that
>that "distinguishers" are universally considered attacks.
You are wrong. Distinguishing attacks are considered valid attacks.
--
Kristian Gjųsteen
Unruh
>According to Unruh <unruh...@physics.ubc.ca>:
>> But your arguments sound like the arguements in the man pages of
>> urandom which have caused thousands to not use it, and use /dev/random
>> instead and screw up their systems.
>That's the other way round, actually. The requirement of not having
>distinguishers is so that the encryption primitive can be safely used in
>a variety of contexts, not only the limited basic encryption setup with
>a passive eavesdropper. In particular, when implementing a PRNG such as
>/dev/urandom, a distinguisher contradicts the very property of
>non-predictibility that you expect from a good PRNG. You would not want
>to use RC4 for that.
Agreed, although lots of people use /dev/rand for their PRNG, and are
happy.
>Having a distinguisher does not mean that you automatically have an easy
>attack in a particular setup. But if you are the defender, that is not
>the proper way to think. Requesting an easy attack is how the attacker
>thinks. The defender wants to be sure that there is no possible attack,
>either easy or uneasy. Conversely, in most contexts, any attack can be
>turned (easily !) into a distinguisher. Thus, if there is no
>distinguisher there is no attack. And that is the kind of property that
>the defender seeks.
You KNOW there there is a distinguisher for any cypher (otehr than one time
pad). There are only a finite number of keys, and they distingush one
stream from the other. Thus is it not the existence of the distinguisher
that is important but the ease of using it to decrypt the message. The key
as a distinguisher is "OK" because it is computationally very expensive to
use it to decrypt the message. The argument I would like to see is that the
RC4 distinguisher is easier to use than than the key to decrypt the
message.
Now as I mentioned in my orignal claim, it can be used if there is enough
redundancy in the message ( eg it can be used to distinguish a message of
10^30 copies of the letter a from 10^30 copies of the letter b). But that
is not the "typical" message. Thus, given a message with say 1 bit of
entropy per byte of message, how can the distinguisher in RC4 be used to
decrypt the message?
That is what most people mean by the security of the crypto system. Now if
you define "distinguisher" as "security", then anything with a
distinguisher is insecure. I agree. But grant me my definition of security,
which is what I suspect the OP was using in his question.
Unruh
>[...]
Thank you for the pointer.
And from section 8.2 Discussion
"
Our main positive conclusion about the security of RC4 is that using RC4 in
this way [discarding the first 256 bytes] seems to be secure, even when
using a concatenation-based session-key derivation: We believe that no
information leaks about either the key or any part of the encrypted
messages.
"
Mind you that was written in 2001.
Thomas Pornin
> You KNOW there there is a distinguisher for any cypher (otehr than one
> time pad).
No, I am using the usual definition for distinguishers, which is
computationaly bounded. I give a maximum amount of computational power
to the attacker and I consider only distinguishers (or any kind of
attack) which fits in that allowance. To be more precise, I give 2^100
bits of fast-access RAM and 2^100 elementary operations to the attacker,
and consider an attack as valid only if it comes to a conclusion with
better success rate than one in a million (equivalently, I give 2^120
elementary operations worht of CPU and expect a 50% success rate from
the attacker).
When attackers are computationaly unbounded, then they may break through
a great many things, including any kind of RC4 and AES, and most of the
discussion is moot. Arguably, when you give infinite computational
abilities to the attacker (i.e. God is your enemy), then applicability
of whatever results you may find is the first thing to go down the
drain.
> Thus, given a message with say 1 bit of entropy per byte of message,
> how can the distinguisher in RC4 be used to decrypt the message?
That's an attacker question. The attacker is concerned with how to
transform a weakness into a break which ultimately siphons money. The
defender, however, wants to be sure that no attack occurs. Rather than
having a description in plain details of how a specific attack may run,
the defender prefers having a rational explanation of why a wide range
of attacks are not feasible.
Requiring that no distinguisher exists (computationaly bounded
distinguishers, if you are fuzzy on the usual definitions in the area)
does the defender trick. Such a lack of a distinguisher implies that
there may be no successful decryption attack, since a decryption attack
provides a distinguisher. Answering your question above, then, is never
needed. If a cryptosystem allows the existence of distinguishers,
then it is not good enough, and thus discarded.
--Thomas Pornin
Unruh
>> Thus, given a message with say 1 bit of entropy per byte of message,
>> how can the distinguisher in RC4 be used to decrypt the message?
>That's an attacker question. The attacker is concerned with how to
>transform a weakness into a break which ultimately siphons money. The
>defender, however, wants to be sure that no attack occurs. Rather than
No, the defender is concerned with the same thing-- that no money gets
siphoned, to use your metaphore.
>having a description in plain details of how a specific attack may run,
>the defender prefers having a rational explanation of why a wide range
>of attacks are not feasible.
That is of course nice, but noone can give it to him. In this case you have
a concept, distinguisher, but no attack that is being ruled out.
It is of course clear that if the distiguisher is bad enough, then an
attack becomes possible, but with what RC4 has it would be nice if some
attack were actually demonstrated. Otherwise it would seem that immense
effort and time are spent on defending against imaginary foes, while real
foes could be overlooked.
>Requiring that no distinguisher exists (computationaly bounded
>distinguishers, if you are fuzzy on the usual definitions in the area)
>does the defender trick. Such a lack of a distinguisher implies that
>there may be no successful decryption attack, since a decryption attack
>provides a distinguisher. Answering your question above, then, is never
The logic is wrong. Just because an attack provides a distiguisher does
not mean that a distinguisher provides an attack. It is an elementary error
in logic. There may be perfectly benign distiguishers, and deadly ones, as
far as decryption is concerned.
>needed. If a cryptosystem allows the existence of distinguishers,
>then it is not good enough, and thus discarded.
That may be your operational procedure. It may also be completely
illogical and cause you to throw out cryptosystems which provide strong
protection of the messages it is used to send, in favour of weak systems.
A very small bias in the output of the PRNG ( and RC4's is very small) does
not in an of itself indicate a weakness. It might be indicative of other
weaknesses, and fear of that is the main reason why people distrust it, but
of itself it does not indicate a weakness.
Let me postulate that every finite key PRNG has a distinguisher. It might
be a bias in the single byte output, a byte pair correlation, whatever.
Would that mean that stream cyphers all all dead and useless for hiding
messages? The answer is clearly no. One must be careful. However, those
stream cyphers may still be perfectly adequate for providing the message
protection they are designed to provide. Ie, those distinguishers may be
perfectly benign as far as the main functionality of the cypher is
concerned. They may also indicate the existence of far more deadly
distinguishers. Ie, one should distinguish between distinguishers.
That is not clear at all.
> --Thomas Pornin
Bill Unruh
claim that properly used RC4 (eg that the first 256 bytes are discarded for
example) is as secure as AES. (proof by contradiction). The concern is that
there have been very slight biases found in the distribution of the output
of RC4 ( slight meaning of the order of one part in 10^5 lopsidedness of the
distribution of the output bytes). No evidence has been given that this
lopsidedness could be used to read the plaintext of a message sent via RC4
( except messages with redundancy of the order of 10^10) and as far as I
know, none is known. But this worries some people. Is it a legitimate
worry? As far as security is concerned there are insecurities in your
system that are far far far higher than this. (Spies and garbage are only
two of them). So to the extent that worry about RC4 detracts you from going
after the real security issues, the concern raised is itself a security
hole.
Paul Rubin
> No evidence has been given that this
> lopsidedness could be used to read the plaintext of a message sent via RC4
> ( except messages with redundancy of the order of 10^10) and as far as I
> know, none is known.
Even if it is proved that no way to read the plaintext exists, there
can still be security failures that don't involve reading the
plaintext. For example, if some group of 3 keystream bits spread
across a multi-kilobyte block are somehow correlated with each other,
and those bits always happen to be the same in the plaintext (e.g.
they are part of the header of each frame in some video format),
seeing the correlation across enough ciphertext may be enough to
detect that the plaintext is video in that format, even if you can't
tell what's in the video frames.
As another example, I think Greg Rose mentioned a while back that if
you find a hard drive of RC4-encrypted natural language text in some
cave in Afghanistan, and you know that it's written in Arabic or
Farsi, then a Kolmogorov-Smirnov test may be enough to tell which
language it's in (and therefore who to drop bombs on), even though it
doesn't reveal actual text. That would be a security failure too.
SSL is supposed to be a general purpose encryption format. That means
it has to do more than prevent actual plaintext bits from leaking. It
has to not leak any info about the plaintext at all.
Paul Rubin
> No, the defender is concerned with the same thing-- that no money gets
> siphoned, to use your metaphore.
Wrong, the defender has a harder goal than that. There are 3 possible
situations:
1) A way to siphon money exists, and an attacker figures it out and
uses it (ouch).
2) A way to siphon money exists, but no attacker figures it out (whew).
3) No way to siphon money exists (yay).
You are saying that situation 2 is as good as situation 3, but a good
defender would not accept that equivalence. The defender wants
situation 3 and will go to any reasonable measures to prevent
situation 2, since those measures automatically prevent situation 1.
The defender, in short, has the notoriously difficult task of trying
to prove a negative, or at least gather the best possible evidence of
the negative. Failing to come up with a specific attack doesn't help
much with that. Something more generic is required. That generic
thing is the absence of distiguishers.
> There may be perfectly benign distiguishers, and deadly ones, as far
> as decryption is concerned.
Right, and in security, if you can't tell the difference between a
benign distinguisher and a deadly one, you have to assume they are
all deadly. Therefore, you want a cipher with no distinguishers.
Unruh
>Bill Unruh <un...@physics.ubc.ca> writes:
>> No evidence has been given that this
>> lopsidedness could be used to read the plaintext of a message sent via RC4
>> ( except messages with redundancy of the order of 10^10) and as far as I
>> know, none is known.
>Even if it is proved that no way to read the plaintext exists, there
>can still be security failures that don't involve reading the
>plaintext. For example, if some group of 3 keystream bits spread
>across a multi-kilobyte block are somehow correlated with each other,
>and those bits always happen to be the same in the plaintext (e.g.
>they are part of the header of each frame in some video format),
>seeing the correlation across enough ciphertext may be enough to
>detect that the plaintext is video in that format, even if you can't
>tell what's in the video frames.
Except there is no evidence of such correlations for RC4.
>As another example, I think Greg Rose mentioned a while back that if
>you find a hard drive of RC4-encrypted natural language text in some
>cave in Afghanistan, and you know that it's written in Arabic or
>Farsi, then a Kolmogorov-Smirnov test may be enough to tell which
>language it's in (and therefore who to drop bombs on), even though it
>doesn't reveal actual text. That would be a security failure too.
Given that they dropped bombs on Iraq with made up evidence, I suppose they
could do so with such incredibly poor evidence, but I do not think that the
hard drive would figure in the decision. And I do not believe that you
could use the biases in RC4 to differentiate with any hard drive in
existence. (By the way, you know this disk is entirely in Arabic of Farsi
how?)
Unruh
>Unruh <unruh...@physics.ubc.ca> writes:
>> No, the defender is concerned with the same thing-- that no money gets
>> siphoned, to use your metaphore.
>Wrong, the defender has a harder goal than that. There are 3 possible
>situations:
>1) A way to siphon money exists, and an attacker figures it out and
> uses it (ouch).
>2) A way to siphon money exists, but no attacker figures it out (whew).
>3) No way to siphon money exists (yay).
There are always ways of siphoning money. That is a given. The question is
where do you spend your money and time and effort defending yourself. Some
are a waste of money, but more importantly use up the precious resource of
time for no advantage. I would say worrying about RC4 falls in that
category. Look to your empoyees first.
>You are saying that situation 2 is as good as situation 3, but a good
>defender would not accept that equivalence. The defender wants
Those two are equivalent, if the defender knows they are the actual
options. Furthermore, there is NO way of knowing which of them is true. As
you have repeatedly said, there is no way of knowing if ways to siphon
money exist or not. AES could be broken tomorrow. That would demonstrate it
was in category 2, not 3, and we know of no way today of knowing whether or
not it is.
Furthermore, worrying about which category it is in detracts fromfar more
useful occupations of your time.
>situation 3 and will go to any reasonable measures to prevent
>situation 2, since those measures automatically prevent situation 1.
The quesiton is what is reasonable.
>The defender, in short, has the notoriously difficult task of trying
>to prove a negative, or at least gather the best possible evidence of
>the negative. Failing to come up with a specific attack doesn't help
>much with that. Something more generic is required. That generic
>thing is the absence of distiguishers.
No, that is not sufficient ( unless he could prove that no distinguishers
exist, an impossiblity since some do exist. ) So then he has to prove that no
distinguishers exist which are computationally reasonable, again a hopeless
task. Now you feel that "if distiguisher exists, I don't trust it." Fine. I
may feel that cryptosystems which have the letter A in their name should
not be trusted. It is not clear to me, that absent an actual use of that
distinguisher for an actuall attack, either prejudices is better than the
other.
>> There may be perfectly benign distiguishers, and deadly ones, as far
>> as decryption is concerned.
>Right, and in security, if you can't tell the difference between a
>benign distinguisher and a deadly one, you have to assume they are
>all deadly. Therefore, you want a cipher with no distinguishers.
Since you cannot tell whether or not a crypto system is breakable or not,
you have to assume all are breakable, and therefor not use any cipher at
all. Seems to be an equivalent argument to yours. But clearly silly.
Gordon Burditt
>>you find a hard drive of RC4-encrypted natural language text in some
>>cave in Afghanistan, and you know that it's written in Arabic or
>>Farsi, then a Kolmogorov-Smirnov test may be enough to tell which
>>language it's in (and therefore who to drop bombs on), even though it
>>doesn't reveal actual text. That would be a security failure too.
>
>Given that they dropped bombs on Iraq with made up evidence, I suppose they
>could do so with such incredibly poor evidence, but I do not think that the
>hard drive would figure in the decision. And I do not believe that you
>could use the biases in RC4 to differentiate with any hard drive in
>existence. (By the way, you know this disk is entirely in Arabic of Farsi
>how?)
I thought the existence of Iraq is more than sufficient cause to
drop bombs on it. Or is it the existence of bombs is more than
sufficient cause to drop them on Iraq?
Finding a hard drive written in unencrypted Goa'uld (just how do
you know that the Goa'uld is unencrypted if you have no way of
translating it - you don't have a high enough security clearance
to know about those who can?) in the "return to manufacturer" bin
at Circuit City mixed in with a pile of ballots for Al Gore and a
partial translation of the Goa'uld to English in Daniel Jackson's
handwriting would also be cause to bomb Iraq.
Guy Macon
Greg Rose wrote:
>The reason I tend to mention the distinguisher
>first is that it is absolutely inherent in RC4,
>and can't be worked around.
The state of the art for RC4 implementations is RC4-drop[N] with
keys that are generated by a strong RNG or a hash function. See
[ http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html#RC4-drop ].
Even RC4-drop[N] has a keystream that is distinguishable from
random given 2^31 to 2^32 bytes (2GB-4GB)of the stream, but
there is no known distinguisher for RC4-drop[N] when less than
2^3 bytes (1GB) of stream are generated from a key.
Also see [ http://www.rsa.com/rsalabs/node.asp?id=2009 ],
which claims
"The 'heart' of RC4 is its exceptionally simple and extremely
efficient pseudo-random generator. The recent attacks relate
only to the key-scheduling algorithm, not to the generator.
There are at present no known practical attacks against this
generator when initialized with a randomly-chosen initial state."
Paul Rubin
> Since you cannot tell whether or not a crypto system is breakable or not,
> you have to assume all are breakable, and therefor not use any cipher at
> all.
You go with the one with the best evidence of unbreakability, which
between AES and RC4, means AES, the one without known distinguishers.
Guy Macon
Unruh wrote:
>It is of course clear that if the distiguisher is bad enough, then an
>attack becomes possible, but with what RC4 has it would be nice if some
>attack were actually demonstrated. Otherwise it would seem that immense
>effort and time are spent on defending against imaginary foes, while real
>foes could be overlooked.
And it should be kept in mind that RC4 has had a *lot* of effort
expended trying to break it. I wonder how many weaknesses for
AES will be known when it has been hammered upon by experts for
as many years as RC4 has.
Paul Rubin
> Even RC4-drop[N] has a keystream that is distinguishable from
> random given 2^31 to 2^32 bytes (2GB-4GB)of the stream, but
> there is no known distinguisher for RC4-drop[N] when less than
Periodic re-keying can presumably get rid of that 2^30 distinguisher,
but I don't think any widespread protocols (viz. SSL) actually use it
that way.
I hacked on a text chat application a while back, where two people
could have an on-and-off conversation over a long period. It was
supposed to use TLS (AES-CBC) to encrypt the conversation and each
client sent a 100 byte packet (the user's message padded with zeros)
to the other every 2 seconds whether anyone was typing or not, in
order to not disclose when the conversation was active. That's 2^30
bytes in 6 months or so. Of course it would be reasonable to do the
same thing for voice chat, increasing the traffic rate to 13 kbps or
whatever. That's 2^30 bytes in just a week. In either case, a
distinguisher (tells when the ciphertext is all 0's over some long
period) would be a security failure.
Guy Macon
Unruh wrote:
>Now you feel that "if distiguisher exists, I don't trust it." Fine. I
>may feel that cryptosystems which have the letter A in their name should
>not be trusted. It is not clear to me, that absent an actual use of that
>distinguisher for an actual attack, either prejudices is better than the
>other.
I would go farther and say say that the feeling you speak of is
not actually a feeling that
"Algorithm A has a known distiguisher so I don't trust it,
algorithm B has no known distiguisher so I trust it more
than I trust A."
But rather
"A known distiguisher for algorithm A was found after N
years of analysis, so I don't trust it, but I do trust
algorithm B (which has had far less scutiny) on the
assumption that no distiguisher will be known after it
has also survived N years of analysis."
Paul Rubin
> years of analysis, so I don't trust it, but I do trust
> algorithm B (which has had far less scutiny) on the
> assumption that no distiguisher will be known after it
> has also survived N years of analysis."
Oh come on, not much work has been done on RC4 since 2001 or so, and
AES has had far more attention.
Guy Macon
Paul Rubin wrote:
>
>Guy Macon <http://www.GuyMacon.com/> writes:
>
>> Even RC4-drop[N] has a keystream that is distinguishable from
>> random given 2^31 to 2^32 bytes (2GB-4GB)of the stream, but
>> there is no known distinguisher for RC4-drop[N] when less than
>> 2^30 [typo fixed -phr] bytes (1GB) of stream are generated from a key.
>
>Periodic re-keying can presumably get rid of that 2^30 distinguisher,
>but I don't think any widespread protocols (viz. SSL) actually use it
>that way.
"There are two reasons why the new attacks do not apply to
RC4-based SSL. First, SSL generates the encryption keys
it uses for RC4 by hashing (using both MD5 and SHA1), so
that different sessions have unrelated keys. Second, SSL
does not re-key RC4 for each packet, but uses the RC4
algorithm state from the end of one packet to begin
encryption with the next packet. The recent techniques
of Fluhrer, Mantis and Shamir thus do not apply to SSL."
Source: [ http://www.rsa.com/rsalabs/node.asp?id=2009 ]
>I hacked on a text chat application a while back, where two people
>could have an on-and-off conversation over a long period. It was
>supposed to use TLS (AES-CBC) to encrypt the conversation and each
>client sent a 100 byte packet (the user's message padded with zeros)
>to the other every 2 seconds whether anyone was typing or not, in
>order to not disclose when the conversation was active. That's 2^30
>bytes in 6 months or so. Of course it would be reasonable to do the
>same thing for voice chat, increasing the traffic rate to 13 kbps or
>whatever. That's 2^30 bytes in just a week. In either case, a
>distinguisher (tells when the ciphertext is all 0's over some long
>period) would be a security failure.
"...An upper limit of 24 hours is suggested for session ID lifetimes..."
Source: [ http://www.faqs.org/rfcs/rfc2246.html ]
Guy Macon
Paul Rubin wrote:
>not much work has been done on RC4 since 2001 or so, and
>AES has had far more attention.
Could be. A count of published papers would be one good
indicator showing the likelyhood of this.
Greg Rose
Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
>> Even RC4-drop[N] has a keystream that is distinguishable from
>> random given 2^31 to 2^32 bytes (2GB-4GB)of the stream, but
>> there is no known distinguisher for RC4-drop[N] when less than
>> 2^30 [typo fixed -phr] bytes (1GB) of stream are generated from a key.
>
>Periodic re-keying can presumably get rid of that 2^30 distinguisher,
>but I don't think any widespread protocols (viz. SSL) actually use it
>that way.
Actually, no. It doesn't matter how often you
rekey, the distinguishers still apply.
Paul Rubin
> Source: [ http://www.faqs.org/rfcs/rfc2246.html ]
Yeah, the real concern is what happens if the 2^30 gets improved to
(e.g.) 2^25, or if the data rate of the application is cranked up by
another factor of 100 to handle video, or something like that.
Anyway, one gets carried away about the possibility of a distinguisher
being amplified somehow into leaking plaintext. The real issue is
that Unruh's notion is simply bogus, that plaintext leaks are the only
security failures that any crypto application can possibly have. Even
if you're quite confident that the cipher doesn't leak plaintext
("security property 1"), if your application is sensitive to
statistical leaks, such as correlations between bits that are far
apart from each other, that's another thing ("security property 2")
you have to have to check for. To quote Bellare and Goldwasser
(http://www-cse.ucsd.edu/~mihir/papers/gb.pdf p. 61, similar quote
also appears in Bellare and Rogaway's lecture notes of a few years
earlier):
As we see more usages of ciphers, we build up a longer and longer
list of security properties SP1, SP2, SP3, . . . that are
necessary for the security of some block cipher based application.
Such a long list of necessary but not sufficient properties is no
way to treat security. What we need is one property of a block
cipher which, if met, guarantees security of lots of natural
usages of the cipher. Such a property is that the block cipher be
a pseudorandom permutation (PRF), a notion explored in another
chapter.
(Heh, PRF there should say PRP). In the case of stream cipher, the
master property is indistinguishability from a RNG. What that does is
knock out the need to evaluate the cipher separately for each
application, and lets you use it much more generically. For a general
purpose protocol like SSL, this is essential. There are of course
still some specific applications where RC4 is the best engineering
compromise because of its speed on a certain class of hardware, but
those just don't occur that often. And RC4's simplicity that makes it
so attractive is perhaps its most dangerous feature: people think they
can plug it into an application and avoid complexity, but the
knowledge and infrastructure required to use it safely is quite
complex, as the WEP designers found out the hard way.
Bellare and Rogaway's notes were just about the most enlightening
thing I've ever read in crypto. I don't claim to be a real expert by
any serious standard, but those notes were the first clue that I got
about how to use crypto primitives without stumbling in the dark.
They should certainly be required reading for sci.crypt regulars who
get into these theory-related discussions. See:
http://www.cs.ucdavis.edu/~rogaway/classes/227/fall03/book/
With that, I'm going to try (maybe not successfully) to drop out of
this thread.
Guy Macon
Greg Rose wrote:
>
>Paul Rubin wrote:
>
>>Periodic re-keying can presumably get rid of that 2^30 distinguisher,
>
>Actually, no. It doesn't matter how often you
>rekey, the distinguishers still apply.
"There are two classes of attack on Arcfour described in [MIRONOV].
Strong distinguishers distinguish an Arcfour keystream from
randomness at the start of the stream and are defended against by the
algorithm defined in this document. Weak distinguishers can operate
on any part of the keystream, and the best ones, described in [FMcG]
and [MANTIN05], can use data from multiple, different keystreams. A
consequence of this is that encrypting the same data (for instance, a
password) sufficiently many times in separate Arcfour keystreams can
be sufficient to leak information about it to an adversary. It is
thus RECOMMENDED that Arcfour (either in the form described here or
that described in [RFC4251]) not be used for high-volume password-
authenticated connections."
Source: [ http://www.faqs.org/rfcs/rfc4345.html ]
I am now going to throw myself at the mercy of those with more
expertise than I have as a Electronics Engineer It sort of seems
to me (but I suspect that I may be getting this wrong) from my
reading of these papers...
[ http://www.mindspring.com/~dmcgrew/rc4-03.pdf ]
[ http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1043_IPA-RC4_%20report_final.pdf ]
[ http://www.waset.org/pwaset/v38/v38-176.pdf ]
[ http://www.ciphergoth.org/crypto/rc4/ ]
[ http://eprint.iacr.org/2005/175.pdf ]
...that when using ARC4-DROP-1536 (As recommended in RFC4345)
and random keys, the weak distinguishers that can use data
from multiple, different keystreams need something like 2^40
to 2^44 bytes, not the 2^30 bytes that suffice for a single
keystream. I am not sure, however, whether I have gotten that
right. Any comments/corrections would be most welcome.
David Eather
"Algorithm A has a known distiguisher so I distrust it,
algorithm B has no known distiguisher so I distrust it less
than I distrust A."
pubkeybreaker
> mike clark <m...@netadv.net> writes:
> >On Mar 22, 11:11=A0am, "Dave -Turner" <ad...@127.0.0.1> wrote:
> Note that ease of coding IS part of security. The harder to encode, the
> greater the probablility of subtle bugs.
True, but irrelevant. Encryption algorithms have KATS and get
thoroughly
vetted before use.
>
> Is RC4 more or less secure than AES? I doubt that any reputable
> cryptographer would make a pronouncement.
You would lose that bet.
I will give a hint: Why do you think that the NSA has approved AES
to protect classified information? Why haven't they approved RC4???
pubkeybreaker
> Unruh <unruh-s...@physics.ubc.ca> writes:
> It is simply not accepted practice in cryptography to assume that
> something is secure until the presence of an exploit is shown. We are
> seeking the absence of exploits, not a mere lack of proof of their
> presence. Mathematically proving the absence of exploits appears
> beyond our capability at the moment (that would require showing P!=NP
> among other things)
This is false as far as block ciphers go. They are FIXED SIZE,
so the question of whether P = NP? does not even apply.
The time to encrypt a block with AES is O(1) and the time to
decrypt by exhaustive search is bounded from above by O(1).
P= NP? does not apply.
>
> > AES has complexity and slow speed, which means it will not be used
> > when it should be, and thus the security is be 0.
>
> If you're thinking of (say) tiny embedded systems, RC4 is worse in
> most of them than AES, because of its higher RAM requirements.
>
> If you're thinking of more typical dektop and server computers of the
> type likely to run protocols like SSL, AES is fine in almost every
> application where RC4 would be ok. There are occasional exceptions
> but they are uncommon.
Yep!
Paul Rubin
> This is false as far as block ciphers go. They are FIXED SIZE,
> so the question of whether P = NP? does not even apply.
Good point for AES--we want something more generic, i.e. quantifying
over all TM's of a less than a given size (this corresponds to an
attacker's storage bound), none can distinguish AES (up to some
probability) in less than some (large) amount of running time. On the
other hand, this is a combinatorial statement, so at least we know
that it is logically decidable. Of course for something like Rijndael
(of which AES is a fixed instance), which is parametrized in key size
and block size, we can ask for a general version of the above, which
gets back to P=NP.
Greg Rose
My understanding, borne out by experiment, is that
the correlations can be detected reliably in the
same amount of keystream accumulated, so long as
you know the alignment of the output bytes (that
is, the index 'i' associated with them) and don't
avoid using certain index values. For example,
some years ago I presented the results of
statistical tests on RC4, and IIRC I used
1-gigagyte independent streams.
I reported those result here in sci.crypt, but
being basically lazy, I seem to have misplaced
them. But Google makes up for that: look for "rc4
bad buckets" in google groups. See also Scott's
(Poncho's) follow up. Basically what he said
is that to use less data, you need to be specifically
looking for RC4-style biases, whereas I was just
using an off-the-shelf tool.
Maaartin
> >but I don't think any widespread protocols (viz. SSL) actually use it
> >that way.
>
> Actually, no. It doesn't matter how often you
> rekey, the distinguishers still apply.
>
> Greg.
Somehow, I can't believe it. At least, when I rekey after each single
byte (which would be very stupid and very slow)...
Could you elaborate on it?
Unruh
>Paul Rubin wrote:
>>not much work has been done on RC4 since 2001 or so, and
>>AES has had far more attention.
>Could be. A count of published papers would be one good
>indicator showing the likelyhood of this.
Nope, just an indicator that something interesting has been found. Negative
results tend not to get written up or published.
Scott Fluhrer
"Maaartin" <graj...@seznam.cz> wrote in message
news:75049ee4-b0ab-4b07...@f19g2000yqh.googlegroups.com...
True, the 2^30 distinguisher relies on the distribution of digraphs (two
consecutive outputs), and so if you literally rekey after each byte, there
will never two consecutive outputs from the same RC4 state, and so it won't
work.
On the other hand, if you rekey every two bytes, then you will have
digraphs, and so the distinguisher will be able to work just fine (actually,
it might work even better, assuming that you discard a multiple of 256 bytes
before generating the two bytes; IIRC, the bias in the states with i=1 was
significantly higher than the average bias values, and so if you generate a
stream exclusively from those states, you might have an even stronger bias
overall, even accounting for the fact that you have half as many digraphs
from the same RC4 state available).
>
> Could you elaborate on it?
The bias is not due of any particular key, it's due to how the 'generate the
next keystream byte' function works, and in particular, the biases that can
occur if the same permutation location is used for multiple purposes while
generating the output. Because of this, it is unaffected if you rekey
(which changes the actual permutation contents, but not the actual process
of generating keystream bytes).
--
poncho
Unruh
remind me-- the bias is such that FF occurs slightly (10^-15) times more
frequently than other bytes, or was it some combination that occured
slightly more frequently. One could alter this by discarding say every
10^15 FF from the output. Just as with discarding the first 256 bytes, both
ends would have to know to do this to keep in sync.
Guy Macon
Unruh wrote:
>remind me-- the bias is such that FF occurs slightly (10^-15)
>times more frequently than other bytes, or was it some combination
>that occured slightly more frequently. One could alter this by
>discarding say every 10^15 FF from the output. Just as with
>discarding the first 256 bytes, both ends would have to know to
>do this to keep in sync.
What's interesting about the above idea is that, from a standpoint
of the code being simple to implement (so simple that ciphersaber
is built on the concept of memorizing the algorithm along with the
key and recreating it on the fly any using any convenient computer
language rather than trying to take working code across borders or
even storing working code in between encryption/decryption sessions)
an algorithm that discards 65535 bytes, uses one, discards another
65535, etc., is simply a standard RC4 algorithm with an additional
16-bit counter. You lose the speed of RC4, of course, but dropping
65535 out of every 65536 bytes would seem to negate any distinguisher
that is based upon a small corrolation between adjacent outputs.
Are the names RC4S (RC4 Slow - drops 255 out of every 265 outputs)
and RC4SS (RC4 Super Slow - drops 65535 out of 65536) taken? :)
Maaartin
Thank you.
> On the other hand, if you rekey every two bytes, then you will have
> digraphs, and so the distinguisher will be able to work just fine (actually,
> it might work even better...
That's funny. I see, rekeying very often is neither practical nor
helpful.
To Guy Macon:
> What's interesting about the above idea is that, from a standpoint
I'm quite sure, what you describe wasn't Unruh's idea. IMHO he said
the following:
1. There's a small bias in RC4
2. Let the bias be - for example - FF occuring too often.
3. Compensate for it by dropping each n-th occurence of FF so that
it's probability is the same as the probability of any other output
byte.
According to Scott Fluhrer the bias is in the distibution of digraphs,
but it makes the compensation just slightly more complicated. I wonder
whether this process introduces other problems.
Unruh
>Unruh wrote:
>>remind me-- the bias is such that FF occurs slightly (10^-15)
>>times more frequently than other bytes, or was it some combination
>>that occured slightly more frequently. One could alter this by
>>discarding say every 10^15 FF from the output. Just as with
>>discarding the first 256 bytes, both ends would have to know to
>>do this to keep in sync.
>What's interesting about the above idea is that, from a standpoint
>of the code being simple to implement (so simple that ciphersaber
>is built on the concept of memorizing the algorithm along with the
>key and recreating it on the fly any using any convenient computer
>language rather than trying to take working code across borders or
>even storing working code in between encryption/decryption sessions)
>an algorithm that discards 65535 bytes, uses one, discards another
>65535, etc., is simply a standard RC4 algorithm with an additional
Well, that is the opposite of what I suggested. I was suggesting keeping
65535 bytes and then dropping one. ( except I count up 65535 bytes which
are FF and then drop the next FF byte.) This would remove any bias which is
due to there being too many FF bytes in a long term stream. I have read
that the actual bias is more like repetition of bytes is a bit too
frequenct. They you could drop the pair so as to bring it back into line.
Now this might well still imply that there was a very much longer term bias
in the output. But it is sort of similar to the vonNeumann whitening trick
( if 0 and 1 occur with the wrong frequency, instead use pairs and code 01
as 1 and 10 as 0 and throw away 00 and 11. That is very profligate ( you
are using roughly 1/4 of the output), but it works if the bias is simply in
the frequency of the bits. In the RC4 case there is a far far smaller bias,
and thus one needs to discard far far fewer bits to eliminate the bias. You
might in the process introduce other, much more long term biases, but as
people have said, if you make the distinguisher hard enough it does not
matter, since all crypto systems are known to have distinguishers due to
the finite key space-- computationally feasible was the words used.
Ie, I do not believe that you need to slow down RC4 to your extent to
eliminate the known biases.
Scott Fluhrer
"Unruh" <unruh...@physics.ubc.ca> wrote in message
news:Whcyl.18369$Db2.10671@edtnps83...
that in a predictable fashion, the attacker would know that as well) that
occur slightly more frequently than expected (IIRC, except for one, it as
1+1/256 times more often than expected), and there were a number of
digraph/i values that occur slightly *less* frequently than expected
(1-1/256 times as often as expected).
> One could alter this by discarding say every
> 10^15 FF from the output. Just as with discarding the first 256 bytes,
> both
> ends would have to know to do this to keep in sync.
You might do some complex logic to discard the more-frequent than expected
combinations every so often. The less-frequently-than expected ones would
be a bit harder to handle (you'd need to do the probabilistic discard logic
on all combinations expect for these specific digraphs). On the other hand,
that would unify the digraph distribution, but there might be, say, trigraph
distribution characteristics that would be still be detectable (something
which I don't believe anyone has done any sort of study on)
And, as Guy points out, you would lose a lot of the simplicity advantages
(and speed, although RC4 isn't that fast compared to some more modern key
generators anyways).
--
poncho
Maaartin
> (and speed, although RC4 isn't that fast compared to some more modern key
> generators anyways).
I'm afraid, such a complex logic could consume much more time than RC4
itself. Probably there's simpler solution performing better, something
like xoring the output with a fast non-cryptographic random generator
having no such bias could do, couldn't it?
WTShaw
It's really a simple matter to simply add a layer of processing so
that good random results become skewed. The result is that an attacker
wants to exploit the skewedness which goes nowhere rather than
maximize the better randomness which as almost any expert suggest
would be a worse choice. Smoke and mirrors still even mask skewed
natural results to build a case for exploring elsewhere than where the
grail is.
Forgetting the real strengths involved in various algorithms for the
bright draw of new stars as worshiped by myrids of obedient followers
chanting montras in a narrow procession is in fact faith-based
cryptography.
Getting down to cases is rather the domain of the forever doubting
Thomas class who fear not to weigh and judge using all measure of
strength and ignore none.
Unruh
The suggestion was to do something similar to the current throwing away of
the first 256 bytes to get rid of the intialisation weakness. If you add a
second ( non-cryptgraphic) stream, it is not longer RC4, while occasionally
thowing away a byte could still be called RC4. I do not believe that in the
context of encrypting plaintext the problems with RC4 are non-trivial.
rossum
<sflu...@ix.netcom.com> wrote:
>You might do some complex logic to discard the more-frequent than expected
>combinations every so often. The less-frequently-than expected ones would
>be a bit harder to handle (you'd need to do the probabilistic discard logic
>on all combinations expect for these specific digraphs).
Perhaps, if you could find a matching pair of digraphs where the
increased frequency of one matches the decreased frequency of the
other, you could replace the too frequent digraph with the
corresponding underrepresented digraph at appropriate intervals.
The match would not have to be exactly perfect, but a reasonably close
fit should improve the characteristics of the final byte stream.
rossum
Paul Rubin
> Perhaps, if you could find a matching pair of digraphs where the
> increased frequency of one matches the decreased frequency of the
> other, you could replace the too frequent digraph with the
> corresponding underrepresented digraph at appropriate intervals.
I think anything that adds processing to the entire rc4 keystream such
as checking for certain digraphs, somewhat defeats the purpose of rc4,
which is extreme speed.
Would it help to drop 256+k bytes from the beginning of the keystream
instead of 256, where k is a secret number derived from the key? That
would conceal the value of "i" from the attacker, but of course there's
just 256 possibilities, so the attacker could try them all...
Greg Rose
Well, it introduces timing problems, and
implementation issues, and slows it down a
surprising amount (remember, conditional branches
on modern CPUs break the pipeline).
But again, it's just a patch for a broken
algorithm; no one proposes any such fix for AES
implementations! Which was entirely the point
of this discussion.
David Eather
> On Mar 24, 1:35 am, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
>> Unruh <unruh-s...@physics.ubc.ca> writes:
>>> Since you cannot tell whether or not a crypto system is breakable or not,
>>> you have to assume all are breakable, and therefor not use any cipher at
>>> all.
>> You go with the one with the best evidence of unbreakability, which
>> between AES and RC4, means AES, the one without known distinguishers.
>
> It's really a simple matter to simply add a layer of processing so
> that good random results become skewed.
How? Are you thinking of basic operations like xor or add mod n to the
ciphertext?
Unruh
No, the point of this discussion was whether or not RC4 was as safe to use
for encryption as is AES. These musings are whether or not there are some
simple ways of massaging RC4 so that the "cosmetic" distinguishers in RC4
which bother some people could be eliminated. Note that if one believed
that a technique like the one I suggested would remove the distinguishers,
and would therefor make people feel that RC4 was safe again, then that
would be evidence to me that those distiguishers were just cosmetic flaws
and not the "completely broken" flaws that has been claimed for them.
Ilmari Karonen
>
> Would it help to drop 256+k bytes from the beginning of the keystream
> instead of 256, where k is a secret number derived from the key? That
> would conceal the value of "i" from the attacker, but of course there's
> just 256 possibilities, so the attacker could try them all...
As you note, trying out 2^8 possible values is not much of a
hindrance. In any case, simply counting general digraph frequencies
does not require knowledge of i. Indeed, Fluhrer & McGrew (2001) note
that:
"The irregularities in the digraph distribution that we observed
allow the recovery of n and i parameters [...] if the attacker
happens not to know them."
Personally, I don't find it surprising at all that RC4's output is
biased -- at its core, it's little more than a badly written Knuth
shuffle. What's surprising is that, despite its biases, it has
withstood as much cryptanalysis as it has while still retaining any
semblance of security at all.
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
Bill Unruh
>No, the point of this discussion was whether or not RC4 was as safe to use
>for encryption as is AES. These musings are whether or not there are some
>simple ways of massaging RC4 so that the "cosmetic" distinguishers in RC4
>which bother some people could be eliminated. Note that if one believed
>that a technique like the one I suggested would remove the distinguishers,
>and would therefor make people feel that RC4 was safe again, then that
>would be evidence to me that those distiguishers were just cosmetic flaws
>and not the "completely broken" flaws that has been claimed for them.
Let me amplify on that "cosmetic" comment. Lets take AES based stream
cypher, and let us assume that it really really is a PRNG, with no biases.
Now, let us change that stream such that I go through the output and I
throw away every 1000 value of FF in the output stream. The resultant
stream cypher will have a distinguisher. It has 1-1/1000 fewer FF on
average than it has any other chacters. However, it would seem to me that
despite that distinguisher, that stream cypher would protect the cleartext
just as would the original AES stream cypher, except for communications
which had a redundancy of something like 256000^2 (squared because Poisson
statistics cannot distinguish a bias in less than N^2 outputs).
Ie, as far as using it to protect communications, that AES based stream
cypher with its distinguisher would be just as good as the original. That
distinguisher is "cosmetic" and not a security hole ( except for situations
like I described.)
So yes, this stream is weaker than the original on some special cleartexts,
but those are so special that almost noone need worry about them.
WTShaw
> WTShaw wrote:
>
> > It's really a simple matter to simply add a layer of processing so
> > that good random results become skewed.
>
> How? Are you thinking of basic operations like xor or add mod n to the
> ciphertext?
>
approach. I can't remember the thread but once I sold the idea as
valid to Ritter at al, because it works. You have the option of
picking characters to be more frequent and/or hiding the presence of
others.
If your are dealing with base 64, you use a cylinder with 65 random
characters in each wheel and of a length 1 wheel longer that the group
your are manipulating. Register the characters in your group on the
wheels with the 65th character registered with them. Rotate the
cylinder and pick your preferences being sure not to include any of
those 65th characters. You have a number of choices equal to at least
65 less the number of wheels. It all works like a champ,
electronically of course.
I'm itching to get back into the cylinder business in a universal
format,to amuse, to amaze, and to perplex. However, first things
first and generation of cylinders is the first step, picking or making
random the rotations the second, and putting it all together the
third, but I've done it all before, simple, simple simple, with extant
algorithms preserved to copy, soon I hope.
Maaartin
> second ( non-cryptgraphic) stream, it is not longer RC4, while occasionally
> thowing away a byte could still be called RC4.
Ok, but is this anything more than a subjective opinion?
1. Whatever you do, it's a different algorithm.
2. In both cases you loose no security.
I think even I could prove this.
> Well, it introduces timing problems, and
> implementation issues, and slows it down a
> surprising amount (remember, conditional branches
> on modern CPUs break the pipeline).
Many things can be done easily without conditional branches, e.g., for
dropping each 256th 0xFF you could do the following (I assume you fill
some buffer instead of encrypting directly, this is usually faster
anyway; there may be errors, I never tried it ).
for (int i=0, cnt=0; i<limit; ++i) {
buf[i] = nextValue();
cnt += (1 + buf[i]) >> 8;
i -= cnt >> 8;
cnt -= (cnt>>8) << 8;
}
Assuming some compiler optimizations (or optimizing the C code
manually) it could be way faster than branching. Nonetheless, I
completelly agree: it's not worth it, it's error-prone, and even in
such a simple case already more complicated (and maybe even slower)
than RC4 itself!
OTOH, xoring with a simple non-cryptographic RNG could be very fast,
something like less than 1 cycle per byte on a 64-bit Intel/Amd. It's
simple and not error-prone and it would remove any digraph frequency
inbalance even without knowing how it looks like. Nonetheless, I've
got persuated not to use RC4 anyway.
Guy Macon
Unruh wrote:
>Ie, I do not believe that you need to slow down RC4 to your extent to
>eliminate the known biases.
Neither do I. On the other hand, while speed is an advantage in some
applications, in other applications slower is actually a bit better.
If, for example, you are encrypting emails, something 65536 times
slower than RC4 would still run so fast on a modern PC that you could
not tell the difference, and it would somewhat slow down any brute-
force guessing attack. I would still choose AES-256 for resistance
to such an attack, of course; RC4S and RC4SS are more thought
experiments than practical algorithms.
Guy Macon
Maaartin wrote:
Hmmmm... Just thinking out loud...
OK, RC4 cannot be easily paralized, but four and even eight-processor
computers are fast becoming common and fairly cheap. You could run
4 instances of RC4-drop-1536 and XOR them all with your plaintext.
Or you could try taking the output of two instances of RC4 as two
streams of bits and running them through a Von Neumann compensator.
It would be interesting to test the statistical propoerties of either
of the above for biases.
Again, these are just thought experiments, not serious proposals
for practical ciphers. The only real advantage of RC4 is the simple
algoritmm. Other ciphers are more secure, faster, or more flexible,
and it can be argued that a few have been more thouroughly analysed.
Guy Macon
Unruh wrote:
>The suggestion was to do something similar to the current throwing away of
>the first 256 bytes to get rid of the intialisation weakness. If you add a
>second ( non-cryptgraphic) stream, it is not longer RC4, while occasionally
>thowing away a byte could still be called RC4.
I don't believe that any rule says that RC4 *has* to work with 8-bit
values. Running everything at 16 bits would still be RC4, wouldn't
it? Or is there something special about 8-bits?
Guy Macon
Greg Rose wrote:
>But again, it's just a patch for a broken
>algorithm; no one proposes any such fix for AES
>implementations! Which was entirely the point
>of this discussion.
Excellent point. It will be interesting to see if any weaknesses
for AES are discovered in the next 20 years, and whether folks will
suggest "fixes" or entirely new algorithms. If the latter, it will
be interesting to see if any weaknesses for the replacement are
discovered in the following 20 years... :)
Paul Rubin
> algoritmm. Other ciphers are more secure, faster, or more flexible,
> and it can be argued that a few have been more thouroughly analysed.
The simplicity isn't THAT much of an advantage, since implementations
of other algorithms are well studied and tested. And the simplicity
is in fact illusory because of all the additional deployment
requirements and security caveats it has. The main thing RC4 has
going for it is pure speed. There are not many choices of comparable
speed that have been around for any length of time. I guess some of
the ESTREAM finalists come about the closest.
Ilmari Karonen
AFAIK, the main problems with RC4-16 are that a) it requires 256 times
as much memory as RC4-8, which is already memory-hungry for a cipher,
b) the key setup takes time proportional to the cipher state, and thus
also becomes 256 times slower, and c) the mixing during the operation
of the cipher is also correspondingly slower, so you need to drop 256
(or so) times as many initial outputs to get rid of the known biases
in the early part of the stream.
But yes, once it's fully mixed, the long-term biases should be lower.
Thomas Pornin
> The main thing RC4 has going for it is pure speed. There are not many
> choices of comparable speed that have been around for any length of
> time. I guess some of the ESTREAM finalists come about the closest.
Actually, most eSTREAM finalists are quite faster than RC4. On my
machine (Intel Core2 Q6600, 2.4 GHz), the (fairly optimized)
implementation of RC4 in OpenSSL crunches through about 295 MB per
second, which is about 8.1 cycles per byte. According to:
http://bench.cr.yp.to/results-stream.html
some modern stream ciphers do much better. E.g., Trivium is at 3.21
cycles per byte, Sosemanuk at 3.68 (both are eSTREAM "finalists").
Even a plain AES in CTR mode runs at 9.25 cycles per byte on that
kind of machine.
The speed advantage of RC4 is old lore. It dates from a time when the
comparison point was 3DES.
--Thomas Pornin
Kristian Gjųsteen
>It will be interesting to see if any weaknesses
>for AES are discovered in the next 20 years, and whether folks will
>suggest "fixes" or entirely new algorithms.
When did RC4 became public? When did the first attacks on RC4 appear?
When was AES/Rijndael first published? How long is that since?
--
Kristian Gjųsteen
rossum
Given that it operates on bytes, I suspect that RC4 would retain its
relative speed advantage on an embedded 8 bit chip, provided the chip
had enough memory to hold the required data. More modern cyphers tend
to be optimised for 32-bit or 64-bit operation and are usually faster
on the machines they are intended for.
$0.02
rossum
>
>
> --Thomas Pornin
Thomas Pornin
> Given that it operates on bytes, I suspect that RC4 would retain its
> relative speed advantage on an embedded 8 bit chip, provided the chip
> had enough memory to hold the required data.
We may say that, but some hard measures on the subject would be handy.
The benefit of an array-based system like RC4 is that index-based
accesses are fast on small CPU (when compared to arithmetic operations).
From what I gathered from discussions with smartcard producers, it seems
that stuffing a 32-bit ARM core into a very small embedded chip is quite
easier than adding an extra kilobyte of RAM. RAM seems to be the most
expensive resource on very small systems (whereas ROM is much cheaper).
Low-end smartcards of a few years ago had relatively powerful 8-bit CPU
(if one could call a 8051 or a 6805 "powerful") but typical RAM size was
around 128 to 256 bytes. An RC4 state is 258 bytes...
Also, RC4 is really hard to implement properly at the ASIC/FPGA level.
--Thomas Pornin
Paul Rubin
> > The main thing RC4 has going for it is pure speed. There are not many
> > choices of comparable speed that have been around for any length of
> > time. I guess some of the ESTREAM finalists come about the closest.
>
> Actually, most eSTREAM finalists are quite faster than RC4.
Yes, what I meant is they come closest to having been around for
some length of time (in that they have withstood at least some serious
cryptanalytic attention).
> On my machine (Intel Core2 Q6600, 2.4 GHz), the (fairly optimized)
> implementation of RC4 in OpenSSL crunches through about 295 MB per
> second, which is about 8.1 cycles per byte.
I think it is possible to do quite a bit better than that with a
64-bit implementation. But, crypto speeds on that class of CPU
aren't all that interesting, and will become completely irrelevant
in the next x86 generation, which will include hardware AES as
part of the AVX extensions.
I'd be interested in benchmarks on medium sized embedded processors,
e.g. ARM7 and the like.
> Even a plain AES in CTR mode runs at 9.25 cycles per byte on that
> kind of machine.
I think that is a bit-slice implementation, which I wouldn't think
of as "plain AES", but I guess it's a valid comparison.
Thomas Pornin
> 64-bit implementation.
Given what RC4 looks like, I feel inclined to think that having
64-bit registers does not yield any significant speed-up. Feel
free to prove me wrong.
> I'd be interested in benchmarks on medium sized embedded processors,
> e.g. ARM7 and the like.
I can try that, but it's not immediate (i.e. I will not do it tonight).
From my experience, an ARM or MiPS CPU will not be good at RC4. RC4
favours processors which are fast at performing array accesses with a
byte index. x86 CPU are quite good at that, mostly because of their
ancestry. However, most RISC-based processors are not good at all at
that kind of game.
On ARM architectures, Skipjack is rumoured to be specially efficient
(which is quite normal, since Skipjack was designed for the Clipper
chip, which was built around an ARM core).
--Thomas Pornin
Paul Rubin
> Given what RC4 looks like, I feel inclined to think that having
> 64-bit registers does not yield any significant speed-up. Feel
> free to prove me wrong.
http://perso.epitech.eu/~bevand_m/papers/rc4-amd64.html
> > I'd be interested in benchmarks on medium sized embedded processors,
> > e.g. ARM7 and the like.
>
> I can try that, but it's not immediate (i.e. I will not do it tonight).
Thanks! I'm actually particularly interested in the ARM9, now that I
think of it.
> On ARM architectures, Skipjack is rumoured to be specially efficient
> (which is quite normal, since Skipjack was designed for the Clipper
> chip, which was built around an ARM core).
That is interesting, it looked aimed more at 8-bit cpu's with almost
no ram. I hadn't heard Clipper had an ARM core either. Skipjack
certainly depends on 8-bit lookups.
robert...@yahoo.com
wrote:
> Guy Macon <http://www.GuyMacon.com/> wrote:
>
> >It will be interesting to see if any weaknesses
> >for AES are discovered in the next 20 years, and whether folks will
> >suggest "fixes" or entirely new algorithms.
>
> When did RC4 became public?
Rivest designed RC4 in 1987. The "ARC4" code was published in 1994.
> When did the first attacks on RC4 appear?
The published first serious evidence of RC4s issues was, I think,
Fluhrer and McGrew's, in 2000.
> When was AES/Rijndael first published? How long is that since?
1997 or 1998. In 1999 it made it to the "final five" of the AES
selection process, and it was selected as the AES standard in 2000,
which was approved in 2001.
So AES has been public for 11 or 12 years, vs. 15 for RC4. And the
level of scrutiny AES has received in those 11 years is clearly higher
than what RC4 did in the decade after 1994.
Scott Fluhrer
<robert...@yahoo.com> wrote in message
news:a47d68e2-5ac0-4dab...@z1g2000yqn.googlegroups.com...
> On Mar 27, 9:12 am, Kristian Gjųsteen <kristiag+n...@math.ntnu.no>
> wrote:
> > Guy Macon <http://www.GuyMacon.com/> wrote:
> >
> > >It will be interesting to see if any weaknesses
> > >for AES are discovered in the next 20 years, and whether folks will
> > >suggest "fixes" or entirely new algorithms.
> >
> > When did RC4 became public?
>
>
> Rivest designed RC4 in 1987. The "ARC4" code was published in 1994.
Actually, it was leaked (on sci.crypt, as a matter of fact), not published.
>
>
> > When did the first attacks on RC4 appear?
>
>
> The published first serious evidence of RC4s issues was, I think,
> Fluhrer and McGrew's, in 2000.
Sorry, but that's far from the first. In 1995, Andrew Roos discovered the
fact that RC4 may leak a key byte if the first two key bytes happened to sum
to 0 mod 256. In addition, in 1997 Jovan Goli\'{c} (sorry, my mailer can't
handle the proper accent) published a distinguisher that worked after about
2**40 bytes.
Just setting the record straight...
--
poncho
Unruh
><robert...@yahoo.com> wrote in message
>news:a47d68e2-5ac0-4dab...@z1g2000yqn.googlegroups.com...
>> On Mar 27, 9:12 am, Kristian Gjųsteen <kristiag+n...@math.ntnu.no>
>> wrote:
>> > Guy Macon <http://www.GuyMacon.com/> wrote:
>> >
>> > >It will be interesting to see if any weaknesses
>> > >for AES are discovered in the next 20 years, and whether folks will
>> > >suggest "fixes" or entirely new algorithms.
>> >
>> > When did RC4 became public?
>>
>>
>> Rivest designed RC4 in 1987. The "ARC4" code was published in 1994.
>Actually, it was leaked (on sci.crypt, as a matter of fact), not published.
Well, I would say it was leaked by being published on sci.crypt.
It certainly was not published by the designer (well as far as we know
anyway. I suppose Rivest could have been the one publishing it.)
Thomas Pornin
Mmmh, let's try: 141 MB/s, i.e. about 17 cycles per byte, on my 2.4 GHz
Core2 Q6600. I am not impressed, since the OpenSSL implementation which
came with the operating system (0.9.8g, from Ubuntu 8.10) is more than
twice faster on the same machine.
What happens here is the following: this implementation has been
hand-optimized in assembly, for the Opteron line from AMD. That code
seeks the optimal instruction scheduling, which happens to be awful on
the Core2, which is built by Intel, AMD's main competitor.
The extra width of the registers (64 bits) does not buy much here. That
optimized code (assuming that it does run fast on AMD processors)
accumulates the pseudo-random bytes into a register, so that it may
perform the final XOR with the data by full words. That XOR is not the
most expensive step in RC4 (the behaviour of the PRNG does not depend
upon the result of that computation, so the CPU abilities for parallel
evaluation kick in and the XOR is almost "free"). The core RC4
computation remains the byte-by-byte operation which defines RC4.
> Thanks! I'm actually particularly interested in the ARM9, now that I
> think of it.
My ARM test machine is an HP50g graphic calculator. It features an
ARM920T CPU (i.e. a kind of ARM9), clocked at 12 or 75 MHz (it
is rumoured that it can also be clocked at 203 MHz, but this reduces
battery life). It can be programmed in C with HPGCC: http://hpgcc.org/
(based on gcc-4.1.1). The C library is skeletal and non-conforming,
but benchmark of cryptographic algorithms can still be performed.
(The HPGCC web site appears to be down right now...)
I have some C implementations of RC4 and Skipjack lying around; I
will try to give it a shot this week-end.
> Skipjack certainly depends on 8-bit lookups.
These are lookups in a constant table, whereas in RC4 the table is
modified at each step. I think it changes things quite a bit in the CPU
pipeline.
--Thomas Pornin
Paul Rubin
> > http://perso.epitech.eu/~bevand_m/papers/rc4-amd64.html
> Mmmh, let's try: 141 MB/s, i.e. about 17 cycles per byte,
That's the openssl speed before they switched to the 64 bit version.
The amd64 version is about 2x speedup. Scroll most of the way
down, it says 322 MB/sec at 1.8 ghz, which is about 5.6 cycles/byte .
> The extra width of the registers (64 bits) does not buy much here.
I remember seeing an implementation (not clear if it's the one in the
link) that got quite a bit of speedup from the amd64's having 2x as
many registers as x86-32. It used the extra registers for allowing
more overlapping operations in a partially unrolled loop.
> My ARM test machine is an HP50g graphic calculator. ...
> I have some C implementations of RC4 and Skipjack lying around; I
> will try to give it a shot this week-end.
Thanks, that will be interesting. Can you also test Sosemanuk and/or
Salsa20/8?
Thomas Pornin
> The amd64 version is about 2x speedup.
No, I mean I tried the assembly version, described on the web page. On
my machine, it runs at 141 MB/s. I do _not_ obtain the promised 300+
MB/s, even though my CPU runs at 2.4 GHz and is supposedly faster than a
1.8 GHz Opteron. On the same machine, the plain OpenSSL which came with
the OS achieves about 295 MB/s. A crude, straightforward C-based
implementation of mine achieves 201 MB/s. A slightly less crude C-based
implementation, unrolled over four steps (accumulating 32 bits of RC4
output into a local 32-bit variable) achieves 284 MB/s.
Now let's put that "less crude" implementation into my HP50g. At 75 MHz,
it tops at 3.08 MB/s, i.e. a bit more than 24 cycles per byte.
Let's try Sosemanuk. The raw implementation submitted to eSTREAM
achieves 2.42 MB/s on that 75 MHz ARM CPU. The ARM CPU in the HP50g
happens to operate in little-endian mode, which allows for faster
decoding and encoding of (aligned) 32-bit words, but the Sosemanuk
implementation does not know that (it does not know that my ARM is
little-endian, and it does not know that I will use it only on aligned
data). If I tweak it a bit (just like I did with RC4, so it's fair),
I get 2.92 MB/s, hence about 25.7 cycles per byte.
So RC4 and Sosemanuk achieve roughly the same speed on my HP50g.
Now, about Skipjack. It is defined with big-endian access of 16-bit
words. I do not want to unfairly lose speed on endianness, so I am
cheating a bit and define Skipjack2, which is identical except for
endianness of input and output blocks. That's what I implement.
I get only 0.35 MB/s. That's more than 200 cycles per byte (ouch !).
That code was never really optimized (contrary to Sosemanuk code) and
straightforward implementation seems to leave some room for
optimization. Yet I think it is safe to claim that on that platform,
RC4 and Sosemanuk are intrinsically faster than Skipjack.
(All of there are with hpgcc-2.0SP2, which contains gcc-4.1.1.
Compilation flags include "-mtune=arm920t -mcpu=arm920t -mlittle-endian
-fomit-frame-pointer -mthumb-interwork -mthumb", and either "-O2" or
"-Os", whichever produces the fastest code. Note the use of Thumb mode.
Supposedly, that CPU has a 16 kB L1 cache for code, and another 16 kB L1
cache for data, so all these benchmark should fit in L1 cache, making
the HP50g memory architecture irrelevant.)
--Thomas Pornin
Phil Carmody
Clipper was an ARM chip. Clipper was also a crypto chip. I don't
think they were the same chip, that was just a coincidence.
Phil
--
Marijuana is indeed a dangerous drug.
It causes governments to wage war against their own people.
-- Dave Seaman (sci.math, 19 Mar 2009)