31 January 1999: Add Axel Horns message.
30 January 1999: Add messages by Jitze Couperus and Steve Bellovin
28 January 1999
To: cryptography@c2.net
Date: Thu, 28 Jan 1999 11:06:34 -0500
From: MCKAY john <mckay@cs.concordia.ca>
This I got from computer historian, Simon Lavington.
The (Manchester) Ferranti Mark I had a hardware random number
generator. This was specified by Alan Turing - (A copy of his
original Internal Report, dated 1949 I believe, still exists.)
The random number instruction was based on electron noise in a
thermionic diode. Turing's report even gives a possible circuit
diagram. The same strategy is used today in the UK Dept. of
National Savings' ERNIE Premium Bond machine.
Another curiosity of the Mark I's instruction set was a sideways
add ('population count'), also specified by Turing. I've always
assumed that the two instructions could be useful for cryptography -
eg for the generation of one-time coding pads and the testing of
decryption procedures.
[See S.H. Lavington's 1978 Comm ACM paper on the Manchester Mark
I and Atlas: http://www.computer50.org/kgill/mark1/lav.html ]
From: "Jitze Couperus" <Jitze.Couperus@cdc.com>
To: <cryptography@c2.net>
Subject: Re: Pop Count Instruction and cryptanalysis
Date: Thu, 28 Jan 1999 11:32:16 -0800
John Mckay wrote:
[Snip]
About the "sideways add" or pop-count instruction - indeed
Seymour Cray's first supercomputer (the Control Data 6600)
sported such an instruction, as did all subsequent Control
Data machines until the advent of the 180 series in the mid
'80s.
It was almost a tradition that one of the first of any new
faster CDC machine was delivered to a "good customer" - picked
up at the factory by an anonymous truck, and never heard
from again.
We always wondered what such an instruction might be useful for -
until one of the first of the 180 series (n'th generation successor
to the 6600) was delivered to such a customer, and cries of
anguish erupted that this machine didn't have such an instruction.
We scrambled and had to create a very tight code sequence within the
instruction stack that could be generated via a Fortran intrinsic
function.
Simon Lavington also mentions in his book that the venerable 6600
inherited some ideas from the Manchester Atlas. I never found out
what specifically - did the Atlas sport such an instruction? -
perhaps also inherited from Mark I?
I'm not sure if Cray's other machines (built after he left Control
Data) had such an instruction, but I'm told they did.
Jitze Couperus
Control Data Systems
To: cryptography@c2.net
Subject: Re: Pop Count Instruction and cryptanalysis
Date: Thu, 28 Jan 1999 15:35:04 -0500
From: Steve Bellovin <smb@research.att.com>
Jitze Couperus writes:
[Snip]
For years, I had heard the story about NSA liking that instruction.
But I never understood why, until I started working on plaintext
recognizers, and independently derived the need for it. See, for
example,
http://www.research.att.com/~smb/papers/probtxt.ps.
There are other instruction types that are useful for cryptanalysts.
The CDC Star had a lovely set of vector operations under masks. And
the Harvest add-on to the IBM 7030 (Stretch), described in a book by
Buchholz ("Planning a Computer System", McGraw-Hill, 1962) was intended
for NSA as well.
From: "Jitze Couperus" <Jitze.Couperus@cdc.com>
To: <cryptography@c2.net>
Subject: Re: Pop Count Instruction and crytanalysis
Date: Fri, 29 Jan 1999 13:15:23 -0800
A correspondent asked me if I could expound some more
on what I know about the use of the pop-count instruction.
The paper cited earlier in this thread by Steve Bellovin
tells you far more than I can, as well as a paper that
it cites in turn about "A Programmable Plaintext Recognizer".
However, and without boring through detail, I can perhaps
give a flavor of how it was used a long time ago and in a
manner that is interesting from a cryptanalysis perspective
- and given that it jibes with similar discussion in the
papers mentioned above.
In one of the first "interactive" environments supported
on the 6600 - the Intercom time-sharing system, we had
a utility that allowed one to search a text file for
some arbitrary character string - much as any text editor
allows today.
This was implemented approx. as follows. Each line of text
in the file had appended to it a 60-bit word, the contents
of which were a bit vector. If there were one or more
of the letter "A" in the line, bit 1 was set, if there
were one or more of the letter "B" in the line, then
bit 2 was set, etc... thus setting some sub-set of 36
bits coresponding to the characters A..Z and 0..9. Let's
call this word appended to each line its "thumbprint".
There are 24 bits left over - more about that later.
Now to search for any line containing some search
string, all you have to do is create a similar thumbprint
for the search string, and loop through the thumbrints
of the lines in the text file, checking each against your
search thumbrint. "Checking" in this sense means doing a
logical "AND" between the two to extract matching bits,
and then counting how many bits matched - hence the pop-count
instruction.
A "hit" would of course only be tentative. It does not
tell you that the line in question contains the actual string
you are looking for - only that the line contains somewhere some
(count of) the characters contained in your search string.
This little loop can however be coded in an extremely tight
manner to fit in the instruction stack (equivalent to instruction
cache in today's technology) thus allowing a very fast winnowing
of interesting text lines that can then be examined more closely.
The actual instructions used within the loop also made good use
of the parallelism offered by the separate functional units
of the 6600 cpu - and in later machines - pipelining.
The extra 24 bits were used in other applications (of similar
ilk) to reflect not single characters, but the occurrence of
certain digraphs in the text line. Thus bit 40 in the the
thumbprint might indicate whether a given "interesting" digraph
did or did not occur in a given line.
Later the border between the 36 bits and 24 bits within the
60-bit word was moved and successively tuned. Certain bits
of the original 36 were commoned up - i.e. a particular bit
might indicate the presence of any of Z, X, or Q because
maybe they are relatively uncommon. This would free up two
more bits for use as digraph flags - and so on.
Then, in another place, the whole mechanism was turned on
its head. It wasn't used to *look for* a certain character
string, but rather to *reject* certain lines of text as
being uninteresting. (Others might use the word "implausible"
here.) Furthermore, the concept of a thumbprint per "line of
text" was refined to support differing granularity of the
thumbprinting, and of course the size of the thumbprint
itself, as 64 bits became a more common word-size.
Some 30 years later, I find the paper cited by Steve Bellovin
on "Probable Plaintext Cryptanalysis" to be extrememely
interesting - in particular it cites another paper
about "A Programmable Plaintext Recognizer". This is
the only open documentation I have ever come across that
discusses this kind of mechanism in any detail.
Jitze
To: cryptography@c2.net
Subject: Re: Pop Count Instruction and crytanalysis
Date: Fri, 29 Jan 1999 22:22:52 -0500
From: Steve Bellovin <smb@research.att.com>
Jitze Couperus writes:
>
> Some 30 years later, I find the paper cited by Steve Bellovin
> on "Probable Plaintext Cryptanalysis" to be extrememely
> interesting - in particular it cites another paper
> about "A Programmable Plaintext Recognizer"*. This is
> the only open documentation I have ever come across that
> discusses this kind of mechanism in any detail.
Thanks for a very interesting article. The other paper you cite
is by David Wagner and myself, and can be found at
* http://www.research.att.com/~smb/papers/recog.ps (or .pdf).
To: cryptography@c2.net
Date: Sat, 30 Jan 1999 14:39:10 +0100
Subject: Re: Pop Count Instruction and cryptoanalysis
From: Horns@t-online.de (Axel H. Horns)
Inspired by this thread I remember that in the late 70ies I attended
a lecture on "COMPASS", the assembler language for CDC Computers, at
the University of Hannover (Germany), the computing center of which
being equipped with two CDC 6600 and one CYBER 76 mainframes in
those days. The professor had explicitely noticed that there was no
obvious use for a hardware-accelerated poupulation count opcode but
he had not suggested to look on utilization for cryptography.
From this lecture I own a copy of "CONTROL DATA CYBER 70 SERIES -
6000 SERIES - 7600 COMPUTER SERIES" pocket manual "COMPASS VERSION
3" printed in 1973.
This document clearly states that in the CYBER 70 Models 74 and 6600
Computers, the opcode "47" for "population count" was executed by the
DIVIDE UNIT. Contrary, the CYBER 70 Models 76 and 7600 Computers had
a separete POPULATION COUNT UNIT.
If I understood the opcode table correctly the respective opcode was
executed in one or two clock cycles (very fast; the same as shift
opcodes).
Hence, it looks like as if there has been some kind of evolution.
The NSA first had demanded the implementation of the "population
count" opcode and they got it in a more economical way by using the
hardware of the divide unit. The NSA software using this opcode must
have been very successfull; otherwise they would not have been able
to require to be provided with a separate hardware unit which I
think was *very* expensive in those days (The core CPU of said CYBER
model was made up of modularized and encapsulated printed circuit
boards equipped with discrete transistors, AFAIK).
Axel H Horns