info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
The S-1 Algorithm
259 views
Skip to first unread message
Paul Rubin
Sep 6, 1995, 3:00:00 AM9/6/95
to
In article <42ka03$b...@blackice.winternet.com>,
Bruce Schneier <schn...@subzero.winternet.com> wrote:
>Which leaves us precisely nowhere. The most likely explanation
>is that it is a hoax, but I am hard-pressed to imagine a hoaxer
>with the requisite combination of skills, resources, and
>attitude. I also don't believe that it is SKIPJACK. It might be
>a preliminary design for SKIPJACK, but if both the key schedule
>and F-table entries are wrong, we really haven't learned
>anything. If we suddenly discovered that unbalanced S-boxes are
>far superior to balanced ones, then all best are off.
Bruce Schneier <schn...@subzero.winternet.com> wrote:
>Which leaves us precisely nowhere. The most likely explanation
>is that it is a hoax, but I am hard-pressed to imagine a hoaxer
>with the requisite combination of skills, resources, and
>attitude. I also don't believe that it is SKIPJACK. It might be
>a preliminary design for SKIPJACK, but if both the key schedule
>and F-table entries are wrong, we really haven't learned
>anything. If we suddenly discovered that unbalanced S-boxes are
>far superior to balanced ones, then all best are off.
If we continue speculating that S-1 might have something to do
with the real Skipjack, we might as well assume that the actual
F-box from the posting has nothing to do with the real one.
After all, it is supposed to be a chip simulator rather than
an encryption tester, and we already know the real F-box is
programmed into the Clipper chip *after* the chip is fabbed.
So the numbers in the F-1 posting could have just been taken
out of the phone book or anywhere else, with no attention to
their balancedness or unbalancedness. Nobody cared about their
cryptographic properties at all. The same goes for the G-box:
David Wagner's attack depended on the specific G-box from the
posting, but the real G-box could be entirely different.
Bruce Schneier
Sep 6, 1995, 3:00:00 AM9/6/95
to
I was in Europe while S-1 was posted, so I missed most of the
discussion. Better late than never....
Over the last year, I have spent considerable effort collecting
SKIPJACK information. I have gone through the published
literature, the rumors, and a large stack of documents received
by EPIC through Freedom of Information Act (FOIA) lawsuits.
At Crypto last week I gave a Rump Session talk entitled "Reverse
Engineering SKIPJACK from Open Sources." I prepared the slides
before I left for Europe. Here is what I said:
What the government told us:
Single-key block cipher.
Can be used in ECB, CBC, CFB, or OFB.
64-bit block size.
80-bit key size.
What the review committee told us:
32 rounds.
No weak keys (like DES has).
No key complementation property (like DES has).
What the hardware specifications tell us:
The latency of the Mykotronx chip has 64 clock cycles.
This means two clock cycles per round.
Assorted rumors (excuse me if I don't reveal sources):
SKIPJACK does not have rounds in the same sense that
DES does: i.e., half of the text block is not
encrypted in each round.
SKIPJACK has half the total S-box data as DES.
SKIPJACK has a 48-bit internal structure analogous to a
32-bit internal structure in DES.
The masks for the Clipper/Capstone chip are
unclassified and the chips can be produced in an
unclassified foundry. Part of the programming in
the secure vault includes installing part of the
SKIPJACK algorithm. The part of the algorithm
installed in the secure vault are the "S-tables",
suggesting that perhaps unprogrammed Clipper chips
can be programmed to implement other 80-bit key,
32 round ciphers.
Trying to puzzle out the meaning of the third rumor, Matt Blaze
and I invented something called an Unbalanced Feistel Network.
These are Feistel networks where the source and target blocks are
of different size. For example, in each round 48 bits might be
used as an input into the F function, and produce 16 output bits
to be XORed with the remainder of the bits. We called this a
48:16 UFN, and we proposed a design at last year's Algorithms
Workshop in Leuven. Our design was broken, but I am still
examining the structure. A 48:16 UFN satisfies the first and
third rumor above, and I think it as good a guess as any
regarding SKIPJACK.
A few months ago, I found some additional information in the form
of documents released under FOIA. One document was a Mykotronx
design review for "Project Capstone" dated 10 December 1991. The
design review was unclassified. Among the details about the
modular multipliers and the SHA code was the following page about
SKIPJACK:
ECB Processing Rate
2 clocks per G-Box operation
x 1 G-box per shift
x 32 shifts per ECB encryption
______________________________
64 clocks per ECB
64 clocks per ECB / 64 bits out per ECB = 1 clock per bit
Yields 40 Mbit encryption using a 40 MHz clock.
The only other thing I found was a SECRET memo. The organization
name (either from or to) is blacked out. The date is 25 August
1992. The subject is "SKIPJACK Revision." Paragraph 2 is
blacked out, but paragraph 1 reads:
1. (U) The enclosed Informal Technical Report revises the
F-table in SKIPJACK 3. No other aspect of the algorithm is
changed.
That's it. Rounds are called "shifts," which seems to indicate
that they are not "rounds" in the DES sense. A shift consists of
a "G-box" operation, which includes not only what we call the F-
F-function but the XOR as well. And there is something called an
F-table, which could be a table of constants or perhaps a table
of functions. In any case, it is something that can be revised
without changing the rest of the algorithm.
Now let's look at S-1. The most probable explanation is that it
is a hoax. But it is a very good hoax:
The hoaxer knew enough about algorithm design to make a
cipher that was not obviously lousy, while at the same
time not unduly complicated. The hoaxer knew enough to
make a design that included three novel ideas not seen
anywhere else: S-boxes that are created according to no
known criteria, a G-table that chooses a rotation of
S-boxes to use in a given round, and a bizarre key
schedule.
The hoaxer knew enough about how algorithms are used in the
military to make a spookish interface. I am
particularly interested in the "zeroize" function, the
separation of the key creation and key loading
functions, and the key masking. Blaze said that the
interface was similar to the Fortezza interface, but
not the same.
The hoaxer knew about Blaze's and my MacGuffin paper and
that we thought SKIPJACK was a 48:16 UFN. We made no
secret about this, and our paper is on Blaze's web
page. The hoaxer knew to use the term F-table. I
haven't shown many people what I found in EPIC's
documents, so the hoaxer either had to look through
them himself or get them by some other means (maybe an
independent FOIA request).
It's not a perfect hoax, though. The classification markings
look odd: NSA algorithms are SECRET, not TOP SECRET, and the
codeword restriction sentence is strange. The key schedule is
hopelessly flawed (David Wagner posted an attack to sci.crypt).
The coding style is amateurish, like it was translated from one
language to another. (Maybe this is clever on the hoaxer's
part.) And there's even a typo in the code.
And maybe the hardware latency is wrong. Clearly the design
facilitates parallelization. You can precompute all possible F-
table outputs in previous shifts, and then use the G-table result
to select between them; I am not sure you can get a shift down to
two clock cycles. I don't have the hardware background, and
would appreciate comments from others.
And why are there not bitwise permutations? If SKIPJACK is
designed for hardware, it makes sense to put them in. They're
free, after all.
Anyway, it's a real good hoax. Blaze estimated that he could
have done it, but it would have taken him a month of effort. I
agree with his assessment: one man-month. It's a lot of time to
spend on a hoax, especially one where the hoaxer doesn't get any
credit.
So, maybe it's SKIPJACK. It has a 64-bit block size and an 80-
bit key size. It's a 48:16 UFN with 32 rounds (or shifts, or
whatever). And it has an F-table. This is really interesting,
because the structure really is an S-box. Everyone knows it's an
S-box, and it makes no sense for a hoaxer to call it something
else. But in S-1 it's called an F-table. (I think this is very
significant, but others find it less convincing.)
And the F-table has been revised at least once. In the code it
says that the F-table entries "differ in the S-2 version." The
code is dated 1 February 1989 and 31 July 1991, and I have a memo
dated 25 August 1992 that says the F-table has been revised in
"SKIPJACK 3." Pretty convincing, I think. (Of course this means
that we can't confirm anything by testing the hardware, since the
F-table entries are different.)
Maybe there are no bit permutations because they make analysis
harder, and perhaps they don't add all that much. Maybe the
algorithm was designed for both hardware and software, or maybe
it was designed for specialized cryptographic hardware with
several parallel microprocessors and some cryptographic
primitives.
If it is real, we have a lot to learn about S-box design. The S-
boxes are not even balanced. Maybe they are created just so to
avoid some bizarre attack we can only dream about, but I kind of
doubt it.
But the key schedule is just plain wrong.
So, here's a theory. Let's assume the code is real. (Not that
it's SKIPJACK, but that it's a real algorithm from some military
or some corporation.) Clearly the code is not designed to test
the cryptographic algorithm, but to simulate some kind of
hardware interface: it's called a "software chip simulator." If
I were the NSA and I designed an algorithm whose security rested
on some tables of constants, I might replace them with phony
constants before giving them to another organization to test. I
might call the phony version S-1 and the real version S-2.
Maybe the code was originally written in FORTRAN, and then
translated into C. (NSA doesn't use ADA.)
NSA algorithms are classified SECRET, put perhaps algorithms in
development are classified TOP SECRET. (We know cryptanalytic
techniques can be TOP SECRET, so perhaps commented code falls
under that category as well.)
And maybe the code originally didn't have an 80-bit key schedule.
Maybe it had a longer key schedule. The poster then modified
this key schedule to make it look more like SKIPJACK. (This
might also explain the bug in the code, which might not be a bug
if it still had the original key schedule.)
Which leaves us precisely nowhere. The most likely explanation
is that it is a hoax, but I am hard-pressed to imagine a hoaxer
with the requisite combination of skills, resources, and
attitude. I also don't believe that it is SKIPJACK. It might be
a preliminary design for SKIPJACK, but if both the key schedule
and F-table entries are wrong, we really haven't learned
anything. If we suddenly discovered that unbalanced S-boxes are
far superior to balanced ones, then all best are off.
Bruce
discussion. Better late than never....
Over the last year, I have spent considerable effort collecting
SKIPJACK information. I have gone through the published
literature, the rumors, and a large stack of documents received
by EPIC through Freedom of Information Act (FOIA) lawsuits.
At Crypto last week I gave a Rump Session talk entitled "Reverse
Engineering SKIPJACK from Open Sources." I prepared the slides
before I left for Europe. Here is what I said:
What the government told us:
Single-key block cipher.
Can be used in ECB, CBC, CFB, or OFB.
64-bit block size.
80-bit key size.
What the review committee told us:
32 rounds.
No weak keys (like DES has).
No key complementation property (like DES has).
What the hardware specifications tell us:
The latency of the Mykotronx chip has 64 clock cycles.
This means two clock cycles per round.
Assorted rumors (excuse me if I don't reveal sources):
SKIPJACK does not have rounds in the same sense that
DES does: i.e., half of the text block is not
encrypted in each round.
SKIPJACK has half the total S-box data as DES.
SKIPJACK has a 48-bit internal structure analogous to a
32-bit internal structure in DES.
The masks for the Clipper/Capstone chip are
unclassified and the chips can be produced in an
unclassified foundry. Part of the programming in
the secure vault includes installing part of the
SKIPJACK algorithm. The part of the algorithm
installed in the secure vault are the "S-tables",
suggesting that perhaps unprogrammed Clipper chips
can be programmed to implement other 80-bit key,
32 round ciphers.
Trying to puzzle out the meaning of the third rumor, Matt Blaze
and I invented something called an Unbalanced Feistel Network.
These are Feistel networks where the source and target blocks are
of different size. For example, in each round 48 bits might be
used as an input into the F function, and produce 16 output bits
to be XORed with the remainder of the bits. We called this a
48:16 UFN, and we proposed a design at last year's Algorithms
Workshop in Leuven. Our design was broken, but I am still
examining the structure. A 48:16 UFN satisfies the first and
third rumor above, and I think it as good a guess as any
regarding SKIPJACK.
A few months ago, I found some additional information in the form
of documents released under FOIA. One document was a Mykotronx
design review for "Project Capstone" dated 10 December 1991. The
design review was unclassified. Among the details about the
modular multipliers and the SHA code was the following page about
SKIPJACK:
ECB Processing Rate
2 clocks per G-Box operation
x 1 G-box per shift
x 32 shifts per ECB encryption
______________________________
64 clocks per ECB
64 clocks per ECB / 64 bits out per ECB = 1 clock per bit
Yields 40 Mbit encryption using a 40 MHz clock.
The only other thing I found was a SECRET memo. The organization
name (either from or to) is blacked out. The date is 25 August
1992. The subject is "SKIPJACK Revision." Paragraph 2 is
blacked out, but paragraph 1 reads:
1. (U) The enclosed Informal Technical Report revises the
F-table in SKIPJACK 3. No other aspect of the algorithm is
changed.
That's it. Rounds are called "shifts," which seems to indicate
that they are not "rounds" in the DES sense. A shift consists of
a "G-box" operation, which includes not only what we call the F-
F-function but the XOR as well. And there is something called an
F-table, which could be a table of constants or perhaps a table
of functions. In any case, it is something that can be revised
without changing the rest of the algorithm.
Now let's look at S-1. The most probable explanation is that it
is a hoax. But it is a very good hoax:
The hoaxer knew enough about algorithm design to make a
cipher that was not obviously lousy, while at the same
time not unduly complicated. The hoaxer knew enough to
make a design that included three novel ideas not seen
anywhere else: S-boxes that are created according to no
known criteria, a G-table that chooses a rotation of
S-boxes to use in a given round, and a bizarre key
schedule.
The hoaxer knew enough about how algorithms are used in the
military to make a spookish interface. I am
particularly interested in the "zeroize" function, the
separation of the key creation and key loading
functions, and the key masking. Blaze said that the
interface was similar to the Fortezza interface, but
not the same.
The hoaxer knew about Blaze's and my MacGuffin paper and
that we thought SKIPJACK was a 48:16 UFN. We made no
secret about this, and our paper is on Blaze's web
page. The hoaxer knew to use the term F-table. I
haven't shown many people what I found in EPIC's
documents, so the hoaxer either had to look through
them himself or get them by some other means (maybe an
independent FOIA request).
It's not a perfect hoax, though. The classification markings
look odd: NSA algorithms are SECRET, not TOP SECRET, and the
codeword restriction sentence is strange. The key schedule is
hopelessly flawed (David Wagner posted an attack to sci.crypt).
The coding style is amateurish, like it was translated from one
language to another. (Maybe this is clever on the hoaxer's
part.) And there's even a typo in the code.
And maybe the hardware latency is wrong. Clearly the design
facilitates parallelization. You can precompute all possible F-
table outputs in previous shifts, and then use the G-table result
to select between them; I am not sure you can get a shift down to
two clock cycles. I don't have the hardware background, and
would appreciate comments from others.
And why are there not bitwise permutations? If SKIPJACK is
designed for hardware, it makes sense to put them in. They're
free, after all.
Anyway, it's a real good hoax. Blaze estimated that he could
have done it, but it would have taken him a month of effort. I
agree with his assessment: one man-month. It's a lot of time to
spend on a hoax, especially one where the hoaxer doesn't get any
credit.
So, maybe it's SKIPJACK. It has a 64-bit block size and an 80-
bit key size. It's a 48:16 UFN with 32 rounds (or shifts, or
whatever). And it has an F-table. This is really interesting,
because the structure really is an S-box. Everyone knows it's an
S-box, and it makes no sense for a hoaxer to call it something
else. But in S-1 it's called an F-table. (I think this is very
significant, but others find it less convincing.)
And the F-table has been revised at least once. In the code it
says that the F-table entries "differ in the S-2 version." The
code is dated 1 February 1989 and 31 July 1991, and I have a memo
dated 25 August 1992 that says the F-table has been revised in
"SKIPJACK 3." Pretty convincing, I think. (Of course this means
that we can't confirm anything by testing the hardware, since the
F-table entries are different.)
Maybe there are no bit permutations because they make analysis
harder, and perhaps they don't add all that much. Maybe the
algorithm was designed for both hardware and software, or maybe
it was designed for specialized cryptographic hardware with
several parallel microprocessors and some cryptographic
primitives.
If it is real, we have a lot to learn about S-box design. The S-
boxes are not even balanced. Maybe they are created just so to
avoid some bizarre attack we can only dream about, but I kind of
doubt it.
But the key schedule is just plain wrong.
So, here's a theory. Let's assume the code is real. (Not that
it's SKIPJACK, but that it's a real algorithm from some military
or some corporation.) Clearly the code is not designed to test
the cryptographic algorithm, but to simulate some kind of
hardware interface: it's called a "software chip simulator." If
I were the NSA and I designed an algorithm whose security rested
on some tables of constants, I might replace them with phony
constants before giving them to another organization to test. I
might call the phony version S-1 and the real version S-2.
Maybe the code was originally written in FORTRAN, and then
translated into C. (NSA doesn't use ADA.)
NSA algorithms are classified SECRET, put perhaps algorithms in
development are classified TOP SECRET. (We know cryptanalytic
techniques can be TOP SECRET, so perhaps commented code falls
under that category as well.)
And maybe the code originally didn't have an 80-bit key schedule.
Maybe it had a longer key schedule. The poster then modified
this key schedule to make it look more like SKIPJACK. (This
might also explain the bug in the code, which might not be a bug
if it still had the original key schedule.)
Which leaves us precisely nowhere. The most likely explanation
is that it is a hoax, but I am hard-pressed to imagine a hoaxer
with the requisite combination of skills, resources, and
attitude. I also don't believe that it is SKIPJACK. It might be
a preliminary design for SKIPJACK, but if both the key schedule
and F-table entries are wrong, we really haven't learned
anything. If we suddenly discovered that unbalanced S-boxes are
far superior to balanced ones, then all best are off.
************************************************************************
* Bruce Schneier 2,000,000,000,000,000,000,000,000,002,000,
* Counterpane Systems 000,000,000,000,000,000,002,000,000,002,293
* schn...@counterpane.com The last prime number...alphabetically!
* (708) 524-9461 Two vigintillion, two undecillion, two
* 730 Fair Oaks Ave. trillion, two thousand, two hundred and
* Oak Park, IL 60302 ninety three.
************************************************************************
Paul Rubin
Sep 7, 1995, 3:00:00 AM9/7/95
to
In article <42ka03$b...@blackice.winternet.com>,
Bruce Schneier <schn...@subzero.winternet.com> wrote:
Bruce Schneier <schn...@subzero.winternet.com> wrote:
>Trying to puzzle out the meaning of the third rumor, Matt Blaze
>and I invented something called an Unbalanced Feistel Network.
>These are Feistel networks where the source and target blocks are
>of different size. For example, in each round 48 bits might be
>used as an input into the F function, and produce 16 output bits
>to be XORed with the remainder of the bits. We called this a
>48:16 UFN, and we proposed a design at last year's Algorithms
>Workshop in Leuven.
>and I invented something called an Unbalanced Feistel Network.
>These are Feistel networks where the source and target blocks are
>of different size. For example, in each round 48 bits might be
>used as an input into the F function, and produce 16 output bits
>to be XORed with the remainder of the bits. We called this a
>48:16 UFN, and we proposed a design at last year's Algorithms
>Workshop in Leuven.
I sent a copy of S-1 to another crypto buff I know, and he remarked
that it could be thought of as a nonlinear feedback shift register.
He mentioned that he and another cryptographer designed a cipher along
the same lines with a 56:8 structure several years ago (I'm not sure
if it was published). The UFN idea may be a fairly natural one.
Leif Nilsen
Sep 8, 1995, 3:00:00 AM9/8/95
to
|>
|> Is there any chance that S-1 is the Norwegian NSK cipher ?
|>
|>
|> /Lars
|>
|> Is there any chance that S-1 is the Norwegian NSK cipher ?
|>
|>
|> /Lars
|>
No, NSK is a stream cipher!
Leif Nilsen
Alcatel Telecom Norway
0 new messages