"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

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 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

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

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
>