Re: RC4 crack

Robert Hayden <hayden@krypton.mankato.msus.edu> writes on cpunks:
> So what was the result of the RC4 key cracking thing that happened last 
> week?  It's at 100% but that's all it says.

[I answered this in email but the answer is: all will be told soon]

A brief explanation is called for, basically the 100% is %age
allocated, and there are still a few stragglers being swept.

For a brief explanation have a look at the brute-rc4.html page which I
have now updated:

	http://dcs.ex.ac.uk/~aba/brute-rc4.html

A more detailed report will be posted to cpunks when the last keyspace
has been swept.

We are expecting that no key will be found at this stage, as it was
not sure to being with that the supplied plaintext/ciphertext was a
correct pair of RC4-40.  Lack of open Micro$oft specs on the workings
of Micro$oft Access meant that we were guessing, and hoping that we
got it right.  The original brute rc4 project was started on the basis
of 'lets brute it and see'.  Looks like nothing will come out.

Several folks have various parts of an RC4 SSL bruter (netscape secure
sockets layer) and are working on sockets based farming tools to allow
this one to be more automated, as there have been key space management
problems with the bruterc4 effort.  Also means a better % of idle time
will be soaked on particpating machines, as we will not need to wait
for operators to get in the next morning, or rely on people to
remember which space they have swept to paste back into the confirm
box.

Soon ( a week maybe ) the respective parties hope to have all this
sorted out, and get ready for a SSL breaking effort.

So outcome of RC4 soon, followed by SSL effort announce in a while.

In the RC4 outcome announce will be a % break down of how much compute
people swept, even some folks on single PCs have swept as much as 1%
of keyspace alone in 1 week.

Adam

-----BEGIN PGP SIGNED MESSAGE-----

On Mon, 17 Jul 1995 aba@atlas.ex.ac.uk wrote:

> Several folks have various parts of an RC4 SSL bruter (netscape secure
> sockets layer) and are working on sockets based farming tools to allow
> this one to be more automated, as there have been key space management
> problems with the bruterc4 effort.  Also means a better % of idle time
> will be soaked on particpating machines, as we will not need to wait
> for operators to get in the next morning, or rely on people to
> remember which space they have swept to paste back into the confirm
> box.

I remember when RSA129 was being done, the program you have you manually 
get a start location, and then email transparent any results that it 
got.  The program that doled out areas to search would base those on what 
had already been mailed in.  I don't know the details of how exactly that 
worked, however.

But, if the program could be written in such a way that it was all 
automatic, mailing in results and automatically (maybe via a telnet 
port?) getting the information about what to search, that would be most 
nice. 

I'd basicly like to be able to start the program, nice it, slam it in the 
background, and forget about it.

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: PGP Signed with PineSign 1.0

iQCVAwUBMArF9DokqlyVGmCFAQGf7gP/QCJFRsBUJ7IRoKzheKeFXvFpjRxeJn11
n8DJbMlMaDoH6AIm49LrHI/fXmdlm8A9hrBMSemD7+HmImxSZmx2InS07eni4Khs
j7Npqen2VTOHfr1RBDqUpzUv4FXVciYVLvQs4gzUhEIOjeN4iVhboUm/pBhaj4s4
3IKPuxIovwQ=
=QR/m
-----END PGP SIGNATURE-----
 
____        Robert A. Hayden      <=> Cthulhu Matata
\  /__          -=-=-=-=-         <=>          -=-=-=-=-
 \/  /  Finger for Geek Code Info <=> hayden@krypton.mankato.msus.edu
   \/   Finger for PGP Public Key <=> http://att2.cs.mankato.msus.edu/~hayden

> I remember when RSA129 was being done, the program you have you manually 
> get a start location, and then email transparent any results that it 
> got.  The program that doled out areas to search would base those on what 
> had already been mailed in.  I don't know the details of how exactly that 
> worked, however.

Yeah it's quite like that except we're going for sockets, and an SMTP
style protocol.  That way people can write other apps to the protocol,
for instance Andy Brown has an SSL bruter and key management s/w for
NT, and he plans to interface to the 'master' software via this socket
protocol, allows intermixing, so some people will be running direct
IP, others with PCs or behind firewalls will be running via the WWW
interface which also talks the SMTP style stuff to the master, and it
would be possible if desired to write an email gateway to the socket
protocol for interacting with the master.

Also the socket protocol (blame Piete for this clever stuff, and most
of the socket protocol design) is planned to work with arbitrary
levels of masters, so you can start a local master say on your local
network, the local master requests keys of the 'big master', and doles
them out to 'slaves' running on each cpu you have.  When all it's
slaves have acked the keyspace it has drawn out from the big master,
it'll ack that bigger keyspace with the bigmaster and draw out some
more keyspace.

> But, if the program could be written in such a way that it was all 
> automatic, mailing in results and automatically (maybe via a telnet 
> port?) getting the information about what to search, that would be most 
> nice. 

Yep a telnet port is it for both reporting and getting keys, also the
WWW interface to the same.

> I'd basicly like to be able to start the program, nice it, slam it
> in the background, and forget about it.

Right, niceing seems to be one option another is to suspend it whilst
people are directly logged in, Kevin and some others have tools for
this kind of thing.  Also there was a similar ultra-nice batch job
suspender which came with RSA129, which we might pinch/combine.

The problem with nicing is that most unix schedulers don't seem to
know what nice means,.. you still get a noticable slow down on
interactive jobs on SGI boxes even if you've got it npri -h 150, and
even though the bruterc4 (and the bruteSSL too) have tiny resident
core sizes).  Also we thought there should be an hours of play option
so you can tell it (the slave) when it is allowed to hammer the
machine, say 6pm - 7am or whatever.

So, yes the idea that you can slam it in the background and forget it
is a very nice one as it ensures max resource usage.  Also it would
allow us to setup a semi-permanent key cracking ring, with slaves that
can support cracking both SSL and RC4, plus whatever anyone else adds
later, you would get to install a new "ability" then your machine
would say know how to do relations for a RSA-512bit or whatever.

Interesting to see how many MIPs can be mustered en masse for this
kind of app.

Adam

> I remember when RSA129 was being done, the program you have you manually 
> get a start location, and then email transparent any results that it 
> got.  The program that doled out areas to search would base those on what 
> had already been mailed in.  I don't know the details of how exactly that 
> worked, however.

Not quite.  The UIDs that were given out for RSA-129 had nothing to do
with the search space.  The reason is that RSA-129 did not search for
the prime factors; it searched for quadratic residue relations.
Moreover, ANY relations within the space is a valid datapoint.  As a
result, the UIDs ojnly told the factoring clients where to start
looking for relations.

You can effectively think of it as a seed to a random number
generator.  So long as everyone has a different seed, they will get
different random numbers.  Thats what the UIDs did; provided each
client with a different starting point.

You had to get a new UID for each run of mpqs because starting over
with the same uid would re-run all the checks you've already done.
Why double-run when UIDs are cheap?  You see, unlike the RC4 crack,
there was no relation between the UIDs and the relations returned.

As the person who wrote the UID returning script, I can tell you that
all it did was keep a file with the last UID given, and when an email
requests came in, it would create a lock on that file, return the last
UID+1 through the number of UIDs requested, and then update the file.
There was no basis of the relations received.  In fact, the UID
responder could have been run on any machine -- it could care less
about the data returned.

> But, if the program could be written in such a way that it was all 
> automatic, mailing in results and automatically (maybe via a telnet 
> port?) getting the information about what to search, that would be most 
> nice. 

The point of runfactor was to allow you to obtain a large segment of
UIDs and dole them out locally.  Since there wasn't a relation between
UID and data returned, then it didn't matter if some UIDs never
returned.

For RC4, you _have_ to search everywhere.  Therefore, you would want
to make runfactor an interactive program that contacted a central
server whenever it wanted to get some search space.  I dont think this
would be very hard to write.

-derek

-----BEGIN PGP SIGNED MESSAGE-----

On Mon, 17 Jul 1995, Derek Atkins wrote:

> Not quite.  The UIDs that were given out for RSA-129 had nothing to do
> with the search space.  The reason is that RSA-129 did not search for
> the prime factors; it searched for quadratic residue relations.
> Moreover, ANY relations within the space is a valid datapoint.  As a
> result, the UIDs ojnly told the factoring clients where to start
> looking for relations.

Thanks, I stand corrected.  As I said, I really don't understand at a 
basic level how it works.  These factoring projects are, to me, an 
interesting sociological experiment.  Of course, to do this correctly, 
you need software that is easy to use. :-)

So, the ability to run a program in such a fashion that as much is 
automated as possible is a "Good Thing{tm}".


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: PGP Signed with PineSign 1.0

iQCVAwUBMArjMjokqlyVGmCFAQHrdgP+NzpimLDgMY0/HMk8CVu4iaqmCdljxLLv
+G6k3CkkiCvowLTEHv45NUaixWl38VgeMnp2vxOPVFcb5lEdHLd2DqXL4vj7sjg1
rWAIX4/Q+/KL98ATCw9+ePs+CFSM3HAkRWT6sNmmAJyHj6y13Yk3Fa9qY5Gt5kO3
8wqSPO2aOYE=
=1ZOw
-----END PGP SIGNATURE-----
 
____        Robert A. Hayden      <=> Cthulhu Matata
\  /__          -=-=-=-=-         <=>          -=-=-=-=-
 \/  /  Finger for Geek Code Info <=> hayden@krypton.mankato.msus.edu
   \/   Finger for PGP Public Key <=> http://att2.cs.mankato.msus.edu/~hayden