Cryptography-Digest Digest #110, Volume #13 Mon, 6 Nov 00 16:13:01 EST
Contents:
Re: On obtaining randomness (Mok-Kong Shen)
Re: On obtaining randomness (JPeschel)
Re: Brute force against DES (Dan Oetting)
Re: On obtaining randomness (Alan Rouse)
Re: rijndael and public/private key encryption (Mike Rosing)
Random Number Newsgroup ("John Feth")
Re: rijndael and public/private key encryption (Paul Schlyter)
AES only 128 bit-blocksize? (Makoto Miyamoto)
Re: On obtaining randomness (Mok-Kong Shen)
Re: Hardware RNGs (David Schwartz)
Re: blowfish (David Schwartz)
Re: Random Number Newsgroup (Mok-Kong Shen)
Re: Psuedo-random number generator (David Schwartz)
Re: hardware RNG's (David Schwartz)
Re: AES only 128 bit-blocksize? (Tom St Denis)
Re: XOR Software Utility (freeware) available from Ciphile Software (Tom St Denis)
Re: example code for your use (Richard Heathfield)
Re: example code for your use (Chris Hills)
Re: Hardware RNGs (David Schwartz)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On obtaining randomness
Date: Mon, 06 Nov 2000 19:10:25 +0100
Dan Oetting wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> > If I choose ten books
> > and put them in series, the
> > number of possibilities is astronomical.
>
> > So if I use a
> > sufficiently long secret key to make such a choice
>
> Does this secret key magicaly appear or will you be using some
> predictable ritual to create it. If you could pull a random secret key
> out of your head you wouldn't need the rest of this process.
You could cast dice or do as you said, relying on the
randomness of your neurons, in case you have confidence
on that. Note also that security is in the end more or
less a subjective issue, there being yet no scientifically
rigorous unit of crypto strength like the units in physics.
>
> > it is
> > almost certain that the opponent can't know which set
> > (sequence) of books I use,
>
> Unless they get a court order requireing the local book store to turn
> over the records of which books you purchased. (sorry, just had to throw
> in a little local politics)
Even they could have obtained a record, the choice can be
huge enough if the number of books to be chosen from is
sufficiently large, thanks to combinatorics.
>
> > Then I shuffle these in small units
>
> Shuffling is another process that uses a random source to make
> decissions yet you don't explain where this random source originates.
That could be from another source or from the same source.
See the algorithm of Bays and Duncan in Knuth vol. 2 which
uses the same source to shuffle.
>
> > Finally I use a good hashing
> > algorithm to concentrate the entropy, leading to
> > sufficiently good randomness and ensuring that the
> > opponent can't reverse my processing.
>
> This is good, if your opponents steals your random number you don't want
> them to be able to deduce what books you read :)
>
> You are starting from the undenyably huge entropy of all words that
> could be written. But reduce this to the set of books printed by one
> publisher. Your entropy is now at most the number of books published
> since the content of these books is fixed and known. You choose and
> shuffle which adds more entropy but only if this entropy is from a
> secure random source. Your choice of books could be leaked since it
> requires external access to the books. And you could use the very best
> PRNG for the shuffle but it will add no entropy if it starts from a
> known state. You might as well just draw 10 numbered beans from a can.
We are considering 'practical' security here, i.e. enough
of complication to prevent the opponent from succeeding,
not 'theoretical' security. (The scheme operating on a
fixed set of books certainly wouldn't suffice to supply
sequences for securely encrypting an 'infinite' amount
of plaintexts. This is easily seen from the analogy of
the impossiblity of perpetum mobile.) Consider the common
case of block encryption, where you can use a key of, say,
128 bits to encrypt a large number of blocks, i.e.
resulting in a very large number of bits that the opponent
can't deal with, if the cipher is sufficiently strong.
There is only 128 bits of entropy working in there, isn't
it? (It should actually only be able to protect 128 bits
of plaintext, if 'perfect' security is required.) This way
I suppose you could better see why with a short key to
select the books (or equivalently selecting a number of
other sources) can with the scheme described nevertheless
result in large amounts of 'sufficiently' random sequences
for use in 'practical' applications. This (general)
phenomenon of apparently yielding more (unreal) entropy
is paradoxical but can be explained in my view by the
fact that one doesn't need in practice 'perfect security'
as defined by Shannon but only some inferior quality
security (provided by the practical encryption schemes)
that is nonetheless above the threshold that the opponent
is able to attain in order to launch a successful attack
of the encryption involved.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: On obtaining randomness
Date: 06 Nov 2000 18:35:18 GMT
Mok-Kong Shen [EMAIL PROTECTED] writes, in part:
>It is interesting to note that natural language is often
>not powerful (efficient) enough to transmit thoughts, i.e.
>what is quite clear to one person may not be so to the
>other.
Especially if you can't use the language correctly.
J
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Dan Oetting <[EMAIL PROTECTED]>
Subject: Re: Brute force against DES
Date: Mon, 06 Nov 2000 11:38:23 -0700
In article <8u1d4t$1vil$[EMAIL PROTECTED]>, "Samir"
<[EMAIL PROTECTED]> wrote:
> (Excuse my English, I'm French...)
>
> I search some informations about the brute force against DES.
>...
> Is the best way to the server to search with ramdom selection ?
The best search order for DES uses GREY codes. In a grey code search
only 1 bit of the test key changes each iteration. If you look at the
DES algorithm it's easy to see that changing some bits of the key do not
affect the first round calculations and have limited effect in the
second and third rounds. Similarly, some bits have limited effects on
the last rounds. The calculation cost for incrementing each key bit can
be measured and the bits ordered so the cheapest bits are incremented
first.
Even when using a hardware DES cracker, a grey code search order will
reduce the number of bits changing state and so reduce the power and
cooling requirements.
#define GREY(count)=((count)^((count>>1)))
------------------------------
From: Alan Rouse <[EMAIL PROTECTED]>
Subject: Re: On obtaining randomness
Date: Mon, 06 Nov 2000 18:42:22 GMT
While we're waiting for the complete literary works of the human race
to appear in digital form, we could settle for another source that is
already available--the local CD store. Imagine how much entropy could
be mined from the thousands of CD's at your local Media Play... enough
to suffice as a onetime pad for a long long time, even with very
conservative amounts of entropy being taken. And you don't even need a
secure channel for exchanging bits!
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: rijndael and public/private key encryption
Date: Mon, 06 Nov 2000 12:44:54 -0600
shren wrote:
>
> Can Rijndael be used for public/private key encryption? I'm new to the
> whole cryptography field, but like every other programmer on the planet
[...]
> It looks like it's only geared for single key encryption, using the
> same key for encryption and decryption. Am I missing something?
Nope, you're not missing anything. It's supposed to be a symmetric cipher.
To exchange keys you need a completely different beast. That usually
requires a lot more chunks of code which are totally independent of this
chunk. Do a web search on "PKI" and you'll find more than you can deal with :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: "John Feth" <[EMAIL PROTECTED]>
Subject: Random Number Newsgroup
Date: 6 Nov 2000 18:45:06 GMT
Does anyone know how the new random number newsgroup is coming along? I
haven't heard anything since I (and other voters) were notified that the
vote was to establish a newsgroup dealing with random numbers.
Thanks,
John Feth
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: rijndael and public/private key encryption
Date: 6 Nov 2000 19:31:45 +0100
In article <CjCN5.128362$[EMAIL PROTECTED]>,
shren <[EMAIL PROTECTED]> wrote:
> Can Rijndael be used for public/private key encryption? I'm new to the
>whole cryptography field, but like every other programmer on the planet
>I'm working under deadlines.
No -- Rijndael is a symmetric crypto which uses the same key both to
encrypt and to decrypt. Naturally, such a key cannot be made public.
> Looking at the code:
>
>int makeKey(keyInstance *key, BYTE direction, int keyLen, char
>*keyMaterial);
>
>int cipherInit(cipherInstance *cipher, BYTE mode, char *IV);
>
>int blockEncrypt(cipherInstance *cipher, keyInstance *key, BYTE *input,
> int inputLen, BYTE *outBuffer);
>
>int blockDecrypt(cipherInstance *cipher, keyInstance *key, BYTE *input,
> int inputLen, BYTE *outBuffer);
>
>int cipherUpdateRounds(cipherInstance *cipher, keyInstance *key,
> BYTE *input,
> int inputLen, BYTE *outBuffer, int Rounds);
>
>
> It looks like it's only geared for single key encryption, using the
>same key for encryption and decryption. Am I missing something?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: Makoto Miyamoto <[EMAIL PROTECTED]>
Subject: AES only 128 bit-blocksize?
Date: 06 Nov 2000 00:00:54 +0100
Hi,
I'm curios, if the AES is only defined with 128 bit-blocksize or if
all blocksizes mentioned in the Rijndael-paper are considered as AES?
Makoto
--
Hi! I'm a .signature virus! Copy me into ~/.signature, to help me spread!
-= Registered Linux User # 183415 =-
[EMAIL PROTECTED] or @gmx.de
[EMAIL PROTECTED]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On obtaining randomness
Date: Mon, 06 Nov 2000 20:38:32 +0100
JPeschel wrote:
>
> Mok-Kong Shen [EMAIL PROTECTED] writes, in part:
>
> >It is interesting to note that natural language is often
> >not powerful (efficient) enough to transmit thoughts, i.e.
> >what is quite clear to one person may not be so to the
> >other.
>
> Especially if you can't use the language correctly.
There is practical advantages in crypto in case the opponent
doesn't have competence in a foreign language that one uses,
as described in Kahn's book about employing a foreign
language by the British army in WWII to defeat Japanese
interception. So the same 'theoretical' entropy could be
said to have different 'practical' entropy.
M. K. Shen
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Date: Mon, 06 Nov 2000 11:37:35 -0800
Alan Rouse wrote:
>
> >If you use Yarrow, all you have to get right is
> > the expected entropy per bit of each of your sources, and then it will
> > safely produce only unguessable bits.
>
> My point is, the output bits from a hash function are no more
> unguessable than the input bits. My underlying assumption is that your
> algorithm is not secret--a pretty standard assumption in cryptography.
This really depends upon your definition of 'unguessable'.
Let me give you an example. I have an input stream which is truly
random but highly biased. Say one bit in a thousand is a '0' and the
rest are all '1's. This stream is guessable in the sense that if you
guess that a given bit is a '1', you'll be read 99.9% of the time.
Now I take 1Mb of data from this stream and run a SHA1 on it. You
couldn't guess a single bit in the output of that hash with a
probability any better than half. So the output of the hash function is
far more unguessable than the input.
The output does not contain more entropy than the input, of course. It
will always contain slightly less.
DS
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: blowfish
Date: Mon, 06 Nov 2000 11:35:13 -0800
[EMAIL PROTECTED] wrote:
>
> Hi ...
>
> I've had the "honor" to translate the blowfish algorithm from c to java
> and i wonder ... can it be done ?
>
> If yes! Hasn't it been already made by someone else ? If so is there
> any good site you would recommend so i can download it thus saving
> precious time ....
>
> Thanx in advance for all help.
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
http://www.acme.com/java/software/Acme.Crypto.BlowfishCipher.html
DS
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random Number Newsgroup
Date: Mon, 06 Nov 2000 20:40:38 +0100
John Feth wrote:
>
> Does anyone know how the new random number newsgroup is coming along? I
> haven't heard anything since I (and other voters) were notified that the
> vote was to establish a newsgroup dealing with random numbers.
We have since quite a time sci.crypt.random-numbers.
M. K. Shen
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Psuedo-random number generator
Date: Mon, 06 Nov 2000 11:46:33 -0800
> Your program processes physical randomness, while he meant
> that a stream from a PRNG (often realized in software)
> can't contain more entropy than the key (seed), because all
> that is derived deterministically.
>
> M. K. Shen
My point was simply that his stated claim:
> > > Running a computer program cannot generate entropy.
Is false. Actually, every physical process generates entropy,
contributing to the eventual heat death of the universe.
DS
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: hardware RNG's
Date: Mon, 06 Nov 2000 11:45:05 -0800
Alan Rouse wrote:
> First, you might have a smaller set of possible values than you
> expect. That can result because your source of supposedly random
> inputs doesn't have as many possibilities as you expect. Or it can
> result because your hash (or PRNG) function doesn't map all your
> possible inputs uniquely to an equal number of outputs. (In other
> words, two different inputs might yield the same output).
You have to know what the range of possible values is. I admit, it's
extremely difficult to carefully trace (in a laboratory) the initial
randomness that you know is there (clock skew) all the way to the
digital end results. Yes, the end results look random, but that doesn't
prove that real physical randomness is the source of the apparent
digital randomness.
However, you can measure the real physical randomness in the input
directly. Crstal oscillators do in fact wander due to microscopic
temperature variations and fast Pentium processors are fast enough to
measure this randomness. I can assure you that first-order compensation
of a typical crystal oscillator is not nearly good enough to achieve
zero measurable drift -- that would be equivalent to a clock whose error
per day was stable to a hundred thousandth of a second. Even the best
crystal ovens have difficulty being that stable -- to expect a cheap,
unstable oscillator going into a cheap, noisy multiplier is insane.
> The second way it can fail is if the possible input values happen with
> different probabilities. If this is the case, an attacker who
> understands the problem can search the most likely values first,
> reducing the expected time to find the target value.
Assuming you use a proper hash function, all that matters is precisely
how much entropy is in the input.
> You might be
> able to overcome by increasing the size of the input seed. But the
> difficulty is in knowing how much is enough. As far as I know, the
> best you can do is to estimate carefully and then add a lot more bits
> than you think you need, and hope it is enough.
If you know the maximum error bound in your estimate (at least in the
downward direction), then hope is not needed.
> I don't know of a good way to overcome the faulty PRNG / hash problem.
> Perhaps the best you can do is to use a PRNG based on a well-studied
> crypto function such as DES, whose weaknesses are well understood, and
> take into account the resulting weaknesses in your random outputs.
If you use a PRNG with no known weaknesses, and you seed it with a hash
with no known weaknesses, and you assume the lower bound for how much
entropy in your input data, the resulting system will have no known
weaknesses.
DS
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: AES only 128 bit-blocksize?
Date: Mon, 06 Nov 2000 20:01:58 GMT
In article <[EMAIL PROTECTED]>,
Makoto Miyamoto <[EMAIL PROTECTED]> wrote:
> Hi,
>
> I'm curios, if the AES is only defined with 128 bit-blocksize or if
> all blocksizes mentioned in the Rijndael-paper are considered as AES?
Rijndael in it's 128/192/256 bit key length and 128 bit block length is
the proposed AES standard.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker,talk.politics.misc
Subject: Re: XOR Software Utility (freeware) available from Ciphile Software
Date: Mon, 06 Nov 2000 20:04:01 GMT
In article <o7BN5.666$[EMAIL PROTECTED]>,
Andre van Straaten <[EMAIL PROTECTED]> wrote:
> In sci.crypt Tom St Denis <[EMAIL PROTECTED]> wrote:
> > In article <[EMAIL PROTECTED]>,
> > Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
> >> XOR Software Utility (freeware) available from Ciphile Software
> >>
> >> This software simply performs the universally available logical XOR
> >> process on two files chosen by the user and outputs the resulting
> >> file.
> >>
> >> http://www.ciphile.com
> >>
> >> goto the Downloads Currently Available web page.
> >> scroll to the bottom of the page.
> >>
> >> Click on the blue anchor tag: CiphileXOR_10.zip (155kb)
>
> > How on earth did you make such a simple program take 155kb?
>
> > Tom
>
> The GUI makes the overhead.
>
> The program itself is very short. The core is a while loop
> with three statements.
>
> A similar program with a repeated key instead is in the first
> chapters of Bruce Schneier's "Applied Cryptography".
>
> Just a few weeks ago, I wrote the same thing in C++ and Tcl/Tk.
> Only my GUI (in Tcl/Tk) looks nicer. I have three entry fields
> for the files, and only if you press "Browse" appear the same
> file selection boxes he uses.
>
> I didn't publish this stuff, as I thought that thousands before
> me have done something similar.
> But if someone really means he wants a copy of the source code,
> C++ or Tcl/Tk, I'll send him one or post it.
> I won't put everything I write in my spare time on my Web site.
> This way you could check out how lame I am. ;-)
>
> My interest was to find out how different implementations on
> different platforms cope with the new line character(s).
> The disadvantage of the OTP is that only one added or left
> character in the key file or ciphertext file messes up the rest
> of the plaintext file.
> (E.g.: encrypting on Unix and decrypting on MS Windows)
I could make a simple GUI for a xor file program take about 5kb of code
memory. I still don't know how he managed 155kb.
Must be a trap door.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: example code for your use
From: Richard Heathfield <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.c,comp.lang.c.moderated
Date: 06 Nov 2000 20:21:48 GMT
[this reply written in comp.lang.c - sci.crypt will have a different
perspective]
Kenneth Lantrip wrote:
>
> I have written a nice (I think so) little program in C to help me learn the use
> of the language. I'm not sure if it's legal to post an encryption algorithm
> that uses a 128 bit key. I'd like to offer it to whoever wants to see the code
> so that they might can use parts of it or learn from it or whatever.
>
> Below is a text mode screen shot of the program. It is a simple IDEA
> calculator that takes an input and a key and makes an output, or an output and
> key to find an input. The cursor is moved by the arrow keys and the space bar
> toggles the value of the bit or nibble it sits on. F11 saves and F12 loads a
> saved state. The program is of no real use, other than educational values, as
> the key space and avalanche properties of the IDEA algorithm is too great to be
> comprehended by the human mind. It is little more than a crypto-analysis tool
> for the algorithm.
>From comp.lang.c's point of view, the program appears to use features of
a particular compiler. The interface parts of it, at least, are not
topical here. You don't mention which platform it is for. This could be
rather important for people wishing to use it.
>
> If you would like to look over the source code, e-mail me and I'll send it to
> ya if ya live in the USA. I'm not sure export laws allow 128 bit crypto
> algorithms to be exported. However, I can point you in the right direction to
> where you can get the source for the IDEA algorithm that was used in the
> program below. I can still send you the main() function.
You are right to be cautious. I'm not sure whether you're being overly
cautious or not. I live outside the USA, and have full electronic source
code for DES, TwoFish, Blowfish, etc, quite legally. (I bought the
relevant books, and typed in the code!)
>
> I realize that these stupid crypto laws are a direct infringement of my first
> amendment constitutional right!
No. You can print out the source code and snailmail it. Legally! Just
don't send it on a floppy disk or CD-ROM. Those might well be illegal.
You gotta love USA logic...
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
--
comp.lang.c.moderated - moderation address: [EMAIL PROTECTED]
------------------------------
Subject: Re: example code for your use
From: Chris Hills <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.c,comp.lang.c.moderated
Date: 06 Nov 2000 20:22:08 GMT
Kenneth Lantrip <[EMAIL PROTECTED]> writes
>I have written a nice (I think so) little program in C to help me learn the use
>of the language. I'm not sure if it's legal to post an encryption algorithm
>that uses a 128 bit key.
Yes in the Free world but probably not in the USA.
> I'd like to offer it to whoever wants to see the code
>so that they might can use parts of it or learn from it or whatever.
There are several crypto News groups where you will probably get a
better response. Crypto is a very specialised field. Have a look at the
links from www.counterpane.com.
>If you would like to look over the source code, e-mail me and I'll send it to
>ya if ya live in the USA. I'm not sure export laws allow 128 bit crypto
>algorithms to be exported. However, I can point you in the right direction to
>where you can get the source for the IDEA algorithm that was used in the
>program below. I can still send you the main() function.
AFAIK IDEA is Swiss and therefore originated outside the USA
anyway?
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills Staffs England /\/\/\/\/\
/\/\/ [EMAIL PROTECTED] www.phaedsys.org \/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
--
comp.lang.c.moderated - moderation address: [EMAIL PROTECTED]
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Date: Mon, 06 Nov 2000 12:57:03 -0800
David Schwartz wrote:
> rest are all '1's. This stream is guessable in the sense that if you
> guess that a given bit is a '1', you'll be read 99.9% of the time.
What glitch in my brain allowed me to type "read" when I meant "right"?
A whole psychology paper could be written on it.
DS
------------------------------
** 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
******************************
