Cryptography-Digest Digest #972, Volume #8 Tue, 26 Jan 99 13:13:03 EST
Contents:
Press release - The Crypto Controversy: no problem ([EMAIL PROTECTED])
Foiling 56-bit export limitations: example with 70-bit DES
([EMAIL PROTECTED])
Re: Who will win in AES contest ?? (Bruce Schneier)
Re: Pentium III... (Marty Levy)
Re: hardRandNumbGen (handWave)
Re: The Performance of Meet-in-the-Middle ("Trevor Jackson, III")
Re: Unicity, DES Unicity and Open-Keys (Mok-Kong Shen)
Re: Unicity, DES Unicity and Open-Keys (Mok-Kong Shen)
Quadibloc III spec wrapped up... (John Savard)
Random numbers generator and Pentium III (student)
Re: hardRandNumbGen ("Trevor Jackson, III")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.security.pgp,mics.legal.computing,talk.politics.crypto
Subject: Press release - The Crypto Controversy: no problem
Date: Tue, 26 Jan 1999 15:45:58 GMT
The Crypto Controversy: no problem
===========================
Tilburg, the Netherlands, 26 January 1999
The Dutch government should do nothing about the problem that
cryptography poses to law enforcement. All available options have more
negative than positive consequences. This is the conclusion of
Bert-Jaap Koops in his recently published Ph.D. thesis "The Crypto
Controversy". Although encoding programs potentially leave
law-enforcement powerless to wiretap communications and to conduct
computer searches, there is not a real solution to retrieve the keys
to decipher encoded data.
Koops, author of the Crypto Law Survey website, conducted a four-year
research at Tilburg University and Eindhoven University of
Technology. He analyzed the conflict of interests that cryptography
poses to society. On the one hand, encryption is crucial for
information security and for protecting privacy, but on the other
hand, it enables criminals to escape the scrutiny of law enforcement.
Governments are trying hard to address this conflict of interests,
but their proposals for regulation have been controversial. The
policy debate is polarized, with privacy activists and
law-enforcement agencies fiercely opposing each other's point of
view.
To address this crypto controversy, Koops discusses four possible
solutions: building-in Law-Enforcement Access to Keys (LEAK systems),
demanding suspects to decrypt, using alternative investigation
measures, and doing nothing. The first option is flawed, because
secure LEAK systems are not yet available, and criminals will anyway
not use crypto which they know to contain a backdoor for the police.
The second option, demanding suspects to decrypt, yields only very
limited opportunities, because of the privilege against
self-incrimination. Alternative investigation measures, such as using
directional microphones and intercepting radiation from computer
screens, can provide some leeway for the police if wiretaps lose
their efficacy, but they are serious infringements of people's
privacy.
Koops concludes that, for the time being, the "zero option"
is preferable: governments should decide upon a policy to do nothing
about the crypto problem. To meet developments in crime and
cryptography, this policy should be reviewed periodically. "Perhaps
the government will slowly have to adapt to the idea that wiretapping
is not a panacea for the information need of the police."
As Koops suggests: "if there is no solution, there is no problem
either." Rather than continue to worry over the crypto controversy,
the government should concentrate its energy and resources on other
pressing social issues which it can address.
==========================
Publication details
==========================
Bert-Jaap Koops, The Crypto Controversy. A Key Conflict in the
Information Society. The Hague / London / Boston, Kluwer Law
International, 1999, 301 pages, ISBN 90 411 1143 3.
A summary and ordering information are available at
http://cwis.kub.nl/~frw/people/koops/thesis/thesis.htm
=========================
Curriculum vitae
=========================
Bert-Jaap Koops (1967) studied mathematics and
literature at Groningen University. After working for Amnesty
International for two years, he started a Ph.D. research at Tilburg
University and Eindhoven University of Technology at the faculties of
law, mathematics and technology management. Since October 1998, he is
a senior research fellow at the Centre for Law, Public Administration
and Informatization of Tilburg University.
Koops is editor of the Dutch reference book Recht &
informatietechnologie. Hij co-edited a book on Emerging Electronic
Highways and has published widely on crypto regulation, computer
crime, and Trusted Third Parties. He maintains an extensive worldwide
survey of crypto laws on the Internet.
=============================
Bert-Jaap Koops <[EMAIL PROTECTED]>
Tilburg University
13 January 1999
------------------------------
From: [EMAIL PROTECTED]
Subject: Foiling 56-bit export limitations: example with 70-bit DES
Date: Tue, 26 Jan 1999 15:47:58 GMT
List:
The Wassenaar Arrangement [WA, WA98] can be seen as defining a
current lower limit for the bit-length security parameter of
symmetric ciphers, which should be larger than 64-bits. However,
ciphers that obey this very limit cannot be freely exported -- due to
the export limitation of 56-bits imposed by the WA.
The objective of this communication is to show how the 56-bit export
limitation can be foiled in a practical system for DES [MOV97],
affording for example 70-bits "perceived secret-key bit-length" --
while still complying with all terms of the WA for 56-bit DES. Thus,
the scheme to be presented here should be freely exportable *and* lie
on the higher level of security. But this discussion is not only a
"proof of principle" that bit-length export limitations can be easily
foiled -- since the added overhead is slight, the scheme is also of
practical importance.
Consider a hypothetical 14-DES Standard, which would specify (for
example) 2^14 pre-defined and publicly known 64-bit random blocks.
Now, Bob would choose one at will and use his choice to XOR-encode
all 64-bit DES blocks calculated with the 56-bit secret-key he shares
with Alice -- without disclosing his choice (i.e., anyone else would
ignore the choice). An attacker would have a workload (2^14)/2 =
8,192 times higher on average for all 56-bit key combinations to be
tried -- which would effectively raise the DES key-length from 56 to
70 bits. But the intended recipient Alice, who knows the 56-bit
secret-key, would just have to try out an average of 8,192 DES
decryptions of one 8-byte block in order to find out which seed was
chosen -- a small initial overhead.
In the above example, no one knows (neither Alice nor anyone else)
which of the 8,192 possible schemes Bob did use -- everyone openly
ignores it. Thus, this situation can be defined as "open ignorance".
This is in contrast to the usual technique of adding "salt" (random
data) to the plaintext, or to the algorithm's bit manipulation as
done in the "crypt" procedure for UNIX passwords [MOV97, p. 393-394].
These forms of adding variability do not actually benefit from open
ignorance to make a brute-force attack more difficult because the
"salt" is publicly known -- it is not an unknown key. Actually, their
main purpose is to make a dictionary attack more difficult [MOV97].
Further, even if unknown, "salt" added to the plaintext would not
increase the attacker`s workload for a brute-force attack.
In summary, the concept of open ignorance was exemplified with 56-bit
DES encryption and shown to easily bootstrap key-length by a large
factor to e.g., 70-bits -- without breaking any export restriction on
the 56-bit limitation since all 2^14 random blocks are pre-defined
and publicly known. Which raises the attacker's perceived bit-length
even above the limit of controlled export [WA98], of 64-bits for
symmetric ciphers such as DES.
For a further discussion, a different example with Triple-DES and a
comparison with the concept of "open-keys", please see [Ger99].
Comments are welcome.
Cheers,
Ed Gerck
=============================================
REFERENCES:
[Ger99] Gerck, E., "Unicity, DES Unicity, Open-Keys and Open
Ignorance", in http://www.mcg.org.br/unicity.htm
[MOV97] A. Menezes et al., Handook of Applied Cryptography, CRC
Press, New York, 1997.
[WA98] http://www.wassenaar.org
______________________________________________________________________
Dr.rer.nat. E. Gerck [EMAIL PROTECTED]
http://novaware.com.br
--- Meta-Certificate Group member -- http://www.mcg.org.br ---
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Who will win in AES contest ??
Date: Tue, 26 Jan 1999 16:28:21 GMT
On Tue, 26 Jan 1999 10:48:51 -0000, "Sam Simpson"
<[EMAIL PROTECTED]> wrote:
>>I thought Twofish was ultra conservative.
>
>But Serpent is even more so, right?
Yes. But we tried to combine ultraconservative with performance.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: Marty Levy <[EMAIL PROTECTED]>
Subject: Re: Pentium III...
Date: Tue, 26 Jan 1999 16:05:24 +0000
Does anyone know the mechanism Intel plans to use to put the infamous serial
numbers on Pentium III chips? I wasn't aware that Pentiums had any
non-volitaile memory (other than ROM) on board. The only practical systems I
can think of is to use a fuse or laser repair type scheme.
------------------------------
From: handWave <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 08:18:01 -1000
Mok-Kong Shen wrote:
>
> handWave wrote:
> >
>
> > > Even the presmption that the output would pass statistical tests is
> > > questionable. One famous gafffe in PRNG design was Knuth's composite
> > > generator, which he called superrandom. Unfortunately it was a closed loop
> > > design.
> >
> > It was a computer program.
>
> Having previously taken part in discussions in several threads of
> this group on random number generations, I doubt nevertheless that
> I have really known an answer to the following question:
>
> If I have two sources of randomness, one software and one hardware,
> both passing all statistical tests I apply equally well, why should
> I choose one source in preference to the other?
Consider than many situations RNGs are used for. In two dimensions there
are four scenarios:
1 You want repeatable outputs or you want unpredictable outputs.
2 You use the RNG is a vaults with trusted guards or you use it in a
college dormatory where you made some energetic enemies.
The preferences become clearer in those situations.
>And if additionally
> I don't know which sequence I get is from software and which is from
> hardware? (Compare the Turing test.) How does the origin of the
> sequence affect the workload of the analyst,
In that case you may chose either one with a chance of making a bad
choice, depending on the future situational dimension in which it will be
used. Random numbers sometimes seem nonrandom, hence lottery players
sometimes find a lucky number or see a pattern.
>if the software
> generation process involves so many parameters that for combinatorical
> reasons he has no chance of directly dealing with them but has
> to try to look instead for possible regularities/irregularities in
> the sequence itself and, by assumption, the sequences from the
> two sources are of equal statistical quality? (Note that the
> hardware source is (in my humble opinion) unpredictable simply
> because there are so many participating 'parameters' that the
> 'summation' (the end product) becomes unpredictable, cf. the casting
> of a dice.)
>
> M. K. Shen
The scenario in which the RNG will be used makes the choice clearer. Pick
a purpose: repeatability for stream ciphers, then use a PRNG. For key
generation use a RNG based on hardware. If you are in the college dorm
with enemies who may interfere remotely, then a thermal noise generator
from an avalanche diode with a high gain amplifier breadboared using
wire-wrapped, unshielded circuits is a bad implementation.
------------------------------
Date: Tue, 26 Jan 1999 12:05:05 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: The Performance of Meet-in-the-Middle
handWave wrote:
> David Wagner wrote:
>
> > By "almost" wrong, I mean that as far as I can tell the MITM attack has
> > time complexity bounded by O(k * 2^k), which is only logarithmically slower
> > (logarithmic in O(2^k)) than the naive estimate O(2^k).
> > I could well be confused; it's easy for me to make mistakes when I try to
> > do theory. If I am, I hope you'll point out where I went wrong.
>
> O(2^k) = O(k * 2^k) by definition of Big Oh Notation
I don't think so. Classical O() notation suppresses all but the largest term in
an expression. Terms are combined by addition and subtration. You are proposing
to suppress factors within a term, which is foreign to my experience.
By your definition O(N) = O(N log N) which is typically considered false.
In this specific example, O(k * 2^k) is identical to O( 2^(k + log2 k ) ). There
is no sense in saying O(2^k) = O( 2^(k + log2 k ) ).
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Unicity, DES Unicity and Open-Keys
Date: Tue, 26 Jan 1999 17:19:53 +0100
[EMAIL PROTECTED] wrote:
>
> Unicity, DES Unicity and Open-Keys
>
> Archived at http://www.mcg.org.br/unicity.htm
I have a tiny question. You say that 'magic numbers' or 'information
tags' enable the analyst to identify the compression algorithm.
Could one suppress that, i.e. let it be part of the secret information
of the communication partners? One could also vary the algorithm
setup (the Huffman table, etc.) depending on some (time-varying)
value not known to the analyst, I suppose.
More generally: It is commonly assumed that the analyst knows the
encryption scheme one uses. But this is reasonable if one repeatedly
uses the same scheme. If one has a fairly large set of schemes to be
chosen according to a secret schedule, then the analyst has first of
all to figure out the scheme actually being used, i.e. he has a much
higher work load. I believe all this could be subsumed under the
paradigm 'Security through variability', which underlies, in
particular, those algorithms that are parameter-dependent (analogous
to parametrized data types in programming languages; the parameters
can be regarded as kind of 'key extensions' which is of interest
in the context of the Wassenaar regulation).
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Unicity, DES Unicity and Open-Keys
Date: Tue, 26 Jan 1999 18:11:27 +0100
Patrick Juola wrote:
>
> How large is "a fairly large" set of schemes, in this context?
> I'm rather suspicious of introducing a thousand new and insufficiently
> tested encryption algorithms in the interests of adding another ten
> bits of security. On the other hand, I don't see creating another
> three bits of key as necessarily being useful; that puts off the
> apolcalypse for, what, two years (Moore's law and all)?
Well, choose 50% of the modern block ciphers described, say, in
Schneir's book. I think that (in fact small) 'variablility' is
sufficient to cause very essential trouble to the analyst. A
parametrized cipher has similar, though perhaps less significant
effect, since the method of attack remains the same. (The variants
of 3-DES discussed in another thread can be considered as such.)
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Quadibloc III spec wrapped up...
Date: Tue, 26 Jan 1999 17:10:39 GMT
Some time back, I noted that I'd finally finished the spec for
Quadibloc II. But I felt that the more elaborate Quadibloc III was
still subject to change.
Well, Quadibloc III has finally recieved the blessings of a recent
inspiration.
The combined shift register and SIGABA process for generating initial
values for the subkeys has now been modified by adding an extra layer
to the rotor machine part, and making its lowest level a type of shift
register instead of an odometer.
In addition, the second run of that process, which used nine bytes of
output to modify eight bytes of subkey material, now includes two
concurrent transposition (and XOR in one case as well) operations on
the preceding and following blocks of 256 bytes, to further obscure
any pattern the subkey generation process might leave.
Essentially, Quadibloc III is an illustration of a no-holds-barred
block cipher, containing all sorts of complications thrown in so as to
make it impossible to analyze. No attempt is made to reduce RAM use or
to meet a particular efficiency goal, although the size and complexity
were limited by using Quadibloc II as a starting point.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: student <[EMAIL PROTECTED]>
Subject: Random numbers generator and Pentium III
Date: Tue, 26 Jan 1999 16:59:21 +0100
Hi !
I have few questions:
1. How secure are "random" numbers generated by measuring mouse
movements or recording keystrokes ? Are they random enought to be used
with OTP, when we want to protect data against the most resourcesfull
enemy ? If not, why ? (If we want very random numbers we can collect a
lot of less-random data in this way and produce small quantity of
randomness-enougth numbers, so theoritically, we can reach any level of
randomness.)
2. How can we know, that RNG embedden in Pentium III is really random ?
Are there any methods to detect any subtle pattern in data from the RNG,
if there are any (if there are any methods, please describe them)? It is
possible to design "Random" Numbers Generator with such a pattern, give
it to people, and in this way we have a something like key-escow
ciphers.
Thanks in advance
T.H. ([EMAIL PROTECTED])
------------------------------
Date: Tue, 26 Jan 1999 12:15:34 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: hardRandNumbGen
handWave wrote:
> Trevor Jackson, III wrote:
>
> handWave wrote:
> > > I am glad you raised the "handwaves" metaphore, because handwaves are
> > > what toss coins. A complex person tosses a coin and you might think it
> > > is random. The oscillator RNG in this discussion is directly analogous
> > > to a coin toss in many ways. If a coin is not rotating (oscillating)
> > > it will fall back into the hand in the same position that it stated from.
> > > It is the rotation that helps the randomness, not only the complexity
> > > of the nervous system, the elasticity of the skin, and the trembling of
> > > the muscles. The rotation should be fast for best results. A juggler
> > > could become skilled at non-random coin tosses for one coin that
> > > rotates slowly. But if she tosses three coins with rapid rotation than
> > > it is likely that random results will occur. If a periodic wind is
> > > present in a coin toss, yes, it will influence the outcome, but the
> > > result will often be recognizable as a useful random throw, or a throw
> > > that was blown away. The same with this RNG.
> >
> > Human gestures are not a good foundation for system design. There are large,
> > industrial concerns that rely upon human-gesture-generated unpredictability.
> > Their interest is *not* statistical randomness as we find in simulations,
> > games, and Monte Carlo tests (in spite of the latter name). Their interest
> > is the same as ours: unpredicability. They are called casinos.
>
> The product I designed was evaluated for casinos by Bally, a potential
> customer.
>
> >
> > In spite of the fantastic efforts taken to eliminate predictability in games
> > of chance human gestures can still dominate the outcomes completely. I'm not
> > referring to shuffling cards systematically, but to rolling a roulette ball
> > against the wheel so precisely that out of 20 tries a human can obtain a
> > predicted outcome (slot 17) 10 times. 50% success. I think that constitutes
> > predictability.
>
> Yes, this is like the skilled juggler I described above. The analogy to a
> hardRandNumbGen is a skilled hacker who controls the power supply noise,
> the clock glitches, the radio beams so that the RNG becomes under his
> control. The chip designer must anticipate such antics, and prepare the
> module for lunar insertion.
>
> > The hand-eye coordination involved is of an extreme level, requiring decades
> > of practice to achieve. But it is real. The complexity of controlling a
> > roulette wheel appears to me to be far larger than that of a coin toss. Even
> > a fast one.
>
> I dispute this. A coin has one bit of output, a wheel has many bits in
> one toss. A wheel is a big target with a smaller bandwidth for RPMs. A
> coin has a wider bandwidth, perhaps 1hz to 50 hz, a wheel, from .1 hz to
> .5 hz on the initial spin. A coin may be tossed from a rooftop. Wheels
> would fracture under such conditions.
Then we disagree strongly. My statement was not based on the degrees of freedom of
the two systems, nor on unanticipated operations on the hardware such as
defenestration. I was referring only to the degree of practice required by a human
to reach a particular skill level. For instance, to get a 10% advantage given the
standard payoff odds. I doubt an average person could control a roulette wheel
that well after a year of practice. OTOH, I think an average person could reach
that level of skill with a silver dollar after a few days or a week.
Clearly the coin and the wheel are part of the physical universe and thus subject
to the same set of arcane and esoteric influences. But the coin is much easier to
control than the wheel. So we have to assume that a coin is not as good a source
of entropy because it is too easy for an external influence to inject bias into the
results.
[ mega snip]
As for the rest of your response, I can only harumph and murphle, which are not
productive of enlightenment.
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
