Cryptography-Digest Digest #42, Volume #9 Fri, 5 Feb 99 21:13:03 EST
Contents:
Re: Threat Models: When You Can't Use a One-Time Pad (Jim Dunnett)
New explanation (sorry for the last one) (Vektor)
Re: MAC generation (John Savard)
Re: Cipher used by iomega in ZIP products ? (Nogami)
Re: Metaphysics Of Randomness ("Tony T. Warnock")
Re: *** Where Does The Randomness Come From ?!? *** (Aaron Boyden)
Re: XOR encryption... (Binder Edgar)
Engima ("Ashley England")
Re: hardRandNumbGen (Patrick Juola)
Re: Metaphysics Of Randomness (Patrick Juola)
Re: Rational points on a curve (Sammy)
Re: Historical basis for BLOWFISH ("karl malbrain")
Re: cryptology in physics (Sammy)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Jim Dunnett)
Subject: Re: Threat Models: When You Can't Use a One-Time Pad
Date: Fri, 05 Feb 1999 22:02:09 GMT
Reply-To: Jim Dunnett
On Thu, 04 Feb 1999 21:28:47 GMT, [EMAIL PROTECTED]
(John Savard) wrote:
>This relates to a discussion that went on in another thread a while
>back:
>
>Suppose I'm sending an E-mail to a friend, and I don't want a hacker
>reading it.
>
>Then, it is quite true that, for the cost of a CD-R or a floppy, and a
>stamp, if I have a way of generating true random numbers available to
>me, the one-time-pad is a satisfactory way of obtaining security for
>that communication.
Sending it through the post is NOT a secure means of distributing
a key.
>It's theoretically perfect, and it's simple. Why bother with anything
>else, some people would ask.
Because, if you have more than one correspondent, you will have
key distribution problems, and problems of used-key-cancellation
if you had a common key in use between 3 or more communicants.
>I don't ask that question myself: I think conventional symmetric
>ciphers, with keys of reasonable length, can be as secure as anyone
>might need, and they are even more convenient. But I have to admit
>that this is a valid approach to this situation as well.
No doubt they are as secure but hardly more convenient. Key
distribution raises its ugly head again. Public-Key ciphers
neatly avoid this problem.
>Suppose I want to encrypt a file on my hard disk, and I don't want
>somebody who later obtains physical access to my computer to read it.
>
>_Now_, can I use the one-time pad?
Yes. If your OTP key is secure and not re-used. But this would
require some other crypto program to store your key. You might
as well use PGPDisc or ScramDisc for everything...much more
convenient.
--
Regards, Jim. | I would be happy to see the devil's
olympus%jimdee.prestel.co.uk | buttermilk banned from Society.
dynastic%cwcom.net |
nordland%aol.com | - Iain Paisley, discussing Guiness.
marula%zdnetmail.com |
Pgp key: wwwkeys.uk.pgp.net:11371
------------------------------
From: Vektor <"vektor_"@hotmail.com(orsoyouthink!)>
Subject: New explanation (sorry for the last one)
Date: Fri, 05 Feb 1999 17:42:43 -0500
Ok...i've explained this quite poorly before, so i will make an attempt
to explain it better this time (i've got some examples, and i go through
and explain elements again that i might have made fuzzy in the first
parts of this explaination). I'm not a C programmer, but i believe that
!= is not equal, if it isnt...i'm using it that way, so please bear with
me :)
first, a 'Random Key' is used to seed a PRNG, which outputs 256 numbers,
0-255 (in a psuedo-random order). (The method it does this is explained
later, in better detail :) )
the 'Encrypt Key' is used to gain offsets in the PRNG output, and a
2x256x256 encrypt array is created. every 256 chunk block contains the
PRNG output, in varying order, so that each block is different (IE.
0,1,1 != 1,1,1 and 0,255,255 != 1,255,255). the last element of the
array (the second 256), will yield the 'encrypted byte' that we're
working on, and its value (to replace the 256) will be the value of the
un-encrypted byte that we're encrypting. the second value (the first
256) is the previous bytes encrypted value, so that depending on what
the last byte encrypted to, the current byte will have a totally
different value. the first element in the array (the 2), is the first
bit of the byte that came before the byte we used in the second element.
depending on the value of the bit, the current byte that we're
encrypting will have a totally different value.
(i know thats a -TERRIBLY- confusing explaination, but i'll try to clear
it up now, using an example 3 byte stream we'll encrypt, and a 2 byte
IV, taken from the Encrypt key)
12 22 32 <--- this is our unencrypted stream, in byte values.
45 254 <---- this is our IV, taken from the 2nd key
the stream would encrypt like this :
u1 = 45 AND 1 (yielding the lowest bit, 0 or 1)
u2 = 254
u3 = 12 (our first byte to be encrypted)
e1 = EncryptArray(u1,u2,u3)
u1 = u2 AND 1 (a new bit)
u2 = e1 (this is our new second byte, taken from the last bytes
encrypted value)
u3 = 22 (this is our new byte to be encrypted)
e2 = encryptionarray(u1,u2,u3)
... and so on, until the entire string has been encrypted.
once it is, the encrypted message is XORd with the key used to generate
the PRNS, to disguise any 'patterns' that might present themselves.
(i hope that cleared up my utterly pathetic explanation :) )
the decrypt array is generated from the encrypt array.
since the PRNG only spawns out 256 bytes, and all those bytes are
basically a random order 0-255, i suppose it would be completely
possible to re-create the exact output of it. BUT...without the offsets
into the array that are used to generate the encrypt table, I dont
believe that the PRNS would do you much good (I hope).
the PRNG is basically just a fibonacci sequence with the starting
numbers taken from the 'Random Key', with a MOD to create varying
numbers. There are initially 400 of these numbers, but only the first
unique 256 are taken (this is a trait from the first-run of the PRNG,
when it would sometimes generate identical numbers. It was re-written
and doesn't generate them anymore, but i kept this part in, 'just in
case', since any duplicates would create an un-decryptable message).
these 256 numbers are sorted, then compared to thier original location,
yielding the numbers 0-255, in randomized order.
After these 256 bytes are created, the PRNG is not used again. all
random numbers are taken from the 256 byte output (which is stored in an
array called RandArray.)
A new function called MRandomize sets the offset to start in RandArray,
based on the seed given. MRnd returns the next number in RandArray,
starting from whatever the offset was initialized to in MRandomize.
The encrypt table is filled, 256 bytes at a time. from 0x0x0 to 0x0x255,
the same offset is used. at 0x1x0 (and every other block, IE 0x2x0,
0x3x0, and so on), MRandomize is called, changing the offset in
RandArray, yielding a different 256 byte block. at 1x0x0, MRandomize is
called again, with a different starting offset, thus making 0x-x-
different from 1x-x-.
If you can recreate the PRNG output (which wouldnt be hard, if you knew
what you were doing), you still could not generate the Encrypt Table,
without knowing what offsets were used.
Since each byte that gets encrypted depends on the encrypted value of
the byte that came before it, the message itself becomes a factor in its
encryption. This would lead me to believe (maybe in my own little
universe :) ) that you couldnt just 'analyze' it, and discover any
patterns, because any patterns that developed would be meaningless.
I'm thinking (and it works out, in my head) that without both keys, you
cant get anything meaningful from any message encrypted with this
method. I'm aware that theres several elements, from several other
schemes in here. RC4 having been already sited (*grin*).
If you can point out any fundamental flaws in this scheme, please do :).
To my understanding, this scheme would be fairly secure, being you could
concievable have 3 "x"'s in a row in the encrypted stream, which
wouldn't exatly mean there were any repeats at all in the message
(BUT..it could ;) ). If you had both keys, you could easily recreate the
encrypt table, and thus decrypt the message. any deviation in either
key, however, would yield useless garbage.
MY APOLOGIES to those who read my previous post on this, and didnt get
at what i was saying...my explanation of it left quite a bit to be
desired, which was entirely my fault :). hopefully this explaination of
it was better (It almost had to be...reading my own explaination, i
almost didnt understand it ;)), and actually contains some useful
information.
thanks for your patience...it speaks volumes of you, and i'm impressed
(under the same circumstances, i would have just given up) :).
as before...feel free to contact me in whatever way you feel
comforatable with.
EMAIL - [EMAIL PROTECTED]
ICQ - 16841690
or just reply here. i check regularly.
-Alex
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: MAC generation
Date: Fri, 05 Feb 1999 21:49:45 GMT
"Vadim Lebedev" <[EMAIL PROTECTED]> wrote, in part:
>Hello i need an opinion on validity and possible weakness of following
>approach to generate MAC for messages 20 to 200 bytes longs.
>Assuming that S is the contents of the message the MAC will be
> MD5(S+SecretPassPhrase)
Probably MD5(SecretPassPhrase+S) is 'better', if your goal is to have
a secret MAC to authenticate strongly. This way, your secret pass
phrase, instead of just encrypting the MAC at the end, encrypts the
initial value at the start, thus affecting everything that happens
later.
Actually, while both approaches are secure, though, for a keyed MAC,
I'd like something even better. I'd like it to affect the process from
beginning to end, in a nonlinear fashion!
I think I may have to settle for MD5(SecretPassPhrase +
SVigeneredBySecretPassPhrase ) or something like that for now. But
you've started me thinking about how to design an algorithm
specifically designed for keyed MAC use. (Panama already has that kind
of capability too...)
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (Nogami)
Subject: Re: Cipher used by iomega in ZIP products ?
Date: Fri, 05 Feb 1999 22:52:45 GMT
On Thu, 04 Feb 1999 21:02:47 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>Michael Curry wrote:
>
>> On Thu, 04 Feb 1999 15:43:37 -0500, "Trevor Jackson, III"
>> <[EMAIL PROTECTED]> wrote:
>>
>> >Paul Gover wrote:
>> >
>> >> I thought it was ROT-13, with two rounds for extra security :-)
>> >
>> >Hmmmm, triple-ROT13. What a concept! Thinks that's enough?
>>
>> Given the fact that it's possible to bypass the Zip disk encryption
>> via simple physical means (all you need is another disk with a
>> password you know and a paper clip) the actual method used becomes
>> rather a moot point.
>>
>> Or have those wise men at Iomega finally dealt with that problem?
>
>Since Rot-13 is its own inverse, any even multiple leaves the ciphertext
>== the plain text. Any odd multiple is identical to a single operation.
Uh, ya... It was a joke ;) [whoosh!]
N.
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Fri, 05 Feb 1999 15:35:58 -0700
Reply-To: [EMAIL PROTECTED]
R. Knauer wrote:
> On Fri, 05 Feb 1999 14:00:05 -0700, "Tony T. Warnock"
> <[EMAIL PROTECTED]> wrote:
>
> >> Champernowne's number is not normal in base 2, only in base 10.
>
> >The Champernowne construction works in all bases. In fact all my postings
> >have been in base 2.
>
> >11011100101110111...
>
> From Greg Chaitin's paper entitled: "Randomness in Arithmetic and the
> Decline & Fall of Reductionism in Pure Mathematics" at:
>
> http://www.umcs.maine.edu/~chaitin/unm.html
>
> and also reprinted in his 1998 book "The Limits Of Mathematics"
>
> http://www.umcs.maine.edu/~chaitin/lm.html
>
> "This is called Champernowne's number and Champernowne showed that
> it's normal in base ten, only in base ten. Nobody knows if it's normal
> in other bases, I think it's still open."
>
> Maybe you need to tell Greg Chaitin something he doesn't know.
>
> Bob Knauer
>
> "Sometimes it is said that man cannot be trusted with the government
> of himself. Can he, then, be trusted with the government of others?"
> --Thomas Jefferson
No, I'm telling you something you don't know.
------------------------------
From: Aaron Boyden <[EMAIL PROTECTED]>
Crossposted-To: sci.skeptic,sci.philosophy.meta
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: Fri, 05 Feb 1999 18:27:03 -0500
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] wrote:
> If you are handed a message without having *any* idea of the underlying
> language or cryptograhic system, the number of possible kinds of hidden order
> are as near to infinite as makes no odds.
They're not near infinite, they're infinite, even if you put limits on the variety
and number of symbols, since the message could be a code for absolutely anything.
Simple proof: say the code represents an integer. There's no integer it couldn't
be a code for, and there are countably infinitely many integers, so there are at
least countably infinitely many possible meanings for the code. Reals are a
trickier case, but it's possible that the same applies for them, in which case the
number of possible meanings is uncountably infinite.
--
Aaron Boyden
"I may have done this and that for sufferers; but always I seemed to
have done better when I learned to feel better joys."
-Thus spoke Zarathustra
------------------------------
From: [EMAIL PROTECTED] (Binder Edgar)
Subject: Re: XOR encryption...
Date: Fri, 05 Feb 1999 21:27:21 +0100
Jim Gillogly wrote:
> As I understand the BWT, it doesn't have compression built in, but
> is a front-end sorting algorithm that produces text to which
> some other [set of?] compressor[s?] is applied, and that it works
> on individual blocks of input text. I suspect the answer will lie
> in the details of what compressors you're applying to the output
> and the block size you choose for the BWT. If the latter is too
> small you'll run into known plaintext attacks, where (e.g.) the
> attacker guesses that your plaintext starts with the same three
> library functions that the previous version of the product used.
Ussualy the blocks are at liest 1 Mb....
> Are you planning to simply use the output of bzip2 as the first
> stage? If so, you'd better know all about its block assumptions
> and what it's using to compress the BWT output.
Nope. I'm writing a compressor based on BWT, and I'm trying to find a fast
encrypting algorithm.
> In any case, since you say "password", it could be subject to a
> dictionary attack. For any data that's worth anything, the
> cryptanalyst will have a way to test whether the resulting
> plaintext is meaningful, so trying lots of possible passwords
> and decompressing the result should result in something testable.
> For some compression algorithms, trying to decompress garbage
> will result in errors or overflows -- e.g. the next character is
> marked as 47121 bits long, when the maximum for this implementation
> is 14 bits per character; or for a system with a maximum of 16 bits
> per character you get a long run of 15- and 16-bit characters. This
> can help eliminate faulty keys rapidly without having to test the
> plaintext.
The only thing that compresses efficiently the BWT output is a fast
adaptive entropy coder. AFAIK, adaptive entropy coders don't leave anything to
test.
> ARJ used your proposed strategy for encryption, and I found it pretty
> challenging to do a single file in an archive, since the compression
> was quite good and there wasn't much statistical leverage for an
> analytical attack. I think Paul Kocher solved one or more of these
> individual ARJ files. Still, something messier than a straight XOR
> with your password will give you better security.
What exactly do you mean by something messier than XOR ?
> In general, a no-hints compression procedure is a good first step
> before encryption, if only to minimize transmission bandwidth...
> but you may as well use a good encryption system at that point.
> RC4 won't take much longer to run than your XOR, and since you're
What is RC4 ?
> taking the time to compress it, you're not all that worried about
> nibbling every microsecond off the processing time.
Well, actually I am pretty worried about the encryptor, because the
archiver will compress 2-3 Mb/Sec on a P200.
Sorry about my bad english...
Edgar
------------------------------
From: "Ashley England" <[EMAIL PROTECTED]>
Subject: Engima
Date: Fri, 5 Feb 1999 20:23:14 -0000
Does anyone know where i can get plans of the enigma?
Ash
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: hardRandNumbGen
Date: 5 Feb 1999 08:50:10 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 4 Feb 1999 14:36:11 -0500, [EMAIL PROTECTED] (Herman Rubin)
>wrote:
>
>>If one can assume independence between generated sets, one can make
>>both of these errors quite small, if the point null is not assumed.
>>That is, the user must specify the inaccuracy allowed, which cannot
>>be zero.
>
>Please elaborate on how this is done.
Well, one starts out by making a questionable assumption, in most cases --
sorry, Dr. Rubin 8-) -- especially when one is testing successive
"pads" from a generator.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Metaphysics Of Randomness
Date: 5 Feb 1999 09:11:19 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 3 Feb 1999 09:23:12 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>>I'm going to remind you just one more time
>>>that dividing random strings into True Random Numbers and Pseudo Random
>>>Numbers creates a distinction without a difference since no test exists to
>>>distinguish them.
>
>>It's not a distinction without a difference. You're just doing the
>>wrong test. There's a test to distinguish Chryslers from Fords.
>>But it's not a test you're going to perform by measuring the gas mileage.
>
>If the crypto-grade randomness of a given set of numbers is based on
>the generation process and not the numbers themselves, then how do you
>propose to test those numbers themselves to show that the generation
>process is crypto-grade secure?
That's exactly the point. Testing "the numbers themselves" in
absentia is not particularly useful. Testing the numbers in
conjunction with an analysis of the generator is more useful.
And in some cases, an analysis of the generator will reveal
that testing the numbers is not necessary because the generator
is provably unable to do the job.
>I realize that you can test them and obtain a certain level of
>confidence regarding the generation process, but that assumes that you
>have tested a very large number of such sets. There is always the
>possibility that a set of numbers from a poor-security PRNG passed the
>tests and another set from a crypto-secure TRNG failed the tests even
>if the level of confidence is high.
There is. If the tests done are extensive, this probability
can be made -- literally -- as small as you like, as long as
it's still non-zero.
>Perfectly secure generators can produce numbers which do not pass bias
>tests,
But, in general, they don't -- this probability can be reduced
as far as you like.
> and perfectly unsecure generators can produce numbers which do
>pass bias tests. Sure, in the limit of very large numbers these tests
>converge on an absolute measure of randomness in terms of bias. But
>how do you perform such a large amount of testing in a practical
>situation?
Start by talking to a GOOD statistician, and produce a testing
budget....
>All we hear in this regard is that there are these wonderful
>statistical tests out there that anyone can use easily that perform
>all this wonderful mathematical magic, but when challenged to produce
>these magical tests and defend them as being so wonderful, we never
>see any presented.
Well, a simple example, then. Perhaps oversimplified -- but what
do you expect for free in a seventy-line posting.
Define a level of "unacceptable" bias -- perhaps your initial
worry is that bigrams are not uniformly distributed. The standard
test for even distribution would be the Chi-squared (although a
real statistician will mention several other, better, tests).
Run your generator enough to get several hundred bigrams, count
them, and confirm (or disconfirm) that your result is compatible
with the null hypothesis of equiprobability. In other words, you
have a "failure to reject" at some level, depending on what your
level of unacceptable bias is.
Implicit in this is are (mathematically) two probabilities, that
the statistician you hired can probabily give you the formulae
for.
1 -- the probability that a good generator would fail this
2 -- the probability that a biased generator with bias right as
the threshhold would pass.
Call these probabilities x and y, respectively. If you can live
with those numbers, you're done. If you use a fairly large sample,
they're easily going to be in the close order of 5%. A *really*
large sample will give you reliablity into the area of 0.1%
If not, run the test again -- this is where Dr. Rubin's suggestion
of assuming independence comes in, which I quibbled with earlier 8-) --
The probability of a good generator failing *both* tests is x*x, which
is less than x. (5% ^2 == .0025, 1/4 of 1%)
The probability of a bad generator passing *both* tests is y*y, which
is less than y. So if your two tests agree, you are more confident
that your result is correct.
If they don't agree, run more tests, and consult with your stastistician.
-kitten
------------------------------
From: Sammy <[EMAIL PROTECTED]>
Subject: Re: Rational points on a curve
Date: Fri, 05 Feb 1999 17:26:38 -1000
Jayant Shukla wrote:
>
> Hi,
> Is there an easy way to find integer points on
> the curve y^2 = a x^2 + b x + c? i.e. both x and y
> are integers. The constants a, b, and c are integers
> as well.
>
> regards,
> Jayant
Yes. (x,y) = (1,1) is easy. So are (2,2) (3,3), etc.
when b=c=0 and a=1. There are many easy solutions to
the equation you gave.
But maybe you were interested in cryptographic uses of
elliptic curves over a finite field like:
y^2 = a x^3 + b x + c mod p EQUATION 1
In this case, there is an easy way and there is a hard way.
Let us look at the hard way first. Suppose p is a prime number
more than 2^169 but less than 2^171. The hard way is to pick
x and calculate the right side, then take a square root
mod p.
Here is an easy way: first choose
p so it is congruent to 3 mod 4
or
p==3 mod 4
now pick an x and calculate the right side of EQUATION 1
before you take the square root, determine if it is a
quadratic residue by calculating the Legendre Symbol.
If it is not a quadratic reside, try another x. When you find
an answer that is a quadratic residue, you are ready to find
the square root using an easy shortcut.
sqrt(y^2) == (y^2)^((p+1)/4) mod p
page 49, "A Course in Number Theory and Cryptography"
by Neal Koblitz
Published by Springer
Graduate Texts in Mathematics # 114
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: Historical basis for BLOWFISH
Date: Tue, 2 Feb 1999 15:33:26 -0800
From: Bruce Schneier <[EMAIL PROTECTED]>
>For the record, I decided to include it because it was presented at a
>Crypto conference. I also references Biham and Shamir's differential
>attack. Biham and Shamir never looked at REDOC III; I chose to
>publish it because I was asked to (back then, block ciphers were
>scarce). Again, this has nothing to do with Blowfish.
>>...
>>Does you answer mean that we are all doomed to some form of advanced
LINEAR
>>analysis???
>
>No.
Thanks for the insight. However, I believe that one DEVELOPS new things on
the basis of one's understanding of the usage of
existing things....
I'm not a mathematician -- I'm a programmer. I don't claim to understand
how S-BOXES are, or are not, subject to LINEAR analysis.
Based on your book, in 1993 I did an experimental implementation of REDOC-3
to encrypt compressed text documents, holding an
incomplete analysis (of the LINEAR problem) that if one's adversary had a
Plaintext and Cyphertext pair, there was no further hope
of security under that key schedule in any event.
Now, I need to decide on a method to establish secure communications. The
direction I need is precisely to what leads you to say
NO, we are not doomed to LINEAR analysis under S-BOXES.
Karl M
------------------------------
From: Sammy <[EMAIL PROTECTED]>
Subject: Re: cryptology in physics
Date: Fri, 05 Feb 1999 17:49:00 -1000
David Leuenberger wrote:
>
> Hi!
>
> Cryptology is a discipline taking place in an abstract number place
> (it's a mathematical discipline)
> I wonder if there are analogous mechanism to the Alice-Bob-Eve-pattern,
> to one-way-functions and to zero-knowledge-protocols in general physics,
>
> biological systems (DNA?), ...
>
> Thanks for any reply
Protein folding. This is a one-way function because it is easy to do
yourself, but it is hard for scientists to calculate a simulation of
protein folding. Your cells can fold one in a millisecond, but computers
take months to get a close approximation.
------------------------------
** 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
******************************
