Thanks for the clear answers! On 1/6/10 7:52 AM, sascha wrote: > On Wed, Jan 06, 2010 at 05:40:41AM +0100, M vd S wrote: > >> - is it correct that the table-generation software as distributed will >> only compile / run / be of use for people having Cell or CUDA machines? >> I have loads of spare x86 cpu time and it bothers me I can't seem to >> contribute or experiment a bit. (and unfortunately those fancy nVidea >> things won't fit in every 1U rack server nor in a laptop...) >> > > there will be support for SSE, nvidia, cell and ati. SSE being the smallest > of the family and the most power-hungry. > > Is the SSE version a work in progress already? The svn source tree lists only /cuda under /devices, assuming that's where I should look.
If so, were can I find it? If not, would it be an idea to at least prop up a working (slow) C version (suitable for whatever architecture), which could be made SSE-aware in a next stage? SSE might be relatively slow, but multicpu multicore Xeons are abundant nowadays so it would allow a larger share of the community to join in and still contribute significantly. The chain generating code must be available anyway to people not owning graphics cards, in order to look up a chain. >> and one relating to A5/1 itself: >> (http://reflextor.com/trac/a51/wiki/A5/1Basics) >> - If I understood the wikipedia page on A5/1 correctly, the algorithm >> gets Key+Frame Number as input and generates 2*114 bits of keystream, >> enough for one burst up/down. Am I right that this is not entirely >> clear, in that the algorithm goes on serving keystream bits for bursts >> following, without (ever) being re-initialised with a new Frame Number >> before the call ends? (otherwise I can't see why having the internal >> state lets you decode the entire conversation) >> > > The A5/1 state gets initialized with Kc and the frame number at the start > of every burst. Since Kc is constant for the duration of a connection and > you can easily compute Kc from the A5/1 state, you can decrypt every burst > of that connection after having brute forced a single A5/1 internal state. > > Is it that easy? You have to reverse step between 100 and 150 rounds, where in every step there are 4 possible shift-permutations (the majority rule thing, combinations 1+2, 2+3, 1+3 and 1+2+3). Has this been verified? Considering the clock bits, and the 3 bits left of them (that's 1<<6=64 combinations), based on some back of the envelope coding: - in 24 of 64 cases there is no valid prior state (example: clock bits = 010 and left to them = 101) - in 26 of 64 cases there is exactly one valid prior state - in 6 of 64 cases there are two valid prior states - in 6 of 64 cases there are three valid prior states - in 2 of 64 cases there are four valid prior states (these are: clock bits = 111 and left to them = 000, or vice versa) On average there is one state that leads to the state you observe, so it shouldn't explode. But still you would get about 57 to 86 possible states on average at the point where majority clocking is not performed anymore and it turns deterministic. (after 100 to 150 rounds of reverse clocking respectively) So you'd get 70 Kc candidates on average for every single A5/1 internal state you'd brute force. Which is a number small enough to just try on other bursts and assess validity by simply "listening" to the decoded audio or by some other means to assess validity of decoded data. Right? If so, I would be happy to update the wiki on http://reflextor.com/trac/a51/wiki/A5/1Basics - but how? I registered but can't seem to edit anything there. Kind regards, M. _______________________________________________ A51 mailing list [email protected] http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
