Let us call "sequential search" an algorithm that remembers which keys were tried and avoids trying them again, and "random search" an algorithm that just tries keys at random without bothering to check. The sequential search has the following problems: 1. The server is badly overloaded. It is vulnerable to a variety of active attacks: 2. "result hoarding" attacks: finding the result and reporting it "not found". 3. "dilution" attack: allocating some search space and not sweeping it. 4. plain old "denial of service" attack: deliberately overloading the server with bogus communications. 5. And of course all of the above in their "buggy software or hardware" versions. The random search has none of them: attacks 1 and 4: there is no server to overload attacks 2 and 3 are no worse than simply refusing to participate in the search, because the rest of the computation is independent of what any one party is doing. The main drawback of the random search is that the expected running "time" is the size of the key space instead of half the size for the sequential search ("time" here is the number of keys to try before finding the right one). In practice, because of server overload, our machines don't seem to be working more than half the time, so the random search could be actually faster than the sequential search. Even if it isn't, I think doing twice as much work is a good trade-off for protection against all attacks, and no more network or server problems, and no more allocation hassles for off-line users. Four more remarks: * I get the factor of two by assuming that the algorithm is "pick a segment at random, look for the key in it, pick a new segment at random, and so on". I suspect that sequential searching from a random starting point would be much worse in the case of many independent searchers. * I hope there's no bug in my math. * Another drawback is that the worst-case running time is infinite (but it is infinitely unlikely). * Of course, we need a good PRNG, but that's essentially what RC4 is. In conclusion, I think random searching is the way to go. It's even better than Monty's pre-allocation with quad-coverage. -- Damien
| Let us call "sequential search" an algorithm that remembers which keys were | tried and avoids trying them again, and "random search" an algorithm that | just tries keys at random without bothering to check. | | The sequential search has the following problems: | | 1. The server is badly overloaded. | It is vulnerable to a variety of active attacks: | 2. "result hoarding" attacks: finding the result and reporting it "not foun d". | 3. "dilution" attack: allocating some search space and not sweeping it. | 4. plain old "denial of service" attack: deliberately overloading the serve r | with bogus communications. | 5. And of course all of the above in their "buggy software or hardware" | versions. And there is the third alternative, hierarchical search, which distributes the task of giving out keys. This is admittedly a little bit more involved, of course. The SKSP had provisions for doing it hierarchically, as far as I understood it, although I might be wrong. What I wonder is wheter the server congestion really showed that the protocol is flawed. Handing out bigger blocks relieved the situation. I think this can be further improved if you do a couple more things. 1. The server knows approximately how many requests per second it can take, and tells the clients this information. 2. The client initially does a testrun, and determines how fast it runs. 3. Each client is handed a block that, given the approximate number of currently pending and active blocks out there, together with the calculation time of the client, will give an acceptable number of requests/time unit to the server. 4. The server acks (S-ACK) the block-ack to the client. If the client doesn't get an ack (S-ACK) from the server for its ack (B-ACK), it keeps the ack around til the next block is calculated, and sends this ack together with the new acks. 5. The server can hand out allocated blocks to others, for those blocks that has not been acked in three times the estimated calculation time. 6. If a client is unable to get a key allocation after a number of tries, it can chose a random block and search that. It can then be acked to the server. This may result in overlapping blocks, but this should not pose such a big problem, since most of the key space is searched in an orderly manner anyway. It would be very interesting if detailed statistics or the logfile of the server could be published somewhere. How many machines were involved? etc... /Christian
Having ACKs from the people cracking your SSL exchange is fun; it provides feedback on whether your code is working, allows the volunteers to see their name in lights, and gives you this nice warm feeling that progress is being made. In server-allocation schemes, it also provides an optimization: no need to hand out chunks that have been ACKed. Not having ACKs provides anonymity to those who are performing the crack. The only two agents who have issues of anonymity to consider are: the one presenting the challenge (and its prize), and the one that gets the solution (and its prize). Perhaps anonymity is unimportant for toy problems: so far, Hal has not complained that Agent 86's CCNs have been spread all over the Net. I can imagine a "real" challenge being a much more serious affair. Do you really want to be caught talking with www.brute.cam.cl.ac.uk for two days straight just before someone posts Louis Freeh's American Express number to alt.credit-cards.exploit? nathan
And there is the third alternative, hierarchical search, which distributes the task of giving out keys. This is admittedly a little bit more involved, of course. The SKSP had provisions for doing it hierarchically, as far as I understood it, although I might be wrong.
Indeed, it does, and we plan to provide a "local CPU farm" server which can be used when a number of machine are sharing the same ID.
What I wonder is wheter the server congestion really showed that the protocol is flawed.
No -- but that the early version of the code were buggy. As it is, 6 clients which are still running are managing to keep the server permanently busy. I think the protocol itself is OKish ..
Handing out bigger blocks relieved the situation.
Not really. It did however mean that when a chunk was allocated, three times as much work was done !
1. The server knows approximately how many requests per second it can take, and tells the clients this information.
Hmm -- hard to tell -- the *server* can take lots, but if the *clients* have problems, things go wrong. A select/poll server is not going to be tried on the next one -- that'll only be used if that goes slow as well ...
2. The client initially does a testrun, and determines how fast it runs.
The latest version of brloop starts with a call of "brutessl -q -t 1" to decide how big the chunks should be ...
3. Each client is handed a block that, given the approximate number of currently pending and active blocks out there, together with the calculation time of the client, will give an acceptable number of requests/time unit to the server.
I suspect that figures would be too crude ... The server would have to keep track of clients and how long their sessions take .... Should a client which takes 20s for a session be given blocks that take 20 times longer to process than one which manages it in 1s ?
4. The server acks (S-ACK) the block-ack to the client.
Sorry -- what does that mean ?
If the client doesn't get an ack (S-ACK) from the server for its ack (B-ACK), it keeps the ack around til the next block is calculated, and sends this ack together with the new acks.
Sorry -- I'm lost ...
5. The server can hand out allocated blocks to others, for those blocks that has not been acked in three times the estimated calculation time.
I've split allocation from ACKs. One server just doles out keys, the other just collects the ACKs. I don't want to add that sort of realtime feedback. What do you do about WWW clients ? What if someone grabe a big chunk, farms it out to several machines, and they ACK bits back ... ?
6. If a client is unable to get a key allocation after a number of tries, it can chose a random block and search that. It can then be acked to the server. This may result in overlapping blocks, but this should not pose such a big problem, since most of the key space is searched in an orderly manner anyway.
Again no realtime fedback from ACKs :-(
It would be very interesting if detailed statistics or the logfile of the server could be published somewhere. How many machines were involved? etc...
That'll come -- as the WWW pags says. pelase let me know what stats you'd like.
1. The server is badly overloaded.
Let's not get implementations confused with algorithms ... We were using ALPHA code when we started .... With BETA clients, a hierarchy and select/poll loops, I reckon a server would stand a chance.
It is vulnerable to a variety of active attacks: 2. "result hoarding" attacks: finding the result and reporting it "not found".
Sure.
3. "dilution" attack: allocating some search space and not sweeping it.
Un ACKed space is re-allocated after the first scan has completed.
4. plain old "denial of service" attack: deliberately overloading the server with bogus communications.
Few systems can resist such an attack !
5. And of course all of the above in their "buggy software or hardware" versions.
... causing them ... yes -- especially (1) !!
The random search has none of them: attacks 1 and 4: there is no server to overload
(4) is still applicable isn't it ? What tells people to stop, or do they go on for ever ?
attacks 2 and 3 are no worse than simply refusing to participate in the search, because the rest of the computation is independent of what any one party is doing.
(3) is just the same for the server -- it re-allocates. (4) would require a restart :-(
The main drawback of the random search is that the expected running "time" is the size of the key space instead of half the size for the sequential search ("time" here is the number of keys to try before finding the right one).
where "expected" is some loose average ..... My stats is *very* rusty, but I'd have thought it would be somewhat less than twice a linear search ... However, I agree that as a ballpark figure, yes: it would be somewhere between N/2 and N ...
In practice, because of server overload, our machines don't seem to be working more than half the time, so the random search could be actually faster than the sequential search.
IMPLEMENTATION !
Even if it isn't, I think doing twice as much work is a good trade-off for protection against all attacks, and no more network or server problems, and no more allocation hassles for off-line users.
random probing does indeed have its merits. Personally I'd go for a scheme whereby on finishing a random search, the client multicast a PGP signed message (there would be a WWW/email/telnet/... interface which would multicast for our non-connected members) allowing interested parties 1) to gather stats as to what actually happened 2) maps of "unsearched" areas to be built by anyone wanting to fill gaps 3) the "big boys" could learn to trust each other and use (2). 4) when all notified keys are tried, go in to killer mode, and try to find who is untrustworthy. Someone can only try it once, and getting a "big boy" tag takes a while, and a lot of CPU cycles !
I suspect that sequential searching from a random starting point would be much worse in the case of many independent searchers.
Convince me (please) .... What size "chunks" should be scanned ?
* Another drawback is that the worst-case running time is infinite (but it is infinitely unlikely).
See above ... the big boys will do it eventually ...
In conclusion, I think random searching is the way to go.
It has its advantages -- yes. Did you use it for Hal1 ? :-))
There are more effective solutions than simple random search, these have been known in the distributed processing arena for years. What you effectivelly have is a farmed solution to a problem with a high degree of trivial parallelism. Farms always suffer from the server bottleneck problem. The alternative is to use a multifarm, its a bit complicated to explain bu the essence is that you distribute the farmming mechanism. The most extreeme example of this is to have every slave also act as a master for some part of the problem. Since the bandwidth/processing ratio is unfavourable it would be better to have a small but non trivial (5-10) number of master controllers. The basic principles are to leverage pipelined parallelism, a slave does not simply ask for a chunk of keyspace, process it, return results and ask for the next chunk. Instead overlap work packages, give them more than one to work at at once so that the system does not suspend waiting on the server. Size the chunks adaptively, the more keyspace a processor works through the more packets it is given at once. Use integrity checks to ensure that the slaves are acting properly. One method of doing this is to keep secret part of the known plaintext (say 16 bits). A slave is required to report _all_ matches in the range to the master. Slaves who report a statistically low number of matches may be considered suspicious. It is a simple matter to allocate part of that keyspace to another processor for a double-check. [Its so obvious I'll apply for a patent on that technique] Another usefull technique is to require the slave to checksum some collateral result from the calculation mix. Then if its simply braindead software it can be detected. When running a multi-master farm it is important to realise that the slaves serve all the masters, not just a single one. Masters can distribute work chunks amongst themselves in larger chunks, as chunks are completed this is communicated to the other workers. If we used the Web as a substrate for this work the control software could then be used for other related tasks requiring large scale parallel processing on networked workstations. This was one of the original applications I looked at back in 1992 when I was doing an awful lot of this type of work. Phill Hallam-Baker
participants (5)
-
Christian Wettergren -
Damien.Doligez＠inria.fr -
hallam＠w3.org -
Nathan Loofbourrow -
Piete Brooks