An on-topic post (*gasp*)

[Scott Fluhrer]

Well, Greg Rose just left (sigh), and while part of the reason was the a
large amount of traffic between a crank and his detractors, the other part
was that there wasn't much traffic other than that.

So, I thought I'd mention something that was on-topic; some research I've
been doing.

Someone (Ixgr from crypto.stackexchange.com; I don't know his (or her) real
name) suggested to me that, because of the known distinguishers on RC4, that
if you were given a large number of encypted messages which all had the same
plaintext, you might be able to recover the plaintext. The scenario that he
was thinking of was an SSH-protected login sequence; where the two sides
negotiate a set of random RC4 keys, and then exchange passwords encrypted
with RC4. The idea is that the password appears in exactly the same
position in the encrypted stream; if you could record a large number of
encrypted exchanges, could you recover the password.

So, what I did was pick a password of 16 characters, and encrypted that with
a large number of keys (using RC4/Drop-512; that is, I would discard the
first 512 bytes of the RC4 key stream, to avoid the known analomilies at the
start of the keystream).

I then collected statistics on all those encrypted messages, and by using
the known RC4 variances from randomness in
http://www.mindspring.com/~dmcgrew/rc4-03.pdf (table 3, in particular), I
was able to recover the password with 8 billion encrypted messages.

8 billion encrypted streams are a lot; however, I was able to get some
partial information (correct guesses on, say, a 4 character subset of the
password) after 4 billion encrypted streams.

Because of this, it would sound prudent to avoid RC4 if you're going to
protect the same login sequence a huge number of times. Now, it might be
prudent to avoid RC4 altogether; this just demonstrates yet another
vulnerability.

I'll be writing up an eprint summary on this.

--
poncho

[Thomas Pornin]

According to Scott Fluhrer <sflu...@ix.netcom.com>:

> Because of this, it would sound prudent to avoid RC4 if you're going to
> protect the same login sequence a huge number of times.

A scenario for that is an emailing client which regularly (e.g. every
minute) talks to a POP+SSL server. This is the kind of setup which was
used to demonstrate effectiveness of padding oracle attacks with CBC,
about ten years ago (by Vaudenay, I think).

One login a minute is "only" 1440 logins per day, so it will not reach
four billions, but it is still worth mentioning.


By the way, could you get some further data by comparing streams for
distinct people ? For two given users, the XOR of their respective
passwords will be fixed.


--Thomas Pornin

[Thomas Pornin]

According to Thomas Pornin <por...@bolet.org>:

> By the way, could you get some further data by comparing streams for
> distinct people ? For two given users, the XOR of their respective
> passwords will be fixed.

Forget about that, it is a bad idea (given a set of streams for one
password, the attacker could generate his own set of streams for a
password he chooses arbitrarily, so comparing streams cannot yield more
information that what the attacker could obtain by observing streams
for a single password).


--Thomas Pornin

[Scott Fluhrer]

"Thomas Pornin" <por...@bolet.org> wrote in message
news:50253a03$0$16487$426a...@news.free.fr...

> According to Scott Fluhrer <sflu...@ix.netcom.com>:
>> Because of this, it would sound prudent to avoid RC4 if you're going to
>> protect the same login sequence a huge number of times.
>
> A scenario for that is an emailing client which regularly (e.g. every
> minute) talks to a POP+SSL server. This is the kind of setup which was
> used to demonstrate effectiveness of padding oracle attacks with CBC,
> about ten years ago (by Vaudenay, I think).

Yes, it was Serge Vaudenay.

>
> One login a minute is "only" 1440 logins per day, so it will not reach
> four billions, but it is still worth mentioning.
>
> By the way, could you get some further data by comparing streams for
> distinct people ? For two given users, the XOR of their respective
> passwords will be fixed.

As you pointed out, that doesn't work. What you might be able to do is
check is get a good guess as to whether they share a password. I haven't
done any detailed analysis, but looking at the raw data, I suspect you might
be able to do that with 2-4 billion sessions from each (and, of course, if
they do happen to share a password; you can use the data from both to try to
recover the common password).

--
poncho

[xxein]

On Aug 10, 1:56 pm, "Scott Fluhrer" <sfluh...@ix.netcom.com> wrote:
> "Thomas Pornin" <por...@bolet.org> wrote in message
>
> news:50253a03$0$16487$426a...@news.free.fr...
>

> > According to Scott Fluhrer <sfluh...@ix.netcom.com>:

> >> Because of this, it would sound prudent to avoid RC4 if you're going to
> >> protect the same login sequence a huge number of times.
>
> > A scenario for that is an emailing client which regularly (e.g. every
> > minute) talks to a POP+SSL server. This is the kind of setup which was
> > used to demonstrate effectiveness of padding oracle attacks with CBC,
> > about ten years ago (by Vaudenay, I think).
>
> Yes, it was Serge Vaudenay.
>
>
>
> > One login a minute is "only" 1440 logins per day, so it will not reach
> > four billions, but it is still worth mentioning.
>
> > By the way, could you get some further data by comparing streams for
> > distinct people ? For two given users, the XOR of their respective
> > passwords will be fixed.
>
> As you pointed out, that doesn't work.  What you might be able to do is
> check is get a good guess as to whether they share a password.  I haven't
> done any detailed analysis, but looking at the raw data, I suspect you might
> be able to do that with 2-4 billion sessions from each (and, of course, if
> they do happen to share a password; you can use the data from both to try to
> recover the common password).
>
> --
> poncho

xxein: Why not use the message itself to provide the key? Every
message would change the key. You could use a set en-decrypt program
without fear because any missed interception would break he chain.
Any followers would loose the connection after one prearranged a
message sent from and to some neighbor's computer. You could
initialize it that way and continue from your own computer without
fear of decrypt even if the interloper had the program.

You could change several parameters within the program by message for
each contact. Back and forth. Billions of combinations at least.
But it has to maintain the chain for each contact. This program for
me and Jim. This program for me and Francois etc.

A little extra work to find out who sent you a message but it is
secure. Only you and your recipient will be able to follow a zillion
combinations.

You can even send the same message repeatedly with an unlimited amount
of re-encryptions from the program and visa versa. The program has
the basic function of human intel. Does it look like a plaintext.
Just encrypt or decrypt again until it shows up. This was it's basic
function in design. But I saw that it needed much more security even
after the NSA couldn't decrypt a threat (although mild).

So I devised the more secure chain unbreaker technique describe
above. The chain can equal more than a mere billion combos. All from
a simple program.

The program works almost instantaneously. But you will have to keep
track of it for each contact.

[Karl-Uwe Frank]

Even if this now is way of topic:

Yes, but we might could get it much simpler. Just add an address book,
protected with the master password of the user to the program. Inside
the address book the contact related passwords are stored. Now on each
message exchange the passwords are changing and stored inside the
address book with the contact names. Therefore no extra program is
necessary. And therefore, as you explained, even if Bob talk to Alice
the password is different from the one used when Bob talk to John and
from John's when he is talking to Alice and so on ...

Cheers,
Karl-Uwe