In the 1970s, the National Bureau of Standards proposed a new
"Data Encryption Standard", which was eventually approved as the popular
DES algorithm, and used for decades.
However, some of the first open academic researchers in encryption
criticized the standard, saying that it was too easy to crack it with
a brute-force attack using a specialized machine. Chief among the
critics were Whitfield Diffie and Martin Hellman, both
at Stanford University.
As a result, people from the National Bureau of Standards and NSA
came to Stanford to meet and talk over the issues. Dennis Branstad
attended from NBS.
It turns out that the critics were correct. DES was too weak, and
was subject to a brute-force attack. I led the project at the Electronic
Frontier Foundation to design, publish, and build a machine that would
prove this once and for all -- by performing the brute-force attack.
One of the most interesting things about the tape is that the arguments
made against making DES uncrackable continue to be made today, over and
over, about all sorts of security measures. For example, "It'll never
be the weakest link in the chain, therefore let's not make it stronger
than it needs to be." This was wrong back then, and wrong now; DES
did become the weakest link in the security of many systems.
Now-famous inventor Paul Baran was also at Stanford at the time of this
historic meeting.
He participated in the meeting and recorded it on a cassette recorder,
with permission of the participants. Decades later, he offered me a
copy of the tape, which I accepted.
I suggested in 2005 that it would be lovely if someone wanted to transcribe this recording. Sam Bretheim did the job in 2008, and the
transcript follows below (in draft form)
for your reading and searching pleasure.
Please send corrections and improvements.
The participants don't record the date of the meeting, nor identify
themselves, at the start of the tape, though they do agree that it's OK
to record the meeting. Many voices are recognizable. Many are still
unidentified, and we would appreciate if listeners could help to identify
them, or fill in more background information (such as full names for
the participants).
?
You can have the cassette - doesn't make any difference.
Martin
'Cause I have a... I guess the real question is: is it okay to set up a second one so we don't have to...
?
Sure, go ahead. Go ahead - I don't care. We can have the recorder record the other one.
Talking over.
?
It's appropriate that they approve their own wiretapping.
Laughter.
?
Hey, has anybody got any more tea down here?
?
Okay, a productive way to start would be to...
?
I was going to suggest one more thing - S4 line 5 - we might also consider the licensing of devices. [??]
?
With respect to ordering the agenda, it seems to me that the preferences of the people who came a long way should be taken into account - sometimes if we spent more - and I gather that you are more interested in discussion of the algorithm.
Doug
But we are here, I think, primarily to see if we can be helpful and provide information so it's - as opposed to suggesting agenda items, so we're pretty much at your service.
Whit
There's a question of when your airplane - when you wanted - if you wanted to take an airplane back or anything like that.
Doug
No, I had that idea, but I abandoned it, so...
Whit
Our good weather went away, and we can't all do much better than
Washington.
Doug
[?]. So we have as much time as necessary.
Martin
Okay, because there are several - We have a number of questions, and we think inputs from the visitors from the East Coast would be very valuable, because basically they're questions about the security of the system, and how things were arrived at, and so on, which I don't think any of the rest of us really know.
?
I'd like to suggest we start there.
Doug
Yeah, that's what I would like.
?
Any questions, or did you just want to...
Martin
I have an outline of several points, which I made copies of; I'll just get this set up. Could we put one of these down there, maybe, and one here...
?
You're going to need a bigger table for the microphones.
Laughter.
?
How many do we have going?
Talking over.
?
When we do it, they'll all interfere with each other and -
?
The first thing we have to announce into the microphone is that there weren't any people that didn't want to have it recorded.
Laughter.
?
So that kind-of was the first thing that always went on record.
?
Why don't you put it on the tray?
Martin
Okay, I've got an outline, and a letter that I wrote to Dennis that I made copies of. Here's the letter to Dennis; why don't you pass these around - I guess Dennis wasn't [???]...
They might be referring here to a letter dated February 23, 1976, and addressed to
Elliot Richardson,
Secretary of Commerce, which is partly quoted in Steven Levy's
"Crypto". A later paper on the topic by Diffie, Hellman, and several other authors is "Results of an Initial Attempt to Cryptanalyze the NBS Data Encryption Standard".
Art
Did you ever get the answer to that letter?
Dennis
It's probably halfway between hither and yon, so... We have responded to it, but...
Dennis
I'll fill [you] in on why and how that response was held up.
?
Does that reflect all your questions, Marty - the letter?
Martin
Not the outline - the letter just has one question concerning the security of the algorithm.
Doug
I'm not sure there's enough to go around.
Martin
Well, maybe I can start off by stating the position that Whit and I are taking in this proceeding, and that is Item 1 on the outline, and that is the need for a security officer to represent the public and non-DoD agencies, such as Internal Revenue, HEW, and the Federal Reserve Board, that are the end users - will be the end users of this cryptographic standard. Basically, we see that most of the knowledge of cryptology within the country resides within the National Security Agency, and possibly associated military agencies. And there are potential conflicts of interest between - with these agencies coming up with devices that would generally be used by the other, non-DoD agencies. And we feel that there's a need for someone or some agency with knowledge of cryptography to represent the eventual users. We don't claim to be totally knowledgeable in cryptography, but at the moment, for lack of anybody else, we're taking that position - nobody's given it to us, but we're going to ask the same hard questions that any good security officer would ask. We'll probably miss some, because we're not security officers, but that's the approach we're trying to take. And the - I'll run, very briefly, through the outline.
The first thing we'd like to hit is the key size of the proposed standard. We feel it's too small, both today - we feel it's vulnerable to attack by an agency such as NSA, although quite secure against commercial assault, and my letter to Dennis outlines this threat. And we feel that, looking 15 years down the line, and extrapolating the decreasing cost of computation, the standard would be insecure against attack by almost anyone. And, as noted on the outline, it's very similar to the problem that if people had recorded World War II cryptographic exchanges, much of that could probably be broken today, very much to the detriment of countries involved. There's much information that you want to survive beyond fifteen years. And there may even be some legal standards on data such as Census data or health records, [or] Internal Revenue Service, that require that they be protected for a period beyond, say, 15 or 20 years.
The other point we'd like to make there is that the cost of the larger key size is very small, and I'll have to go into that, because there's always a user problem - that remembering a hundred-bit key is much more difficult than remembering a fifty-bit key - but we think there are ways around that.
Item three concerns several questions - basically, the key size was cut down from 64 bits to 56 bits by using 8 of the key bits as parity, and we'd like to know why they were not added on. If you need parity error detection, why not add on 8 parity bits? Even a 64-bit key, we feel, is too small, but it's somewhat better than 56.
Moving down, the other minor points which (if there's time to go into)... Item four is the lack of a performance standard, which is even cited in the Federal Register. Basically, we'd like to know how strong the system is. We currently - I hate to say wouldn't believe - we currently feel very strongly that the system is insecure, and I'd like to know why we're wrong, if we are, and how strong exactly you think it to be. And... let's see... What were the other submissions that were made in response to the Federal Register solicitation, how was the selection procedure - what selection procedure was followed, what certification procedure was followed, and what happened to IBM's 128-bit version of Lucifer, which we feel, at least on the basis of key size, would have been much stronger.
Fifth point... can be glossed over.
Item six is a return to the first question - the need for a security officer to represent the public. Basically, we feel there may be a need for an agency external to the military and external to the Executive Branch to represent the interest of privacy outside of that community, and we think that, in fact, the manner in which this standard was selected, and the particular parameters selected may give strong evidence of that being necessary.
Item seven - again, if there's time - would be a question of flexibility versus standardization: basically, there was an earlier critique that Whit sent to NBS that included some of these points, and one of the things it hit was the point that the standard was too firm, and that you couldn't use it with a small block size or large block size - may have been a good compromise, but maybe a compromise wasn't the best thing to do here and there should have been several standards - basically, a parameterized family of algorithms. And maybe some planning should be done for this now by including header information in the key which is discarded, but which would allow a terminal to discover when, later, new families are included, that the material coming in is encrypted in a key, but in a system which is not compatible with your terminal. And by planning for that now I think we could eliminate a lot of cost later. The most important of these that we see is Item 2, the question of key size.
Martin
I guess I'd like to address a question to Doug, Dennis, and Art on that. Have you all had a chance to see my letter to Dennis, basically?
Martin
I'd appreciate any comments you might have on it.
Dennis
Well, first of all, have all the rest of you around the table had an opportunity to first review this letter? I also have an update - have an idea on how NBS got into the picture; the people that we're attempting to aid; the types of threats that we see; how we got to where we are; where we are; and where we hope to be. Now that's an awful lot of information - that's probably an hour lecture, of which I have some
viewgraphs, but I wasn't exactly sure what you people were interested in.
?
I think we'd probably like to hear that.
Martin
Dennis, maybe I should have asked the other people. I haven't detailed why we think that currently the system is insecure against, for example, NSA, but not against commercial assault. Maybe I should take one minute just to say what that is. Basically, without going through the details in the letter, if you have $20,000,000 to invest in a machine, which you then
amortize over five years at a cost of about $10,000 a day, you could break the proposed algorithm by exhaustive search in one day's time, and so it would cost you $10,000 per search. To do this in the most efficient possible manner, you would need a
known-plaintext / cryptogram pair, and so for example if a certain group of
IRS files are all encrypted in the same - in a certain key, and one of them happens to be yours or a friend's, you might be able to get a known-plaintext / cryptogram pair, and then by searching through the keyspace until you found a key that encrypted the known plaintext as that cryptogram, you would have the key involved. Well, there might be several of them, but you would have a very small number of -
Art
Marty, in the answer to the letter, which you haven't got for various bureaucratic reasons, I guess, these assumptions are seriously questioned, and Dana Grub[??], one of the engineers, made a study of your letter for Denny and produced figures that were quite at variance with yours, and instead of one day he gets something like 91 years.
Martin
Well, okay, I thought - maybe we were being -
Dennis
Anyway, again, I apologize that this didn't get out. The way that the standards process works is everything is free and open to everyone at the same time, and of course that's one of the requirements that we set up. Some of the early papers that we put out stated the requirement that any standard that we do publish and any of the standards that we do promulgate must be equally open to everyone. Well, of course, one of the things about cryptography is it's one of the things that you would like to keep closed, but that's not acceptable with our standard, and some of the comments and the criticisms that we've got - "Why did you publish this? Why didn't you keep this secret? And then you wouldn't have hit situations -"
Martin
I think you would have. We agree wholeheartedly that -
Dennis
Anyway, in the letter - let me respond quickly that we started with two basic assumptions. One, that the algorithm is published in its entirely and freely open to everyone, which we've gotten some criticisms on, but that was our assumption. And the other thing was that, as you were stating, that the technical people that were going to be looking at it, or penetrators, as such, would not only know the algorithm, but have sufficient plaintext and ciphertext to derive the key.
One of the requirements for a standard, if every, let's say, potential terminal was going to - in the federal government, since this is a federal standard, we're looking at our own uses and purposes - and out sat a line of terminals, each one hard-wired to a separate computer, and there's no compatibility, you can't - if there's a queue for the PDP-10, you can't get to another type of computer because the terminals aren't compatible. And one of the purposes of cryptography is that you can lock people out, if you so desire, and what we wanted was one that would be acceptable in many different applications, one which potentially could be used in all terminals to talk to all data processing systems, and the only thing that was secret would be the key - the one variable that's missing.
Anyway, to make a long story short, on your own thing, we are prepared to talk about what our assumptions were, and what our computations are. But let's go back a little bit: how did we get to where we are?
Martin
Okay, my real interest would be - and I don't know about the other people - maybe people do know something about this standard-making process - is the difference between the one day and the 91 years, because that's a large difference -
?
I want to review some of the assumptions... I think we have a clear difference of opinion, and I think it probably all hinges on the assumptions. Now maybe if we can get some of these made explicit it would be helpful. For example, let's see, you're saying that the standard is designed for terminal-to-terminal type communication, right?
Dennis
Terminal-to-data-processing type; of course, you can use it for terminal-to-terminal if you so desire.
?
One of the points that Marty and Whit raised is this is not the best... sufficient for small transmissions of a couple characters at a time, that there are other ways of doing it; that's one of the questions, you know... And you mention that you were concerned - that COSA[?] was concerned about publication of the algorithm. Well, it seems wild that anyone would ever have any confidence in security with the algorithm not being published.
Dennis
That's right. Because, sooner or later, someone's going to find out about what's in the device, etcetera, so...
?
I don't want to cause you to spare much worry, or...
Dennis
I'm just saying - I talked with Marty on the phone at length about this over the last few months. If we take all of the comments that have come in concerning the process that we're going through getting to where we are, that it seems like the way that we've done it - all of the comments kind of balance around a disk, and it seems like we're kind-of on the right base, but...
Whit
Well, let Branstad finish with his explanation of the background, because I don't know it and I think it naturally goes at the beginning.
Dennis
Well, first of all, there's - people have already stated that there isn't enough information on cryptography in the open literature - you start looking at the various papers, and they probably number ten, starting from about the early '70s, let's say. I know the first time that I heard NBS requested you look into this field, I believe, was a national ACM conference in 1972 in Boston, where someone stood up in the audience to say "Hey, we need some - an algorithm for protecting information while it's being transmitted; why doesn't NBS get involved?" And at that time the effort was initiated - the first open solicitation for algorithms was in 1973, in the Federal Register and also to various companies and organizations that had been publishing in the area, for algorithms.
Some of the interesting ones that came in - who said it doesn't make any difference, but just to show the lack of education or the immense amount of uneducation, took the classic case of two infinite-length tapes, write random information and distribute to the two areas, add it on to one end, and subtract it off the other. I wanted to write a letter back: "Please give me the name of the supplier of infinite-length tapes," but I didn't -
Laughter.
Dennis
I didn't think that was -
Dennis
Yeah, Turing had [??]. But I wasn't allowed to send that letter out, needless to say.
Essentially, nothing came in at that point. What we were looking for is - were algorithms, any information, statements of requirements, was it needed; who's out there that's interested in it, and we probably made a poor choice of words when we put it out. We said "We solicit proposals for encryption algorithms." Well, of course, universities have people that - professionals that read the Federal Register, and we got a lot of calls saying "Gee, we would be happy to submit an unsolicited proposal for developing algorithms. We don't know anything about it, but we would like to take some money on it." So, anyway, the first fishing expedition was - we knew companies like Datatech[?], etcetera, but most of those algorithms they considered proprietary. They feel that the security of their algorithm is based at least in part on the proprietariness of the algorithm.
The second solicitation went out. We kept looking, kept looking, and this puts me to August of '74. And, at that time, several algorithms came in, some of which were considered proprietary, and that was one of the problems. When we receive proprietary information, we treat it as proprietary, and we said "You can't use it - we have to publish it." IBM has published a significant amount on their family of algorithms, and what we were looking for was one that could be publicly known, would be efficient in hardware, especially in LSI-type hardware, so you could stick it right down in these intelligent terminals. Security based on the key, and security that would provide - a high level of security.
How high is high is probably the argument that we're here on. Well, we had a threat model that we had defined, and that was essentially a return-on-investment-for-money model, and privacy - otherwise, an unclassified data communications network model. How high is high, again, is... We looked at hundreds of meters[?]. We were looking at some order of magnitude like this - at a microsecond per try or so. And we went out on the open solicitation, and the one that came in and satisfied it, said "Gee, let's put it out for comment," and that's when it came out, in March, and you sent your comments in at that time.
?
I might add that, if I may -
Dennis
Anyway, let me just finish. The comments came in; we responded to them; we felt that we had satisfied those comments, and again we put it out so more people could look at it, as just an algorithm, not a proposed standard.
On August 1st of this year we published it as a proposed standard. There's a fixed way of establishing a standard; our 90-day minimum comment period closed November 1st. About 20 or 30 comments have come in; we're currently summarizing them. Eight major concerns, I would say - again, kind-of spread around the spectrum, too complex. Banking people say "We can't afford it now as an individual terminal type of thing". Lack of information was one of the biggest criticisms, and this is kind-of a tough thing: if you don't know what you're talking about, how can you supply - how can you comment on it?
And yet, unless you have something that everybody understands, it's difficult to start establishing ways of using it, and these were the main things. They said "Finally, the algorithm - we now understand it can be done. Now tell us how to use it. Tell us how to interface it. Tell us about the protocols. Tell us about how to protect the key, how to generate the key, how to distribute the key," and that brings up the parity types of bits. What the biggest thing was, was "Gee, if you have a standard, I want it right now. Who's building it, and how much is it going to cost?"
I can fill you in on who is going to build it. One company has... neither has made the public announcement, but on an OEM basis they're going to put it up, and they have different ideas. One says "We're going to make it as fast as we possibly can make it, because people will want it fast for data processing applications," and the other people say "We want it as cheap as possible," but it's on the other end of the spectrum on speed. Neither of which, by the way, comes even close to your expectations.
Dennis
And that was one of the things that we... We did a lot of analysis. Mean time between failure is one of the things that I want to talk to you about. I talked to the people at Burroughs who designed and built
ILLIAC. We looked at Hypercube 4, which... I'm not sure... Anyway, I had the engineer look at it, and the mathematician - the postdoc mathematician that's doing the analysis of the algorithm for me, full-time since September, and I can fill you in on some of the results that we've gotten out of them. But I asked them both to comment on the letter, and I'll be happy to give you duplicate copies of it, but it essentially came down to the fact that we were looking at square footage, cost, control, power requirements -
?
This is not a response, though.
Dennis
No, this is in particular - Now, I've given you the background. Are there any questions on the background?
Martin
No. Before you get into a critique of our critique, I think I'd like to summarize our objections, for those people who have not had a chance to hear about it earlier. Would that be valuable? I think I can do it in three minutes. Okay?
Dennis
Sure, go ahead. I think that now is the appropriate time. If there aren't any questions on how we've gotten to where we are and what types of organizations we're trying to service, your first thing on the agenda was the need for a security officer, [which] I find very interesting - I don't know if there should be a security officer for everyone, but there probably should be a hierarchy of information dissemination and a security officer for each organization, and this is spelled out in, well...
Martin
I guess that should be modified. What I really mean is the need for a security agency to represent the public and non-DoD agencies -
?
Oh, it's a security agency...
Martin
Yeah, or FCC might - maybe should be given an extension to its charter -
Dennis
For doing what - distributing keys?
Martin
No, for communications security for the civilian sector, just as NSA has an all-encompassing charter for security for the military -
Doug
I would like to make an amendment to that statement. NSA is administratively in DoD, and it's primarily concerned with DoD; that's true. However, there is a government-wide organization called the United States Communications Security Board, and the director of NSA turns out to be their executive agent for most things, but they are concerned with government communications in general, not just -
The United States Communications Security Board was later rolled into the NTISSC, which changed its name to NSTISSC, which is now
CNSS.
Art
Doug, could you spell out the membership for -
Martin
I'd be interested in hearing that.
Doug
The membership is approximately ten different agencies, including Treasury and...
Art
ERDA, the Energy Research and Development Administration, was the relatively short-lived and little-known successor to some of the functions of the AEC, and later became part of the
Department of Energy.
Doug
You see, they're the people who are involved, classically, with classified information, so there is DoD, there is ERDA[?], because they were AEC, and they have their own
classification act, and so on. There's
Treasury, and - I wasn't really prepared to identify -
Art
The point is that it is government-wide and goes beyond...
Doug
And so, for example, we are - I'll pick a particular example of an area in which, at their request and with their approval, we have assisted
LEAA in providing privacy-type so-called equipments to police departments and so on - again, for a law enforcement purpose, which has nothing to do with classified information, so that... Regardless of what you think about us,
black hats or
white hats or
gray hats and so on, NSA has certain requirements to assist the government as a whole in these areas. Now, these areas, of course, were of less importance because things didn't used to be handled by electrical communications that are now being handled. It seems that one of the more important things that government agencies are concerned with are the things like funds transfers where they're worried about fraud problems, because they're obviously targets for people. The next thing: we have
OMB starting to talk to agencies about what they should do because of Privacy Act obligations as tele-processing of files - you know, VA, HEW, etcetera - kind of things go on. So that was the - it was in fact because of that obligation that we found it very appropriate to work with NBS, as their technical advisor, because I agree that - we believe we are the repository of most cryptographic skill, and therefore, if something is to be done this way, that we have to assist, at least in the technical side of things, including the evaluation. There's another part of our skill that we had also done - in looking ahead a couple years ago to the question of - here were these things upcoming in non-classified information; we attempted to analyze threats, because part of our job is to analyze threats and then say "This appears to be an appropriate level to counter against it." Because there is no such thing as 0/1 security, and in analyzing the threats, we had come up with a certain level that we thought things needed to be. And one of our - therefore, as we looked at the things that NBS submitted to us, we were looking to see the level we thought was necessary. And, in analyzing threats, we also looked down the years ahead and said "Yes, technology is going to improve." Our rule of thumb is that computing technology - you get a factor of ten every five years - that's computations per dollar. And it's really amazing that it's lasted now from relay logic all the way down to the present time, and you put those things - I'll send them over on paper, and it just runs right down there. We also, though, attempt to look realistically at exactly how good things are, because this has to be done as realistically as possible. So we did try to do threat analysis as part of our national - not DoD - concern, and then we found it appropriate to be working with NBS, who are concerned with computer standards for other government agencies. Now life gets a little complicated, because NBS is concerned with computer standards; there are other people in the government who think they have concerns in this; there's OTP, who don't quite know where they belong but think they have some action; there's Commerce's Office of Telecommunications; OMB administers the Privacy Act; the subject in general has certain -
Dennis
There's also the National Communications Standards Committee, which is worried about the protocols for federal communications and things like this. We worked carefully with them, looking not only... well, how to use the standard. If it's established, how do you use it?
Martin
This seems to be directed toward my Item 1, which I put down first not because it was of primary importance at this point but because I wanted to mention the attitude that we're taking in this. Really, Item 2 is the one that I think... We have limited time today to talk about this; I'd like - I know other people are much more concerned with HR 214, so I'd like to move to Item 2 rather sooner, because -
?
I'd like to suggest two ways to cover Item 2. One is answering your inquiry, and the other is to get an update from these three people relative to attempts of penetration or key-breaking - any changes in what's being proposed by NBS; what the NBS position is with respect to updating the level of protection, and under what conditions; today's definition of a standard in that sense; the wording is not important.
Dennis
Is everybody familiar with how the algorithm works - not that it's important in - the details of it, but... 64-bit mapping from 264 items onto 264 items. The same mapping, but based on a variable of 56 active bits. Total key length 64, 8 bits of which were reserved for parity, for, essentially, keying using the communication channel itself - remote generation, to make sure that when it gets there it's correct.
?
I don't understand these parity bits. This is in the device itself; is it for correction of line errors? We already have that automatically.
Talking over.
Dennis
Doug, why don't you -
Doug
Okay. One of the proposed modes of operation, which we believe is a very important mode, is a mode in which some central authority, having found out that the person at the terminal is the right person, because he's able to put his own personal key thing in first, gets ready to transmit to that terminal a special... a key to be used for that one particular set of transactions.
?
A key on top of the key, so that -
Doug
Actually, the thought is that, knowing what's in there at the moment, a new random variable would be generated, sent out encrypted under the key that is there, gets decrypted and it's fed around back in, and becomes the new key variable to be used, for example, this particular log-on session. Now, the same authority will have to also worry about getting to the process that you want to be accessed - the same key variable, so now you will have something that we've called end-to-end protection, meaning you have a unique key variable that you're using all the way from your device to this process that you're executing on some other computer, across the country or wherever.
Martin
If Paul and I want to set up a conversation and we don't have a key for talking, this is an important key distribution problem. We would contact the central authority, perhaps - a key distribution node, and request the key to that conversation?
Doug
Well, that assumes that you're working under some situation in which you are willing to put faith -
?
In the central authority.
Doug
In the central authority; that's right. Now if... and so it's up to what... Suppose you both work for the same company, but in different parts of it. You can request from a central authority for your company, or for your bank or whatever, over commercial telecommunication systems, to get this setup going. That's part of this so-called remote keying scheme that makes it very attractive. You have the ability for two people to authenticate themselves to some central mechanism which will then set up the vehicle for them to conduct their own private transaction.
?
I'm very na. You have another 256 keys.
Martin
Not really. The algorithm operates in a way that even if you were to put in 64 bits without adding parity, it strips off the parity bits automatically.
Doug
Yeah, only 56 bits get used. That's correct.
Talking over.
?
The most you'd ever get out of the other 8 bits -
Talking over.
Martin
It's for error detection purposes.
Dennis
That's the error detection part of it, yeah.
Martin
Which we maintain should be added on top of the key, rather than being taken out of the key.
?
Wasn't the assumption that some of the communication channels will have no other error detection facility except these 8 bits?
Doug
Not necessarily, but you're also concerned with the thing getting through the process correctly if it's going to be fed around back in, because otherwise, if you put in a bad key, then it's very difficult to find out what happened.
?
My feeling is - and, again, I approach this from a communication point of view - that most of the communication links now being built have rather fancy error-correction stuff, so if it's embedded in the message it will have the benefit of some bits that are out there that are -
Dennis
One of the parameters of the algorithm is that it could be made in many different applications, and authentication of terminals and authentication of users is one of the biggest -
Doug
Now I want to say one more thing about this. Also, I said, or Dennis said, that an NBS goal, which we found acceptable to us, was - did this get adequate chance for the private sector - to be provided, and so part of the task was to assess things that came in and say: were they adequate? Now this is the form in which this particular thing came in.
Dennis
The way that it came to us is - except for one index error, which a fellow at IBM found, L1 instead of L0, it hasn't changed one bit since the way we got it.
Martin
One major point, I think - if all the submissions you got were not secure, you shouldn't select one of them. And it comes to the real question: is this secure or is it not?
Doug
I was about to say: this did meet the standards that we had derived independently for the threats. So, from our viewpoint, it was satisfactory. We see value in certain things that were in there. I claim that we see value in the parity bits as proposed. I would also take up with you later this question about the initial permutation and so on.
Martin
The real conflict comes down to whether it's secure or not. I think that we've spent a lot of time -
?
I think we'll spend a moment more on the parity bits, since we're at them.
Talking over.
?
That's up for argument, it seems to me. The basic question is: 56-bit isn't big enough.
Martin
In terms of whether 56 is enough, we can argue about whether it's good or bad to include the parity as part of the key, but if it's too small, then there's no question.
?
I wonder if... In the interest of time, there are a couple of overriding[?] major issues, and one is: what threat are we talking about? Is it reasonable for the threat? Is it the only standard, or can we have other standards later for dealing with other things. Let's just pick a general ballpark before we go into detail, and we can get through the subject a little bit faster if we can just bring out these key assumptions of what's under the whole thing. What was the threat assumption that [??]?
Doug
I'm not sure that I can tell you details about threat assumptions, because that isn't an area that I was involved in. But, basically, the kind of thing was to say... Let's consider the funds transfer business. The kind of thing was to say: have we made the cost of attacking... of some kind of attack of this - exhaustion - we'd argue exactly how much it would cost. We made that so expensive that the person who wishes to attack that will go some other way, like attempting to buy the key variables from the custodian, or steal them when they're in transit, or - all kinds of problems like that.
?
So you put a price on the cost of stealing vs. the price of [?].
Doug
Stealing, or subverting, or -
?
And you looked at the future time.
Doug
Yes, and we looked at the future time, particularly for the cost of doing it by some mechanism - computational way.
?
Okay, that was the basis...
?
The fastest computers of today - how fast would they be able to do that.
Doug
And for the next ten years - fifteen - [???]
Talking over.
Art
Secondly, this was never intended -
Talking over.
Doug
Now, why did we only look fifteen years ahead? Because we figure that by then other things will have happened that will probably, say - for communication technology, etcetera, there's time to open up the whole thing again.
?
You're saying that a factor of 103 in cost/performance, and -
Martin
But I would now make one point: that anything which is sent out in this key today and which is recorded by somebody, and which should be protected for longer than 15 years, will become vulnerable 15 years hence when it should still be protected.
Doug
But what are those things that require... It's one thing to talk about diplomatic secrets - what the Secretary of State said to the foreign minister or something like that. Someone might very strongly want to get that. I still say that if somebody would like to read your Social Security file -
Martin
My medical records.
Doug
Okay, medical records... I still think there are other ways that he can get at your medical records without having to build...
Art
You think your medical records require fifty years' protection?
?
Maybe it has legal implications; I haven't had a chance to check that; my understanding is that census data legally must be kept secret for a hundred years.
Martin
The other point is -
Art
But that data today is in the clear.
Talking over.
Martin
That's a good point, but one point I'd like to make - well, actually, it's a two-sided point. The reason that you're asked to come up with a cryptographic standard is that people worry about this data being in the clear right now, and the fact is, as more and more of it is put on easily copied disks and so on that the potential for theft becomes higher. And the other point is that when you have a security mechanism present, people tend to trust it, whether it's good or bad, and people may become more sloppy. The question isn't whether this is better than what we have today; the question is, is this as good as it should be? And there, until - I'd like to get to that point - we maintain it as-is.
Dennis
One of the comments that we got back was from people that already had an algorithm in software, and they said "We don't want to have any other algorithm - we're happy with the one we [??]."
End of tape side; two minutes of silence.
Martin
... for those who haven't had a chance to look over my letter in detail, what the problem is with the 56-bit key.
?
I wonder if it would be helpful to say - the problems - we can document your case is well made. Let's talk about the larger picture.
Martin
I disagree, and we really ought to get a consensus. The reason is, we're saying that we have an analysis which indicates $10,000 to break the system with today or five-years-from-now technology, and they're saying it takes 91 years, and a proportionally higher amount of money. I see that that's important - until we settle that point, or until we understand it - we don't have to settle to it, but until we understand where the difference is, we're going to be arguing around a very important thing, because I'm going to -
?
Why don't you summarize what your letter says and what your assumptions are.
Martin
Okay. And if you could summarize where you disagree.
Art
I don't think that this would be the appropriate place to go argue each, point-by-point.
Martin
No, but I'd just like to know -
Art
We would like to meet with you to answer, but we can summarize your position and our - why we think you're wrong.
Martin
Basically, 256, which is the number of keys, is about -
?
Could you use different-colored chalk?
?
Why don't you use this - that's a...
?
There's white chalk there.
?
Yellow - any color but red.
Martin
256 is about 1017, which is a very large keyspace. However, if you search it in parallel with a special machine that's been built solely for this purpose, and we assume that it has a degree of parallelism of a million - that is, if it can do a million searches concurrently, and the next assumption is that it takes one microsecond for each chip - basically, the algorithm has been designed so it can be implemented on a single chip, and so we're saying you buy a million chips, put them together in a machine, and you give each chip 1/1,000,000 of the keyspace to search. That immediately cuts down the amount that's being searched per key to 1011 - I'm sorry, per chip, is 1011 keys per chip. Now, the real... There are two questions: what is the cost of this machine, and what is the time it will take for one chip to go through 1011 keys? Now, you put a cost of $10 per chip, and basically when you buy a million of a special chip, $5 or $10 seems to be the current price range, and this will probably come down with time. And so we feel that this is somewhat conservative - $10 a chip. The one microsecond for each chip to try a key - and remember how it works: we assume you have a known-message / cryptogram pair, and so you feed these in once; there's very little input-output associated with this device.
Art
You think one pair is sufficient to determine the entire...
Martin
I think it may not be sufficient to determine the key uniquely, but let me - I'll come back to that, okay? For the moment - I guess that's going to be a point we can -
Doug
That makes a significant cut-down.
Art
That's one of the problems of giving a mathematician - and he doesn't even have an idea of how to prove that that's an accurate decision.
Martin
I would imagine that the average number of keys which will encrypt a given message into a given cryptogram is on the order of 2 or 3, unless your algorithm - unless you purposely design it to do otherwise.
Art
I think you need more than one pair to verify that you have -
Talking over.
?
But that's trivial to the computation time.
Martin
Once you've got it down to ten keys that encrypt a given message into the given cryptogram, you try each one on the rest of the file and see what makes sense, but you can't do that with all 1017, because it takes too long. It may take too long to verify that what's coming out looks like an Internal Revenue Service document, for example. We'll come back and argue these numbers, but a million chips at $10 per chip is $10,000,00 for the hardware, and if you multiply that by a factor of two for power supplies and design and so on, you end up with a $20,000,000 machine. Now if each chip takes one microsecond to do an enciphering - that is, it takes the message which has been loaded in once at the very beginning; it does not have to be loaded again. It enciphers it under a key which is stepped each time through the portion of the keyspace being searched by that chip - they could just be consecutively numbered keys, so that's a simple counter - and then it sees whether or not the cryptogram that comes out under that key matches the cryptogram that you have. Whenever it does, it puts out a signal that says "stop the machine for a minute while I put out a potentially correct key." And that'll happen a few times, we think, and so the input-output is really very limited. Now 106 keys being searched per second per chip cuts this down to only 105 seconds for the chip to go through all 1011 keys. This is roughly one day, so it will take roughly a day of time on this super-machine to exhaust the keyspace. Now, if you amortize $20,000,000 over five years, it comes out to roughly $10,000 per day to operate this machine, and it takes one day to determine the key, so it's roughly $10,000 per file, provided you have a known-plaintext/cryptogram pair. And once you get the key you can read that whole file, so for example if all Internal Revenue Service returns for California are encrypted in a given key, once I've found the key under which mine was encrypted, I can read everybody else's Internal Revenue Service tax form for that year. And so you can get a potentially tremendous amount of information for $10,000.
?
When do you think that it's possible to do?
?
To have that hardware... And the cost associated with it.
Martin
I think that $10 per chip is a reasonable estimate, probably, now. Now you may wish to comment on that, because you said there are two manufacturers who are thinking of coming out with these.
Dennis
I'd like to find that manufacturer that's willing to sell...
?
What is the current cost that you estimate?
Dennis
$50 to $100 is the current "swag", as they say
?
Is that just for the chip?
Dennis
That's just for the chip itself.
?
In quantities of 100,000?
Dennis
No. In quantities of hundreds or thousands.
?
OK, now put the [?] curve on that, and I think you get [?] the same -
Martin
I don't think, again... If we extrapolate an order of magnitude every five years, and we're talking about five years from now...
Dennis
What was the final assumption that...
Martin
The final assumption that comes out of this is: if you can spend $20,000,000 when this technology appears, whether it's today or a few years from now - if you can spend $20,000,000, then you can break the system in one day's time, which doesn't make the data too stale, and it costs you $10,000 per day to operate the machine.
?
Given the fact that the information... someone wants the information...
Martin
That's right - the information has to be worth $10,000.
Talking over.
Martin
Let me explain - that's what I'm worried about; let me explain what I'm worried about. I don't think IBM, even - even if it were interested in commercial espionage, which I'm not saying it is - would be willing to invest that kind of money, they just don't have 365 things per year that they'd want to cryptanalyze. But what I'm concerned about is that - in particular, NSA has a budget which could afford a $20,000,000 machine, and if this standard becomes used by the federal government as a whole, it may also be adopted by some foreign countries, for use by them, and NSA would then have legitimate reasons for building this machine to cryptanalyze those documents. However, that also gives them the ability - and I'm not saying this is why they'll build the machine, but it also gives them the ability to cryptanalyze these IRS documents and so on. And I think that the production cryptanalysis that goes on at NSA probably is at least on the order of one file per day - I don't know; all that's very highly classified. But it's a potential threat that we see currently, and if you look 15 or 20 years in the future, and you extrapolate -
Art
You think NSA today is looking at anybody's income taxes?
Martin
No, but the intelligence community as a whole -
?
Honestly, we don't think so, but that's... In the climate of Watergate, we think that's something we hardly take for granted.
Martin
And the other thing is if you extrapolate three orders of magnitude of improvement over fifteen years, if these figures are correct, you see this $20,000,000 machine becoming a $20,000 machine, the $10,000 per day becoming $10 per day, and I might add that the high degree of - the fact that you have a million replicas of the same chip will probably allow these costs to come down very rapidly, because you'd only have to design the chip once, and then have it copied by laser - maybe just as now we can put on the order of 105 components on a chip, 20 years from now we'll be able to put what are currently 105 chips on a chip.
?
When do you think that's really doable?
Martin
Well, Whit checked into... I think that $10 is doable today, if not yesterday.
Martin
The one microsecond, Whit... neither of us is a hardware expert, but Whit checked with some people who were more knowledgeable, and what were their comments?
?
They said they thought that it could be build in I2L or in Schottky TTL. I gave them an estimate on the number of gates on the chip, and thought that the internal -
?
I thought it was dominated by the S-boxes, at 2000 bits, roughly, of S-boxes, taking about two transistors each to store the bits, so based on a chip of that size, taking into account the fact that you need fewer connections to a purely cryptanalytic chip - it can load most of the stuff serially, bit by bit. It just needs one data-in line and a few control lines, so it could be put on a very much smaller package. They also thought it was very conservative to assume that you'd have 100 nanoseconds per internal round, giving you 1.5 microseconds per encryption.
Doug
I would like to comment on that.
Martin
And I might add that we may be off by a small factor on this, but there's a big difference between this and 91 years, which is five orders of magnitude from... I'd like to see where -
Doug
I think you're off by... at current technology, the only chips that we know how to make of that dense logic are the low-power, relatively low-speed chips. NMOS, PMOS, those kind of things. On those kind of things you can do this in the neighborhood of 40 microseconds. I2L is probably the technology that will give you the kind of density you need at the kind of power you can afford, and that is five or six years from now to get those kinds of densities.
Talking over.
Doug
Schottky TTL - you can't pack that kind of thing in that area - it'd burn up.
Martin
Well, Doug, even if we took your - if we accepted 40 microseconds as the figure currently, that only increases our cost estimate by a factor of 40 - less than two orders of magnitude, which is less than ten years -
?
Marty, I think you don't -
Talking over.
Dennis
When you start multiplying things together, all of a sudden you do get the four or five orders of magnitude, which is the level that you were originally arguing about - as a matter of fact, two orders of magnitude.
Martin
Well, the factor of 40, which you're saying comes in here -
?
Look at the development cost of Hypercube - one, I'm not even sure that 512 have ever been assembled and working, but look at the development cost of ILLIAC IV and divide it by some reasonable number -
Talking over.
?
This is all - everything goes in parallel; you're not talking Hypercube architecture; you're talking about a very -
Dennis
No, the only thing that we were arguing about is just the space that it took to contain the device that you were talking about. And we did go to... As we discussed on the phone, you don't need all the generalities of a general-purpose computer, which is what you're talking about. But just for mean time between failure, I did go to the people at Burroughs and found out how many devices were in the one quadrant of ILLIAC IV that was built. Well, it turns out it's a quarter of a million.
?
But ILLIAC IV was built quite a while ago.
Martin
I'd say two things. Failures are fairly unimportant here, Dan, because, first of all, the typical failure will be that it says that a key is right when it isn't, and you can easily check that. It's very unlikely that the one key out of a billion that's the right one will be missed.
?
You can throw away your dead chips - [??]
Doug
Yes - that's correct.
Martin
And I really... I think MTBF is really an inappropriate argument here. I think technology may improve that, and I think -
Dennis
We were looking at size - was one of the things, and we did look at a theoretical... I thought it was practical, but I'll keep this pointed out, that Hypercube was not the one. Let me just make a quick statement of what the engineer who did design the algorithm for us... By the way, I have plenty of copies - I have three copies of this "Guidelines for Implementing and Using the NBS Data Encryption Standard", which includes many of the things that you're talking about.
Dennis
I brought three along - I didn't know how many people were going to be here; I'd be happy to leave one for each of the major organizations, and if you have any comments, of course...
?
By the way, [??]'s only involvement in this is we have a parking lot that's easier to get to.
Laughter.
Dennis
Anyway... So I sent the letter down, not being an engineer myself, I sent it down to the person that designed our own box like this out of T2L logic and said "Make an estimate that you think is the full state of the art, and what would happen in about five years, based on all of the information that you can collect," and he went to the... an array of a thousand LSI devices did not seem to be unreasonable in the near future. IMS Associates, Inc., are quoted in ComputerWorld, October 29th, as offering 512 Intel 8080 microprocessors in a Hypercube IV. But it takes eight 6-foot 19-inch racks to do it.
?
One very simple objection: What we're doing here is asking the builder of the Maginot Line to analyze its vulnerabilty. I think if you have a question of whether the system is bustable or not -
?
I'm sorry, I picked that engineer simply to design a hardware implementation. He's not the designer of the algorithm.
Talking over.
?
Can you give us some detail - who did design the algorithm?
Dennis
It came out of the Horst Feistel families.
Martin
I brought this problem with key size up with Feistel, and I don't know what his limitations are; he wasn't able to tell me too much, but I know that it left - as I understood him to say, the design left research at one point, and there were many changes made, for understandable reasons, in other parts of IBM, and I think it would be very interesting to have Feistel, who is the father of this, in a way, freely and with no security restrictions comment on the security of this device. The impression I have is that he's currently not free to do that because of either IBM or governmental restrictions on him.
?
This hits a policy issue that... What our concern - this is a paranoia-type discussion, the whole thing.
Martin
I'm not sure it is anymore.
Talking over.
?
I thought that at first, a few months ago. Let's say what the public policy implication of this is. It's a balance problem - if we get a cryptosystem out there that's too hard, it'll give NSA trouble in the future, clearly, no problem on that. If we have something out that's too easy, and it's taken as a government standard, and the public finds out that a standard has been approved for protection of personal information that's easy to bust, they're going to get mad as [??]. The question we really have to balance is national security's concern about the enemy versus the public's concern about distrust of government. Look at any survey about what concerns the public, and their attitudes toward all institutions, not only government, they're very, very concerned - very distrustful of government, and underlying this discussion, I think, is the question: Do we have a standard that's good enough for most threats today, and you can justify what you're doing, but downstream, is this thing going to backfire on us? Is the public going to turn around -
Art
Outside "downstream", this is not - and that's clearly stated - intended to be the standard forever. It's not the Ten Commandments. It's intended for the current threat, as Doug said, for information that you understand today is entirely in the clear.
Talking over.
Art
And this is to protect non-classified information, and there are other means of getting at it.
?
I agree that it's better than what we have; however -
Art
The threats may be much greater than simply the fact of... that can be handled only by encryption. But at current technology, and for the next n years, up to 10, we stand by the statement that this is more than adequate, and that the machine Marty's talking about won't work for the cost, the space, the time that he says it does, and by the time you can do that, the standard will be... We'll always be ahead of them.
?
Can I just respond to this one philosophical point - that what you say is actually true, that this information would be better protected than now, which is in the clear -
Art
And it's subject to other threats that encryption can't handle.
?
This is similar to the doctor that stops at the scene of the accident, gets involved, and provides some medical care, when he had the option to go on and do nothing. The mere fact that he stops and gets involved opens him up to malpractice actions in the future, and here we have a case of a government agency going [?] and its implicit certification -
Art
I'm not certain the analogy is -
Art
Nobody's sitting around wounded.
?
I think the question here is that there's no defense on saying, hey, the information... in five, ten, fifteen years the thing's busted, and people get uptight about it, and you say, well, that was okay, because the protection we provided was better than we would have had without the crypto. So I think the underlying argument here is saying: are we proposing a system that is not strong enough?
Art
And the answer is no - we aren't proposing this - It's strong enough for the purpose for which it was designed, and for the time in which we expect it to be a viable system.
Martin
Let me ask some direct questions about the system -
Talking over.
?
You have several questions; are you going to ask them?
?
I'm going to ask the question: how strong, and what are the assumptions, because clearly we have two very -
Talking over.
Martin
Let me ask some specifics about weaknesses. Do you feel that for the next... I guess the first question is, do you feel that information encrypted today under this standard will be secure 25 years from now?
Art
I don't know what's going to be here 25 years from now, so I don't know.
Martin
But if you wanted to protect against that, you would use a larger key size.
Art
I see nothing in the kind of information that this is addressed [to] that requires 25 years of security.
Martin
Well, census data, medical records -
Art
Census data, as I say, has been around... I don't see anything in census data that requires 25 years' protection.
?
I say it because it's my understanding that it's statutory.
Art
That's actually not your business, it's not my business, it's really the director of the Census Bureau, and if he thinks -
Art
And Congress, and they can request waivers on things. I don't think anybody [?] makes [??].
Doug
Let's say something else about the Census Bureau. The Census Bureau, presumably, is a... I don't know how they intend to keep their information away from people who shouldn't have it. What exists only in electrical form on storage media, and where are they going to have these storage media - are they going to be sitting out on [?] Road for anybody to come up and copy a tape or a disk or something? You've got to ask, what are the various layers of things?
Martin
This is a question of how strong. But, as I understand your answer, if you really need something that would be secure 25 years from now, and that data protected today must be still kept private 25 years from now, you -
Art
I don't know of any unclassified data that requires that kind of protection, and whether it does is a judgment of other people.
Martin
Well, let's not get into that; let's get into technical issues.
Art
I'm not willing to say about anything that it'll be secure in 25 years. I don't think anybody who says he does does knows what he's talking about.
?
Nor am I, and I don't think the issue. I think the issue is... and that's why I raised it, because I think there is a real matter of policy here, which probably deserves to be sent to the level of Congress. I brought Census up as an example because I believe that there's a statutory statement -
Art
I don't think you can tell any Congressman what's going to be secure 25 years from now.
Martin
I'd like to ask one more question. The other question I would like to ask is - against the time of attack I've posed here - that is, against NSA being able to read these things, would you say that it's even secure for the next ten years?
Art
I don't know why you... I spent my career there, and I never read anybody's income tax return. I don't know anybody who did. It's not a target of NSA. NSA is, by litigation,
Talking over.
Martin
But if there's a request from the Executive Branch to do that, what would you do? There were requests by the Executive Branch -
Art
That's a [?] question. If the Executive Branch comes and tells me as civil servant to shoot Marty Hellman, I don't know what I'd do.
Laughter.
Art
I don't know what to say to that. When you're asked to do something, that becomes an existential question.
Martin
But it can be phrased in a way that -
Art
This is a matter bigger than all of us, what the Executive Branch requests.
Talking over.
Martin
Do you feel that over the next ten years the technology that I've suggested, which NSA might use to break this, is something that would be unavailable to NSA? It's not whether they'd do it or not; it's whether it's available to them or not.
Art
Today, it's not available to us.
Martin
Not today, but what about over the next ten years?
Dennis
If it becomes available, we can improve the...
?
Point of order: could they generally [?] what you've said?
Talking over.
Art
I think that's the important thing - to outline what the Bureau of Standards engineers talked about.
Dennis
Let me just tell you how we responded to that. Whether you believe it or not, I'm not here to argue with you on that; I can't change -
Talking over.
Art
You should get this and study it, and if you have any questions...
Dennis
I feel - in fact, I've even stated - that if enough people buy them, the commercial versions of this will probably come down to $10 per chip in quantities of, let's say, 1000. Now I think it may take three to five years before there's enough demand for the commercial versions, or even - I gather you're using the commercial version, is that right? As opposed to using -
Martin
You wouldn't have to. In fact, you wouldn't, because you need the extra register for the known plaintext / cipher pair.
Dennis
Well, we're going to have to go out and buy a million of these at contract. So the company knows that they're going to produce some very special cryptanalytic chips.
?
You can amortize that at maybe a $100,000 setup charge, so it's 10 cents a chip.
Dennis
Setup charge is $100,000 - $150,000, from what we understand. The speeds.... 40 microseconds is what we used. That's the fastest thing that they could put on a 40-pin chip, commercially. They're going for T1 carrier speed, which is about 40-50 microseconds.
?
Well, you could do this pipelined -
?
This is, what, PMOS? NMOS?
Talking over.
Dennis
We looked at the possibilities of going to a million, and the engineer said "No way," so he took a thousand and worked out space and power requirements. We started with an Intel computer per chip, and of course there's no reason to have an Intel computer per chip to control it. What we did do is say you will undoubtedly need at least one other chip to handle the input and output and the bussing and comparison.
?
This was scaled to a thousand because of the practical reasons of communication paths between the thousand elements, or what? Not availability, certainly.
Dennis
No, not availability. Because of power, bus connections, and because of what has been put together as far as space is concerned.
?
Space on what level? You mean space on the boards?
Dennis
Boards, power, and busing connections; things like this.
?
But this doesn't have to be dense, board-wise, because the communication between chips is very restricted, so there are no questions of delay time. I mean, it doesn't matter if it takes you several minutes to load it initially.
Dennis
Let me tell you what the engineers sent back -
Talking over.
Dennis
Anyway, based on this, it came up with, for a thousand devices, that it would take 16 racks of equipment, and a million would take 16,000 racks of equipment, which we priced out at somewhere over $400,000,000 just for, essentially, the racks, I believe - I don't have those figures with me. And 20,000 square feet of floor space.
Dennis
And this was... an optimistic estimate would be one device per 4x5 card, 20 cards per 19-inch chassis, 8 chassis per rack - 160 devices per rack, or 6 racks for a thousand devices - 6 to 8 feet high, etcetera. Like the Hypercube.
?
I think the assumptions, right off - we're starting with an off-the-shelf slow chip, modifying for this operation; you're talking special-purpose chips, special-purpose architecture. I can see the difference in the assumptions, and I think one case is trying to make it as fast as possible; the other set of assumptions are clearly trying to make it expensive as possible and slow as possible. But somewhere between these two is the truth.
Doug
Let me make one additional comment, because you asked about pipelining and so on -
?
Yeah, in the chip itself -
Doug
Well, if you're using a low-speed technology, you might as well go ahead and do the whole thing, kind-of like the two vendors are planning to do it, I think. I said those are about 40 microseconds at $10 or so - maybe $20 in a system - as being state-of-the-art. I said what happens if you take MSI - the best thing we've got now - and [??] 100K ECL line, what it would take to do the algorithm. It took about 80 packages, about $5 or $6 a piece; about $700 all together on a board. Pipelining that, and then taking out the [?] factor on speed, because it's speed versus the cost, turned out to be about the same price.
?
Pipelining in the chip itself, not external to the chip. In other words, your data path path, you say -
Doug
Yeah, but then... Most of the chip is used up with... It's complex logic, which is achieved by memory, which is those S-boxes, and you have to do the same thing over and over again. To replicate them and pipeline doesn't buy you anything in speed in the low-speed technology. In the high-speed technology, it does, but I came out with almost the same dollar value doing it with ECL - well, within a factor of two; it was a little more expensive, but I thought a factor of two, in these kinds of calculations you can't leave anything out. So I did consider using the highest-speed commercial technology versus a specialized chip, which I agree would come down in the neighborhood of $10 for the new chip - it would cost a little more to put into the system. I guess I'm a little between Danny[?] and you guys in a sense.
Dennis
I looked at the pipelining approach, and what you did was you blew up the number of gates, and we came up with about 5000 gates for the algorithm. And for the pipelining you blew up the number of gates, and your size of your chip went up, and the cost went up, so again we balanced out -
?
You can't compete for density with I2L in the next couple years. It looks like what Marty and Whit are saying is not that far from reality, but you wouldn't [??] that kind of thing.
?
I was just going to ask you - in this range that you've identified here, has anyone come up with a believable scenario of a threat, of an incident in which the workfactor would be - where this would be the lowest workfactor, and I suggest that, at least from my experience in looking [at] about 380 of these problems that have occurred, that you would have to go to extreme lengths to build the protection around the whole thing in all other ways, other than the crypto protection, before this becomes the weakest link. And I think... This is a suboptimization kind of situation, and until you're convinced that there is no other weak link, then this becomes unimportant.
Martin
Two comments I'd make to that. One is that when you have - once you have - you know, people accept computer output as gospel truth who don't understand computers. And, similarly, people who don't understand cryptography will accept cryptographic protection as unbreakable, and often, I think, let their other defenses drop. Secondly, I don't think just because there are other weaknesses in the system we should design this weakly. I think if it's no more expensive to design this to be very secure, from my point of view, pretending to be a security officer for IRS, for example - not pretending to be a security officer for NSA, now - I would want to see a larger keyspace. I see almost no addition to the cost in doing this. Because, basically, the algorithm, as it currently is, uses 768 bits of key - well, it needs 768 bits of key. And what they do is take the 56 bits that they actually have, expand it out into 768 bits by repeating the bits in a permuted fashion to produce the 768. And this points out an interesting fact: it's fairly easy to take an algorithm which requires a large key and use it with a smaller key, by key expansion techniques such as you're now using. It's much harder, and not necessarily as secure, to take an algorithm such as this, which has been designed for a small key, and to modify it to use a larger key. And so one of our suggestions, in fact, would be to modify the algorithm so that you could store even up to 768 bits of key. I don't know if you want to go quite that large, because it might make you go to two chips, so I'm not sure that the extra cost would be going to be that much that you would want to do that. When you have a chip... maybe you might even have two chips now: one of them runs the algorithm with 768 bits of key, and the second chip, which accepts any number of bits of key up to and including 768, and it basically expands as many as you put in out to 768, and I see ways that this might be going, and I think that that... I guess what it comes back to is the question of why not do it the more secure way. It's no more expensive, it's stronger, it's more flexible. Why do it the less secure way? Unless it's for the reason that Paul mentions, and that is that there is an interest that NSA has in ensuring that any publicly known algorithm is not too strong. And that gets into the question, then, of who should decide what's too strong? And there's a balance between - there may be a balance between national security from the point of view of gathering foreign intelligence, and national security from the point of view of protecting the constitutional rights of the citizenry, because I see that as national security also. We saw, a few years ago... I feel Nixon did a great service to the country, incidentally, because he made it possible for people to stand up and say "I think the government's doing something cruddy here that it shouldn't do," and they may be listening to it, whereas ten years ago they wouldn't be.
?
If there would have been a 1,000-bit key on some of the data that he wanted, would he have taken that approach - or even a 20-bit key?
Talking over.
Martin
Let me finish my thought. The point is, there's a tradeoff between these two aspects of national security, and a balance has to be struck, and I think -
Art
We feel we've struck that balance.
Martin
Here's the deal. I don't think that the National Security Agency is the appropriate organ of the government to decide where that balance lies.
?
There's a conflict of interest.
Martin
I think that it should be decided by some impartial, but concerned, party.
Art
We have - we do... You keep losing sight of the fact that Don pointed out, that encryption is one of the... Given all the means of penetrating, you find this data encryption only protects a small portion of it.
Martin
Well, why have a crypto standard at all?
Art
I said it doesn't protect nothing; it's a small portion. It protects it from some prying, but if the Executive Branch, these villains, really wanted to, then no encryption would really stop them going at it from every other means of which to get it.
?
Doug, is this... Is a higher level of protection a problem for NSA?
Doug
Paul summed the situation up very well. You also summed up the situation that, you say, we have a built-in conflict of interest.
?
I think we're putting you in an awful position; I don't think you should answer -
Doug
But I think nobody else is in a better position to do it. I don't know what else to say, except that there was very careful consideration given to trying to come up with what was the right factor.
?
The other issue is - since there really can only be an implied answer to your question - is the issue of - if that's not an issue, the question is raised: what are the costs, and is it sensible to raise the level of protection of the algorithm?
Dennis
By modifiying the algorithm to be... what? How high is high? That's one of the questions. 56 doesn't satisfy a requirement, so...
Martin
No, I don't think 64... I think 128 is in a good realm... I mean you can - this is an interesting point, and that is that cost of computation cannot continue to come down at this rate forever; there are quantum-mechanical considerations that come in, and somewhere around 128 bits of key - I haven't done the calculation exactly, but somewhere between 100 and 200 bits of key, I'm sure you could use quantum-mechanical considerations to show that exhaustive search... You know, all of this has been [??] to exhaustive search....
Dennis
Right - you've only looked at one aspect of the algorithm. If you try to look at the other aspects - If we looked at the other aspects, that would be interesting also.
Art
You haven't proved at all that it's weak; I don't - why do you think that it's weak?
?
Some people could think it's weak, and that in itself is a problem.
Art
Some people think 2,000,000 bits is weak. You can think anything - that's the great thing about this country.
?
We're talking about perception of reality.
Art
I have not perceived 56 as weak, and he's not demonstrated -
Martin
Well, that's because you don't see the intelligence community as a threat to the files that I've talked about. I think Paul has summed it up, and what it really comes down to is this tradeoff -
Art
You're talking about that very tradeoff, and we feel that 56 is quite adequate, and we've given out matched plain and cipher to anyone who wants it, and if they can produce the key, we will gladly scrap it.
Martin
Would you use it for -
Art
You want 1,000 bits of matched plain and cipher to produce the key?
Martin
It's not even worth $10,000 for me to break the thing.
Whit
Have you offered a large prize for cracking the algorithm?
?
That's a very interesting question.
Talking over.
Art
I would be very surprised. We don't believe your machine is going to do it.
?
That could well be. I think the issue here is that some people are going to listen to what Marty and Whit said, to become very concerned about it, and the question -
Art
Are they concerned about all the other threats to the information? Are they equally concerned? I mean, if you want to protect against everything, you're going to have to -
Talking over.
Dennis
One of the biggest criticisms of the presentation when people are interested in the algorithm is they say "Gee, what will this do about the authorized user getting to the computer system?" I say "Nothing - why are you talking about it?"
?
This is probably a very troublesome possible solution - that what you have here in the present algorithm once you've already gone through a proven mechanism - is a very powerful, very effective system that's good for everything except very, very, very, very potent threats.
Martin
Or looking to the future.
?
Or in the future, looking backwards and... okay, so you have something that's very, very strong. The point that Marty says is: hey, for a little extra length in the keyspace, you can go over that point where there's any uncertainty or not, and you're pretty damn sure that you're on safe ground. But that poses some other problems: if you do that, you have a lot of people using the cipher and you wish they probably wouldn't - that's another fair reason. OK, so this... The question is: how do you balance these two, these two reqs? Now, clearly, what Marty's saying is going to come out - you can't keep that secret.
Art
But I don't think what he's saying is true; that's the only problem with it. We don't agree.
?
I think in the context that Paul is raising this issue it may not matter.
Art
If he says it's weak, he must demonstrate this in some way. He can't just say it's weak; he... we don't agree with...
?
He's demonstrated enough to raise eyebrows and questions. I think his basic assumptions are not unreasonable.
Art
We don't believe that he can build a machine for that price, at that rate and that speed. When it can be built, we will... if it can be demonstrated that this is a practical solution, we will be the first ones to, to... this algorithm.
Whit
This is an actual question - this is just a matter being brought up in the engineering community, right? - and I think we should now do that, to solicit these speed estimates from the engineering community at large, and we'll get expert answers on these things.
?
I don't think that there's the expertise in this room to really -
Art
I think that the discussion between Marty's thing and our answer is a proper discussion for us.
Martin
This really was called HR 214 initially, and I would propose that we adjourn for lunch at this point, and that we come back and discuss HR 214 after, which we also have to get comments in on, and I apologize to Paul and Don that this has gone too far afield from their... if HR 214 was your primary interest, that this has gone too far afield. And then, after this meeting is over, perhaps, if there's still time for those interested in the key size question to get together and discuss what should be done about this. We realize that there are tradeoffs here, and on the one hand we don't want to take the attitude of... I don't think a security officer should accept the attitude of "Trust us - it's good; we won't tell you how strong..." As I said in my letter to Dennis, it's not quite as blatant as the Russians giving NSA a cryptographic system and saying "Look, we can't tell you why it's good, we can't tell you how good it is, but trust us, it's good." You wouldn't use that, because there are potential - first of all, one of the prime things in security is not to trust anybody without proof. The other thing is they're a potential opponent to the system. Now it's not quite as blatant in this situation; I see a mild analogy existing, and that worries me, and I want -
Art
I feel a little funny that you regard me as an enemy -
Art
Well, that's what you're saying - that NSA is the enemy.
Martin
Not you, specifically. I'd say NSA is the potential...
Talking over.
?
NSA's been sucked into something they shouldn't have gotten sucked into.
Art
No, NSA was a perfectly proper -
Art
No, NSA - the Bureau of Standards shouldn't go to Hellman to answer this question, or anybody else. I see NSA has the expertise. It's up to you to prove the -
End of tape.
Perhaps the most interesting aspect of this entire conversation is that, despite all its post-Watergate-era conjecturing about the executive branch using NSA capabilities to break data belonging to American citizens or corporations, at no point does anyone suggest that if NSA has the resources to break DES, its Soviet or other foreign counterparts might too. The discussion is also almost entirely constrained to the threat against U.S. government information about individuals encrypted in DES, and there's only an oblique allusion to weak encryption being used by organizations other than the government that might be targets of foreign intelligence services.
The use of cryptography in authentication is also not mentioned.
From the Senate Intelligence Committee's report on DES: "The NSA convinced IBM that a reduced key size was sufficient."