Cryptography-Digest Digest #3, Volume #9 Fri, 29 Jan 99 21:13:03 EST
Contents:
Re: some brief questions (Jim Gillogly)
Re: Non exe/com crypto prog (Paul Rubin)
yet another U.S export restriction ques... (chris)
Re: Random numbers generator and Pentium III ("Kazak, Boris")
Re: Spread Spectrum ([EMAIL PROTECTED])
Re: yet another U.S export restriction ques... (Kent Briggs)
Re: some brief questions (David A Molnar)
----------------------------------------------------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: some brief questions
Date: Fri, 29 Jan 1999 17:11:06 -0800
Reply-To: [EMAIL PROTECTED]
Spiffy wrote:
> I'm a high school student and I'm doing encryption for my senior project. I
> have a few questions about things I've read/heard. I'm currently reading
Good questions -- looks like you understand what you're reading.
> * What are all those "unsigned long 0x4b7a70e7" in blowfish's source code in
They're constant values, called "magic numbers" in the trade. In many
designs they're arbitrary but fixed in a way that one can verify they
weren't "cooked" to provide a back door: digits of pi, numbers from the
Rand Corporation book of random numbers, and so on.
> * Does anybody know how to manipulate bits in C or can refer me to a
> website? I'm planning to write a simple encryption program for my project.
Probably your Kernighan and Ritchie text will give you all the bit
arithmetic you need to know. Look at the &, |, ~ and ^ operators in
particular for useful bit operations.
> * In Applied Cryptography, he said that truly random numbers are
> incompressible. Does it follow that incompressible data is random? Example:
> "if P, then Q." Are "If Q, then P," and "If not P, then not Q" true in the
> case of this randomness and compressibility? If so, does that mean I can zip
> up an mp3 file and say that the data is random? In general, is ciphertext
> random?
No, it doesn't follow. Check some of the old threads in sci.crypt about
randomness to get an idea of the flavor of the problem.
> * If computers know they cracked a code by getting ASCII letters, then can't
> I zip it and then encrypt it so they don't see any letters?
Typically not. Zip produces known plaintext at the beginning of the file,
including the letters PK and a lot of other knowable or guessable bytes.
Compressing is better than not compressing, though.
> * Is it really that hard to get "good" random numbers? What's wrong with the
> static from the TV (channel 3 for example) or the radio?
Again, read some sci.crypt threads; this one has been discussed extensively.
The Intel Pentium III chip has been in the news lately, and it includes a
random number generation facility. The Capstone chip (packaging of the
ill-fated and intensely bogus Clipper initiative) also included a RNG.
> * The export laws on strong encryption don't make sense. What's stopping
> somebody from bringing a hard copy of the source code to another country?
> Seems like one of those dumb laws that make politicians look good and that
> are unenforceable.
That's correct. The only thing the export laws do that the pols might
consider useful is that it keeps the fixed targets such as Microsoft or
IBM from blatantly shipping strong crypto. This has allowed them to
prevent the world from coming up with a single standard strong system,
which gives them a little longer to read the general mass of text that
flies across the wires. If real terrorists, pedophiles and drug dealers
want to communicate securely they can do so with no trouble: the software
is available internationally. The export laws are only useful for making
the text of average people and incredibly stupid criminals visible to the
authorities.
> * Is PGP shareware or freeware or neither? If it is one of the previous, is
> it worth downloading even though I probably wouldn't really use it. Btw, is
> the source code available?
If you're going to use PGP for anything commercial you should buy it from
Network Associates Inc. If you're using it for personal experimentation
you can download it yourself from MIT. It's worth getting it and understanding
how it works. The source code is available, e.g. from www.pgpi.com.
> * What are the math/computer courses do you have to take to fully understand
> the posts here and most of the algorithms?
Number theory, linear algebra, and all the general computing courses you can
handle, at least. Read the proceedings of the Crypto conferences for
additional material.
> * Today, how long would it take to crack enigma (the WW2 German encryption
> machine) on a Pentium 2 400 with hardware written esp. for cracking it (you
> know the algorithm and that it is encrypted in it). I heard that enigma has
> 10^(big number) of combinations so I don't see why it's weaker than any
> contemporary encryption algorithm. Wouldn't adding another rotor make it a
> lot more strong?
It all depends. It wouldn't take long to break the same messages broken
during the war by the Allies, given the same quality of "cribs" and the
same kinds of errors by the opponents. However, it is still quite hard
to break an arbitrary short message in 4-rotor Enigma with no crib... at
least with the unclassified methods we know about. There is still a great
deal of classified information dealing with breaking Enigma; it will probably
be declassified in your lifetime. However, it is indeed weaker than modern
algorithms. A single message in 3-rotor Enigma with no crib and 8 or 9
plugs can be broken fairly readily with a low-end Pentium if it's long
enough. Yes, adding another rotor makes it much stronger, and allowing
the user to select from a larger set of rotors and reflectors also makes
it stronger. However, Enigma-specific attacks (such as noticing that
letters don't encrypt to themselves) give it weaknesses not shared by modern
systems.
--
Jim Gillogly
Hevensday, 9 Solmath S.R. 1999, 00:50
12.19.5.16.4, 11 Kan 17 Muan, Ninth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Non exe/com crypto prog
Date: Sat, 30 Jan 1999 01:11:11 GMT
In article <[EMAIL PROTECTED]>,
Michael Paul Johnson <[EMAIL PROTECTED]> wrote:
>
>
>Eli Gamal wrote:
>
>> I need some the expertise of the group. At work we have a new network
>> up an running and my boss and all of my superiors have access to
>> everything in my file space and every message I send and receive. I am
>...
>> deleted). I would like to have some way to encrypt my files for storage
>> to deter my fellow employees. The files I would be encrypting are
>> .doc's (Microsoft Word). It doesn't have to be cryptographically secure
>> though that would be better. I ma looking for privacy not protection
>> from the NSA. The problem is the server restricts the running of .exe
>> and .com files. Are there any encryption programs out there that are
>> not .exe's? Maybe some kind of Microsoft Word Marco or an add-on for
>> Word?
>
>I can think of at least 3 options:
>
>1. Buy your own computer and internet service, and keep all your
>sensitive files on it at home.
If you are trying to keep the files secret from your employer, this
is the best thing to do from both a technical and non-technical point
of view. The non-technical issue is that you're using your employer's
computers to do your own stuff, which may not be such a great idea
for all kinds of reasons.
>2. Use Microsoft Word's built-in password protection (breakable easily
>enough, but not everyone knows how).
If you're using Word 97, the encryption is 40-bit RC4 which is
nontrivial to break (though it won't keep out the NSA). Breaking a
file on a fast PC, even if you know how to do it, takes on the order
of weeks of nonstop CPU crunching. This is good enough to keep out
anyone who's not pretty determined. (If the attacker is the NSA,
they'd break it with expensive special equipment that's a lot faster
than any PC).
>3. Run your an encryption program on your workstation and not on the
>server.
Yes, if the program is good, this would stop pretty much anything.
------------------------------
From: [EMAIL PROTECTED] (chris)
Subject: yet another U.S export restriction ques...
Date: Fri, 29 Jan 1999 22:24:23 GMT
if i encrypt a chunk of stuff with a block cipher, etc, using a 56 bit
key, i am within the U.S. export law, correct?
if i encrypt the same chunk with a block cipher in CBC mode, using the
same key, i am still within the U.S. export law, correct?
what if i take either of those encrypted blocks and then further
encrypt them using a stream cipher. have i then crossed that magic
line?
what if i come up with a new "algorithm" that combines my block cipher
and stream cipher, am i ok then?
or, is the law entirely subjective?
-c
------------------------------
From: "Kazak, Boris" <[EMAIL PROTECTED]>
Subject: Re: Random numbers generator and Pentium III
Date: Fri, 29 Jan 1999 20:30:00 -0500
Reply-To: [EMAIL PROTECTED]
Mok-Kong Shen wrote:
>
> R. Knauer wrote:
> >
>
> > It is called "crypto-grade" to distinguish it from the other kinds of
> > randomness that confuse this discussion.
> >
> > You do know the difference, don't you?
>
> Unless there are scientific tests to determine the 'crypto-grade'
> in terms of figure of merits or the like in quantifiable terms
> nobody (exepting perhaps you) will be able to know the difference!
>
> > The concept of crypto-grade randomness is not profound at all (on the
> > surface anyway). To understand it all you have to do is unlearn all
> > your prejudices that you got from thinking you knew what a random
> > number is, accept the fact that there are different kinds of
> > randomness, and that crypto-grade randomness is not the same as what
> > you were taught before.
>
> Are you suggesting one should forget what scientists have achieved
> through the centuries and 'believe' the religious statement of some
> person that everything from a hardware generator is crypto-grade???
> This group is not the right place for clergymen.
>
> M. K. Shen
=============================
In all the heated discussion about "statistical" randomness
versus "crypto-grade" randomness one crucial thing appears
never to be said in open. We generate the random numbers not
for our own fun, but with a PURPOSE...
If this purpose amounts to Monte-Carlo tests, then we really
do not care how the random numbers are generated, we worry
about their statistical properties. On the contrary, when the
intended purpose is cryptography, then we are sometimes ready
to sacrifice the statistical aspect of randomness in favor of
the much more important aspect - the random number used must
be unguessable to the OPPONENT.
All the concept of "crypto-grade" randomness is based on
the ability (or inability) of the opponent to discover the
right number, or at least to narrow the search down to some
manageable choices. It is exactly here that all the drawbacks
of PRNG's manifest themselves - it is silently assumed that
the PRNG routine is known to the opponent, or at least the
choices for PRNG's are so restricted that it is possible to
find the correct one used in the generation of the number.
It is also silently assumed that the seeding of the PRNG is
easily guessable - time stamp, User ID, or something of the
sort. Violate these conditions, and the number generated by
a PRNG will become as unguessable to the opponent as any
number generated by dice or by keyboard latency.
In short, for a number to be rated as "crypto-grade" we
might know or not know the procedure of its generation, but
our opponent must be unable to reproduce this procedure.
How is this goal achieved - in hardware, or in software,
or in combination of the two, is of secondary importance.
This is why the concept of "crypto-grade" randomness is
psychological even more than it is mathematical. Depending
on the circumstances and on additional information, same
numbers can be rated as "crypto-grade" or not.
Consider the following 32 numbers:
0x6A09E667 0x4520A9C6
0x22AF0A42 0x8B6C6575
0x89F2429C 0x84FEA367
0xADEF9E84 0x9B98BDA7
0x4E717789 0x9E3DB228
0x22B9502F 0x613B6F79
0x7455A930 0x1F620EEB
0x14D2AB03 0x52F1A68D
0x797769F4 0x3AF576DC
0x1B0FF6B4 0x5AB367D8
0xCBFA0F88 0x220CE382
0x640AAF5D 0xA1D860F0
0xAC4BEE57 0x3363002F
0xF8E9C2C8 0xD4097046
0xB23DFD6A 0x5689B0D8
0xAB446C7B 0xC418E961
Do these numbers seem random enough? Yes, if you don't
know how these numbers were derived. If our opponent also
does not know this, any of these numbers can be used as a
genuine "crypto-grade".
But now look at the next table. The first number in this
table is equal to fractional part of sqrt(2), less initial 1,
the second number is its multiplicative inverse mod 2^32+1.
The next 15 lines contain powers of the first 2 numbers,
also mod 2^32+1.
What happens? Our perception suddenly changes, and the
numbers are not perceived as "crypto-grade" any more! Now
it is obvious that the whole table can be easily reproduced
by any opponent...
IF ONLY HE KNOWS THE ROUTINE !!
Power Seed Inverse
1 0x6A09E667 0x4520A9C6
2 0x22AF0A42 0x8B6C6575
4 0x89F2429C 0x84FEA367
8 0xADEF9E84 0x9B98BDA7
16 0x4E717789 0x9E3DB228
32 0x22B9502F 0x613B6F79
64 0x7455A930 0x1F620EEB
128 0x14D2AB03 0x52F1A68D
256 0x797769F4 0x3AF576DC
512 0x1B0FF6B4 0x5AB367D8
1024 0xCBFA0F88 0x220CE382
2048 0x640AAF5D 0xA1D860F0
4096 0xAC4BEE57 0x3363002F
8192 0xF8E9C2C8 0xD4097046
16384 0xB23DFD6A 0x5689B0D8
32768 0xAB446C7B 0xC418E961
If there are any comments, I am listening.
Respectfully BNK
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Spread Spectrum
Date: Sat, 30 Jan 1999 01:28:35 GMT
[EMAIL PROTECTED] wrote:
> Is a computer and software, such as Fast Fourier Analysis required to
> extract recognizable speech from a DSSS transmission or is this
> possible in real time using a wideband receiver with filters, DAC's or
> whatever in the front end, or is it a combination of both?
How you can write a non-technical book on this subject is unclear. Just
to begin to describe these systems requires a fair amount of technical
language. Go ahead, try and explain "orthogonal binary sequences" in
plain language and expect a reader more used to watching movies where
spy satellites always look straight down to understand it...
The answer to your question is: it depends. What is the form of speech
modulation? If the speech a simple narrow-band FM signal (20kHz bandwidth)
which was then spread to 1MHz via some sequence, then, no, a computer would
not be required. Just discover the spreading sequence, build something
which can aquire and lock onto it (numerous chip-level solutions available),
and that 1MHz is despread to a signal which a commonly available scanner can
take care of.
But no one is sending voice this way; low-bit rate voice coders are used.
The 4kbps bitstreams (or whatever) are spread out to 1MHz or so. The
only difference, however, is the the final demodulation.
Does this hypothetical interceptor know the spreading sequence? Are the
sequences from a small set? A predictable set? If not, life is somewhat
more complicated. But not unbearably so.
About the only non-technical way to summarize: yes, it is possible. Yes,
it is within the envelope of amateur/hacker class adversaries. Yes, the job
is made vastly simpler by published digital cell standards. No, elaborate/
expensive equipment is not required.
> I appreciate the responses but they are over my head; I don't know the
> basics well enough.
That, sir, should be a clue. Perhaps you ought reconsider writing a book
about this?
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Kent Briggs <[EMAIL PROTECTED]>
Subject: Re: yet another U.S export restriction ques...
Date: Sat, 30 Jan 1999 01:55:23 GMT
chris wrote:
> if i encrypt a chunk of stuff with a block cipher, etc, using a 56 bit
> key, i am within the U.S. export law, correct?
>
> if i encrypt the same chunk with a block cipher in CBC mode, using the
> same key, i am still within the U.S. export law, correct?
>
> what if i take either of those encrypted blocks and then further
> encrypt them using a stream cipher. have i then crossed that magic
> line?
>
> what if i come up with a new "algorithm" that combines my block cipher
> and stream cipher, am i ok then?
>
> or, is the law entirely subjective?
>
The export regulations prohibit an application from using double
encryption. All encryption meant for export from the U.S. requires at
least a one-time review by the NSA and they will simply reject anything
"cute" that you try to do to get around the 56-bit key limit. You
probably won't even get to use a 56-bit key unless you pick an algorithm
from their "approved" list (RC2, RC4, DES, CAST).
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: some brief questions
Date: 30 Jan 1999 01:45:02 GMT
Spiffy <[EMAIL PROTECTED]> wrote:
Hi there. I'm only replying to things I'm fairly sure about.
> * Does anybody know how to manipulate bits in C or can refer me to a
> website? I'm planning to write a simple encryption program for my project.
You have probably seen the conditional operators || and && for use with
if statements, while loops, and the like. The logical operators are just |
for logical OR and & for logical AND.
a |= b --- a = a OR b
a &= b --- a = a AND b
a ^= b --- a = a XOR b (good one!)
a <<= c --- a shifts left c bits
a >>= c --- a shifts right c bits
> * In Applied Cryptography, he said that truly random numbers are
> incompressible. Does it follow that incompressible data is random? Example:
> "if P, then Q." Are "If Q, then P," and "If not P, then not Q" true in the
> case of this randomness and compressibility?
I do not think so, because in this example :
>If so, does that mean I can zip
> up an mp3 file and say that the data is random?
my gut feeling is "no, not at all", because
that mp3 is not random to begin with. You'll want
to look into the definition of "entropy" and
Shannon's information theory -- there's a Dover
book on the subject, plus someone (Ed Gerck?) just
posted a pointer to scanned copies of his
original papers.
> In general, is ciphertext
> random? Just wondering.
Ciphertext is supposed to look random. It's not, of course, because it's
generated by algorithmic means and as we all know from von Neumann, this
is a "state of sin." In the best case, the ciphertext is
indistinguishable from random data without the key.
This is actually kind of interesting, since you will see
papers which talk about security in terms of how long it
will take a machine to distinguish ciphertext from a
random string. That, or the probability of
> * If computers know they cracked a code by getting ASCII letters, then can't
> I zip it and then encrypt it so they don't see any letters?
That is a good idea. You should always compress before encrypting.
It will not save you, however, since the structure of a zip file
is pretty well known...and besides, you have to assume that they have
at least _some_ plaintext already. Keep in mind that the plaintext can
be something like the header of a Word file. It's not just text - it's
any stereotyped set of bytes.
You may also want to look into all or nothing transforms -- see the thread
here or check out the Crypto and Info Security Group under
http://theory.lcs.mit.edu/ -- with them it's harder to check for a
correct decryption.
> * Is it really that hard to get "good" random numbers? What's wrong with the
> static from the TV (channel 3 for example) or the radio?
Well, the paranoid answer is "someone could beam bad random numbers at you."
More pragmatically, it's apparently hard to remove correlations that arise
naturally. Which is why many people hash the random numbers they get
in order to "concentrate entropy."
There's other threads here which answer this better than I can.
> * The export laws on strong encryption don't make sense. What's stopping
> somebody from bringing a hard copy of the source code to another country?
Nothing.
Except most companies don't have time to deal with that kind of crap.
Especially if their market could give about crypto.
It's a fair bit of work. Plus then you need to keep the international and
the domestic versions separate and synchronized.
Many companies have trouble keeping their beta and shipping versions
properly separated _and_ up-to-date, even when they are both in the
same place and equipped with the latest in version control. Imagine what
happens when your "sync process" is "send courier to Lisbon from New York
with the secret documents."
> Seems like one of those dumb laws that make politicians look good and that
> are unenforceable.
Yes, yes, yes, you're so right. Except it's not particularly profitable to
think about it that way, because you end up treating politicians as
stupid and impotent. This will bite you.
> * Is PGP shareware or freeware or neither? If it is one of the previous, is
> it worth downloading even though I probably wouldn't really use it. Btw, is
> the source code available? ^^^^^^^^^^^^^^^^^^^^
Oh, come on. Set up your own keyserver. Addict your friends. Run a remailer.
(he says even as he forgets to sign this message)
Yes to the last - in fact, it's even available in printed form. Ready to OCR.
To the first :
If you want to use it for profit (encrypting orders or using
at work and such), you pay.
If you want it for personal use only, it's free.
A web search should turn up both, or check out comp.security.pgp.announce and
comp.security.pgp.discuss .
You will also want to check out the GNU Privacy Guard.
> * What are the math/computer courses do you have to take to fully understand
> the posts here and most of the algorithms?
I wish I knew. I'm just starting here at school.
Freshman programming courses help a lot - CS1 and CS2 or their equivalents.
Implementing RSA is a good exercise, even if it's in something like Scheme.
Read and understand _Applied Cryptography_. See what your next impulse is.
If, like me, you get ticked off by the fact that very little "why" is
included (not a criticism of the book -- it's called applied for a reason),
then find the original papers. Read them. Re-read them. Make lists of
terms you don't understand and match them to the course catalog. Look up
references when they interest you (only if they interest you).
Install GSview. Buy the CRYPTO proceedings when they come out. Realize that
some of this is going to be mystifying for a while. It took me a whole
summer to understand modular arithmetic. I'm still trying to
get through the "Random Oracles are Practical" paper (available at
http://www-cse.ucsd.edu/users/mihir/ I think), which introduces the
"Random Oracle Paradigm" that tonz of later stuff depends on.
Linear algebra is very important.
I'm hoping that the classes will follow -- I'm trying to get into
one on crypto this coming term.
by the way, a big thank you in passing to everyone on sci.crypt.
seriously. learning to read here is an education in itself.
> * Today, how long would it take to crack enigma (the WW2 German encryption
> machine) on a Pentium 2 400 with hardware written esp. for cracking it (you
> know the algorithm and that it is encrypted in it). I heard that enigma has
> 10^(big number) of combinations so I don't see why it's weaker than any
> contemporary encryption algorithm. Wouldn't adding another rotor make it a
> lot more strong?
Hopefully someone who spends more time with Enigma will answer this, since
rotor and block ciphers aren't my strong point (but I have Bruce Schneier's
self-study course somewhere around here, and you should too : www.counterpane.com),
but the Enigma cipher has weaknesses in it that allow you to figure out
which combination is the right one without trying them all. The numbers
are very impressive, but don't mean much against such an analytic attack.
Yes, that's vague. :-\ Go read _The Codebreakers_, David Kahn, for
more info.
Contemporary encryption algorithms, if they are any good, do not have
such weaknesses. At least not ones that are that bad. That is why they
are considered secure and Enigma is not.
You might want to look for "Crypt Breaker's Workbench" if you haven't
seen it already. It breaks the algorithm used by the UNIX crypt command,
which is a modified version of the Enigma.
Good luck on your project -- let us know how it goes, why don't you?
Are you implementing something, or just putting together a report?
-David Molnar
------------------------------
** 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
******************************
