"S1" encryption system (was: this looked like it might be interesting)
I suppose the unstated implication is that this might be Skipjack. I have looked at the program a bit and have a few observations: There is an obvious typo in the "g" function, whose first parameter should be 0 or 1, but which tests it for 0, 1, or 2. This suggests an amateur effort. The coding style in general suggests a lack of familiarity with C (absence of "for" loops, with equivalent "while" loops substituted). The program appears to be based on a hardware-based description of the algorithm, judging from comments and style. The algorithm uses two fixed arrays F and G. Comments indicate that F was designed as four independent arrays F0, F1, F2, and F3. These are suposed to be non-linear. Each takes 8 bits in and 8 bits out. G is two arrays, each 8 bits in and 1 bit out. The comments indicate that it is supposed to be "pseudo-linear". G1 is the odd parity function. G0[i] is 0 0 1 1 0 1 1 0 0 1 repeated over and over. This is unusual because it is period 10 (the second 5 bits are the inverse of the first 5). I don't know whether there would be a more concise algorithmic representation of G0. Key size is 80 bits. The program implements the ability to hold 5 keys at once. Block size is 64 bits. The keys are expanded internally into a large array. I haven't looked at the key scheduling in detail. The encrypt and decrypt block functions have fixed xor's applied to the 64 bits of input and output. This appears to be cryptographically useless (or at least not very useful), similar to the initial permutation in DES. It is curious that xor's are used here rather than a permutation. That may represent an attempt to design the cipher to run well in software. The encryption function itself is a modified Feistel type cipher, with the blocks broken into 8 pieces and xor'd with functions involving F, G, the key and other pieces in a reversable pattern. The loop iterates 32 times but only two of the 8 pieces are changed each iteration so each 8 bit piece actually gets modified only 8 times. The pattern is: piece 6 modified by pieces 4, 5, 2, 3 piece 7 modified by pieces 4, 5, 0, 1 piece 0 modified by pieces 6, 7, 4, 5 piece 1 modified by pieces 6, 7, 2, 3 piece 2 modified by pieces 0, 1, 6, 7 piece 3 modified by pieces 0, 1, 4, 5 piece 4 modified by pieces 2, 3, 0, 1 piece 5 modified by pieces 2, 3, 6, 7 repeated 8 times. Decryption goes in the inverse order as is typical of these ciphers. The key is basically 80 bits, however there is a function S1_create_key which pads it with 16 bits of 0 and then encrypts it with two overlapping encryptions using the all-zeros key. The resulting 96 bit key is then fed as input to S1_load_key which decrypts it and checks for the 0's to ensure validity. I am not much of a cryptanalyst, but from what I understand the overall security of a Feistel-type cipher like this depends a great deal on the structure of the F (and in this case G) boxes. I would not be at all qualified to analyze those. So potentially this may be a strong cipher or it may be weak. The actual implementation does as I remarked show some signs of amateur programming skills. In addition to the points mentioned it is curious that the G arrays are initialized with a list of 256 values rather than taking advantage of the apparent regularities noted. Hal Finney hfinney@shell.portal.com
In message <199508092259.PAA10092@jobe.shell.portal.com>, Hal writes:
I suppose the unstated implication is that this might be Skipjack.
I don't suppose anyone has access to Skipjack to verify or refute this claim? [...much intresting analisys deleted...]
In addition to the points mentioned it is curious that the G arrays are initialized with a list of 256 values rather than taking advantage of the apparent regularities noted.
It is fairly simple to cut & paste 10 values ~25 times, it is harder to write and verify code to initilize the array. More intresting is that Gx[i % 10] is faster then a stright index on many systems (anything you could expect cache line conflicts or cache capacity overfills on, and supports a modulis signifigantly faster then the first few parts of the memory hierachy). Also note that the code may have been written from a dissasembled binary rather then a hardware spec. [...]
Hal Finney hfinney@shell.portal.com
Hal writes:
I suppose the unstated implication is that this might be Skipjack.
I have looked at the program a bit and have a few observations:
....
The encryption function itself is a modified Feistel type cipher, with the blocks broken into 8 pieces and xor'd with functions involving F, ...
Someone sent me (to my bell labs address) a copy of this this afternoon via an anon server in the netherlands. It looks like others got it as well, and it appears to have been posted to the cypherpunks list, though it hasn't yet shown up here from the list (my mail seems to be slow today). Did anyone else have a copy mailed directly to them? I don't quite know what to make of it. A couple of random quick first-order observations: The code appears to have been translated from some other language by someone not skilled in C. Hal noted the lack of "for" loops where they are obviously called for, and at least two odd bits of code that appear to be bugs, at least one of which one would suspect would cause it to fail to interoperate with correct implementations (if we are to assume the "correct" cipher uses the entire key schedule). Also note the awkward assignement to the F and G tables. S1 could suggest Skipjack, but it is also a pretty generic name for a cryptosystem. I thought Skipjack (like most other NSA cryptosystems) is SECRET, not TOP SECRET, but on the other hand this appears to be part of some kind of "secondary analysis" package, whatever that is, so if this is really spook stuff, the TOP SECRET designation could be reasonable. The cipher is similar in some ways to one designed by Bruce Schneier and I last year (MacGuffin, described in ftp://research.att.com/dist/mab/mcg.ps ). In particular, note that in each of the 32 rounds, 16 bits are operated on by 48 (or 40, depending on the effect of the G function). There is at least one novel feature - the G function used to select which F's (Sboxes) to use. I've not seen this before. The cipher appears to be designed for software implementation (byte oriented, etc.). The software, on the the other hand, goes to some trouble to emulate a hardware interface, as if it were written to be dropped in to some pre-existing code or library. The F outputs are not uniformly distributed. In fact, some outputs appear far more often than others (I base this on running "grep|wc", not on any real analysis.) What a strange key schedule. The "family" XOR business at the begining and end suggests RSA's DESX. The lanuage in the comments suggests that it's there to allow for non-interoperable "families" of users. GOST has similar features, though GOST couples this more closely to the cipher's internal structure. As far as I know, no one has EVER leaked TOP SECRET material cryptosystem in this way, so I'm very skeptical. But there's always a first time. I don't know what to believe. If this is a real, classified cryptosystem, it would be a very unusual first. On the other hand, if this is a hoax, whoever did it appears to have gone to some trouble, and has included some interesting design features. A third possibility, if we are to believe the spook markings, is that it is a re-implementation of someone else's cryptosystem, created for the purpose of cryptanlysis. All in all, I remain very skeptical. It smells like a hoax to me, but I'm willing to look at it with an open mind. -matt
On Wed, 9 Aug 1995, Matt Blaze wrote:
I don't know what to believe. If this is a real, classified cryptosystem, it would be a very unusual first. On the other hand, if this is a hoax, whoever did it appears to have gone to some trouble, and has included some interesting design features. A third possibility, if we are to believe the spook markings, is that it is a re-implementation of someone else's cryptosystem, created for the purpose of cryptanlysis.
Two other possibilities: (1) It's merely an independently produced cryptosystem disguised as a "leak" to save its creator the trouble of asking experts to analyze it for him/her. (2) It's a misleading / intentionally "wrong" version of something, "leaked" by a government official of whatever ilk to precipitate a legal investigation of Cypherpunks, remailers, etc. (ie to show a judge to get wiretaps, etc.) I'm skeptical of (2), but it occured to me, and one can't be too safe... Jon ------------------------------------------------------------------------------ Jon Lasser <jlasser@rwd.goucher.edu> (410) 494-3253 Visit my home page at http://www.goucher.edu/~jlasser/ You have a friend at the NSA: Big Brother is watching. Finger for PGP key.
Jon writes:
Two other possibilities: (1) It's merely an independently produced cryptosystem disguised as a "leak" to save its creator the trouble of asking experts to analyze it for him/her.
It strikes me as rather foolish to mail off anonymous copies to several individual recipients (Matt, Perry, Tim, ...) in addition to the list, if S1 is a real leak. Why aid the traffic analysts by firing off multiple messages through the remailers ? BTW, the code has been posted to Usenet by a Frank Falstaff -- look for message ID <40b8tk$cj4@news.xs4all.nl> in sci.crypt (Wed, Aug. 9, 1995). His article refers to a message ID (namely <40b50l$oa8@utopia.hacktic.nl>) that differs from the message ID of the copy sent to c'punks. So it looks like there was at least one additional recipient. That's a minimum of 5 originals so far.... -Futplex
On a fair number of occassions I have been told that federal type folks have made statements to the effect that there is no such thing as a "TOP SECRET" classification of US government docs. Since really secret things tend to get neither confirmed nor denied, I am inclined to believe this. Thus SECRET is the top classification in today's government/military. If anybody knows otherwise I would be interested in the information. JWS
On a fair number of occassions I have been told that federal type folks have made statements to the effect that there is no such thing as a "TOP SECRET" classification of US government docs. Since really secret things tend to get neither confirmed nor denied, I am inclined to believe this. Thus SECRET is the top classification in today's government/military. If anybody knows otherwise I would be interested in the information.
JWS
Well, I don't hold (and have never held) a clearance, but I've seen declasified/sanitized documents that have crossed out "TOP SECRET" markings all over them. -matt
participants (6)
-
futplex＠pseudonym.com -
Hal -
Jon Lasser -
Josh M. Osborne -
Matt Blaze -
solman＠MIT.EDU