Cryptography-Digest Digest #218, Volume #14 Mon, 23 Apr 01 17:13:00 EDT
Contents:
Re: C code for GF mults ("Brian Gladman")
Re: "UNCOBER" = Universal Code Breaker ("Joseph Ashwood")
Re: simple schema for encoding/decoding a 128 bits block ("Joseph Ashwood")
Re: padding for RSA/EG ("Joseph Ashwood")
Re: 1024bit RSA keys. how safe are they? ("Joseph Ashwood")
Re: OTP WAS BROKEN!!! (Scott Craver)
Re: SHA prng ("Joseph Ashwood")
Re: "UNCOBER" = Universal Code Breaker (John Myre)
Re: Delta patching of encrypted data ("Anon")
Re: OTP WAS BROKEN!!! (Joe H Acker)
Re: 1024bit RSA keys. how safe are they? ("Tom St Denis")
Re: OTP WAS BROKEN!!! (Joe H Acker)
ok newbie here ya go ("Tom St Denis")
Re: SHA prng (Ross Younger)
Re: "UNCOBER" = Universal Code Breaker (Joe H Acker)
----------------------------------------------------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: C code for GF mults
Date: Mon, 23 Apr 2001 21:20:43 +0100
"David Eppstein" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <3YQE6.31605$I5.161433@stones>,
> "Brian Gladman" <[EMAIL PROTECTED]> wrote:
>
> > I suspect that Conway's method of multiplication is equivalent to the
use of
> > this method for field extension but I have not yet looked at this again
> > since I saw your formulation.
>
> Conway proves that his version is equivalent to repeatedly extending by
> polynomials of the form T^2+T+c, where c is the last power of two in the
> integer ordering of the previous stage.
This looks like the same process but with a different set of generators.
I had got as far as working out that Conway's method used the quadratic you
describe. What I have not been able to do yet is to show that, with c as
you indicate, this quadratic is always irreducible in the base field.
> I'm not sure how this relates to Jyrki's choice of extending by the
> polynomial T^2+x_{i-1}T+1=0.
I assume that is just a different set of field doubling operations - both
methods generate GF(2^(2^k)) from GF(2^(2^(k-1))) but, I assume, with the
elements in a different order.
It raises the question of how many polynomials of the form T^2 + aT + b
remain irreducible with respect to field doubling and where the successive
a's and b's simply related (or fixed) in some way (a and b are field
elements in each base field before doubling).
Brian Gladman
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Mon, 23 Apr 2001 12:45:26 -0700
I agree that the stand you take is far from provable, I am however rather
biased, as I believe the statement to be false.
The simple fact is that if you discard without examination no harm will be
done to the sequence, but if you discard based on examination you can and
most likely will do harm to the sequence. There are a very few known methods
of altering a stream like this based on examination that do not create
problems.
Joe
"Joe H Acker" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Joe H Acker <[EMAIL PROTECTED]> wrote:
>
> > Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> >
> > > "Joe H Acker" <[EMAIL PROTECTED]> wrote in message
> > > news:[EMAIL PROTECTED]...
> > > > If the random source is truly random, it doesn't do any harm when
some
> > > > of its output is discarded, except for performance slowdown. So yes,
> > > > tests are useful to (a) continually test wether the hardware has
failed
> > > > or does appear to work correctly, and (b) to prevent against very
very
> > > > bad luck when a true random source happens to output the complete
volume
> > > > of Shakespeare's Macbeth (very unlikely)
> > >
> > >
> > > Actually it can do a great deal of harm. A short, rather extreme
> > > demonstration:
> > > take a perfect random number generator that generates binary
> > > throw away all the output bits that are 1
> > > Is the sequence predictable?
> >
> > You may not filter the sequence heuristically. I was talking about
> > testing large sequences and when they fail the test, discarding them
> > *completely*. Discarding an output sequence of a tRNG completely can
> > never do any harm, except a performance slowdown, given that the
> > discarded sequence is large enough and not just 1 bit in length. That's
> > provable.
>
> Sorry about the duplicate answers. After some thinking, I do no longer
> believe that my claim is provable. It was a quickshot I'd like to
> apologize for. Still, I believe that filtering out large sequences that
> look very non-random has more benefits than it can harm, given that it's
> a tRNG and not a pRNG. E.g. it doesn't appear to be a security problem
> if you have 2^128-2 or 2^128 possible outputs of a 128-bit sequence. But
> an all 1 or all 0 sequence can be a security problem, because it may
> indicate that the tRNG is broken.
>
> Regards,
>
> Erich
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: simple schema for encoding/decoding a 128 bits block
Date: Mon, 23 Apr 2001 13:01:01 -0700
Well I'm assuming you've got a few cycles to burn on the computer to do
this.
pt1 = 96-bit block
pt2 = first 32-bits of SHA-1(pt1 | shared secret)
pt = pt1|pt2
choose one
ct = Rijndael_encrypt(pt)
ct = RC6_encrypt(pt)
ct = Twofish_encrypt(pt)
ct = MARS_encrypt(pt)
ct = Serpent_encrypt(pt)
Any of those should be more than suitable, and you can use a 128, 192, or
256-bit shared secret key for any of them. Since you only have one block
don't bother with a chaining mode, just use ECB.
Joe
"user1002" <[EMAIL PROTECTED]> wrote in message
news:%hHE6.78411$[EMAIL PROTECTED]...
> I would ask suggestions for creating a simple piece of c code for encoding
/
> decoding a 128 bits block, I have a single 96 bits (3 x 32 bits words)
> block to encode and send through the net, I know there are many different
> ways to encode a 96 bits block but what I need is to include some
additional
> data / information so that when I decode the block I obtain some sort of
> certificate of authenticity for ALL (or almost all) the bits of the block
> (i.e. to know that the block has been generated by the right sender and
not
> by a evil-doer), I hope that an additional word (32 bits) could permit to
> authenticate the block, is this opinion tenable ? Could someone suggest a
> (possibly) simple algorithm for encoding / decoding the block ? Of course
> the block could include more than 128 bits if necessary.
>
> Thanks,
>
> Paolo
>
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: padding for RSA/EG
Date: Mon, 23 Apr 2001 12:56:56 -0700
The basic method for encryption is OAEP which look ssomething like:
given a k-bit hash function
given an n-bit modulus
given data that is padded to length k
choose a random R of size n-k-1
h = hash(R)
plaintext = R | (h XOR data)
encrypt that value
You can also use it to sign with RSA, but PSS (below) is at least as good.
For RSA signing use PSS:
given a k-bit hash function
given an n-bit modulus
choose a random R of size n-k-1
sigText = R | hash(R | data)
the data can be either a hash or the original data depending on what is
supplied
Decryption/verification should be fairly obvious. If it isn't then 1363 has
the text on either and just a few days ago I posted the reference to PSS.
Joe
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:ylGE6.30105$[EMAIL PROTECTED]...
> I was wondering what the generally accepted methods for padding in RSA and
> ElGamal. I have seen PKCS #1 but I have also heard that it has
problems...
>
> I am in the midst of writting another crypto lib (somewhat
> portable..hopefully, the goal is small... it has ELGamal, RC4, a base64
> encoder/decoder, a portable RNG (uses RC4 to output the rng bytes after it
> has been seeded, and you can restart it), and some other goodies) and I
want
> to get the PK stuff right.
>
> Last I remember (afaik) you pad with binary ones when signing right (in
> RSA)? What about encrypting and the ElGamal operations?
>
> Thanks,
> --
> Tom St Denis
> ---
> http://tomstdenis.home.dhs.org
>
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: 1024bit RSA keys. how safe are they?
Date: Mon, 23 Apr 2001 13:10:56 -0700
I trust 1024-bit RSA enough that I would post my personal credit card number
to a hacker newsgroup protected by such a key (provided I knew certain
additional constraints). And the credit card I have in mind has a credit
limit that could buy someone a house. However I would make sure that the
card expired in the next 5 years. Move it up to 2048-bit and I might
actually trust it with my social security number.
So to answer your question, yes, a 1024-bit RSA key is sufficient to
maintain the privacy of a credit card number, as long as the private key is
not compromised, and the generation process was done properly. I would
suggest that in order to make your system a bit more robust you use the
largest RSA key you can, if you can afford the time for a 4096-bit key, use
a 4096-bit key, if you can afford a 128Kbit key, use it, etc.
Joe
"George T." <[EMAIL PROTECTED]> wrote in message
news:9c0956$ph0$[EMAIL PROTECTED]...
> HI
>
> Does anyone has idea how safe RSA 1024 bit keys are? Are they safe enough
to
> be used for encrypting credit card information, travelling over the
internet
> and or residing on servers (email) for more than 24 hours.
>
> If no, what encrypting method would be sufficient?
>
> Any help is greately appreciated.
>
> George
>
>
------------------------------
From: [EMAIL PROTECTED] (Scott Craver)
Subject: Re: OTP WAS BROKEN!!!
Date: 23 Apr 2001 20:18:31 GMT
nugatory <[EMAIL PROTECTED]> wrote:
>
>So here's a challenge: What is the shortest possible
>argument that will convince an intelligent layman
>that an OTP cannot broken (as long as the "one-time" part
>is honored)? It should be *much* shorter than a
>derivation of E=mc^2.
Do you want a short layperson argument in English,
or a short argument in SEKRIT MATH LANGUAGE? In the
latter case, after all, the math does not get any
deeper than basic probability.
Your average proof that OTPs have perfect secrecy
is a half-dozen lines, for instance:
Argument:
Suppose c_j = encrypt(m_i, k_m).
1) Prob( M=m_i|C=c_j ) = Prob( M=m_i && C=c_j )/Prob( C=c_j )
2) ... = |C| * Prob( M=m_i && C=c_j )
3) ... = |C| * Prob( M=m_i && K=k_m )
4) ... = |K| * Prob( M=m_i && K=k_m )
5) ... = |K| * Prob( M=m_i ) * Prob( K=k_m )
6) ... = Prob( M=m_i )
Reasons:
1] Definition of conditional probability
2] All ciphertexts are equally probable, w/ probability 1/|C|
3] The value of K is entirely determined by choice of M and C.
4] There are as many keys as ciphertexts.
5] M and K are independent.
6] The keys are also chosen equiprobably, with probability 1/|K|.
Hence, knowledge of the transmitted ciphertext does not
increase/reduce the probability that any particular message
was sent. It provides no extra knowledge, and hence perfect
secrecy.
The proof that you need at least as many key bits as plaintext
bits is also easy to prove, if "bits" refers to the Shannon entropy.
-S
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: SHA prng
Date: Mon, 23 Apr 2001 13:25:12 -0700
Just using a pRNG won't get you anywhere, you'll only be compressing the
entropy of that pRNG into 160-bits, which will give you no more entropy than
was seeded into the pRNG. If you can afford to use someone else's code you
might look into openssl's RAND_* functions.
Just in case some sources of entropy.
Time the amount of time it takes to write a 128MB chunk of data to memory,
perform repeatedly.
Spawn 1024 threads, have these threads perform constant work, determine the
order they come in (just check which of them was the last to run)
have the user pound on the keyboard
open several connections to www.yahoo.com compute the rate of data transfer
None of these is fast for generating entropy but each will give you a little
bit. If you feed these data into SHA-1 to condense them it will provide a
reasonable amount of entropy over time.
Joe
"Dobs" <[EMAIL PROTECTED]> wrote in message news:9c1hko$9c8$[EMAIL PROTECTED]...
> I know that to generate secure random number first I need to collect R
bits
> of entropy and then use HASH(R) which will give me 160-bit string called
> message digest which is said to be random number.
> However I have a problem collecting entropy because it is really very
> difficult to make it use in my program.
> Can I just generate random number R by function
> srand( (unsigned)time( NULL ) ) instead of collecting entropy and than
HASH
> (R).Would it be random number and would it be secure PRNG which could be
> used in cryptography aims?????
>
>
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Mon, 23 Apr 2001 14:27:22 -0600
> THE TESTS BASED ON STATISTICS _*CANNOT*_
> ESTABLISH ANYTHING ABOUT THE GENERATOR.
This isn't really true. While a truly random source can
indeed (must, in fact) produce sequences that are anything
but random-looking (long strings of zeroes, Shakespeare
plays, and so on), the presence of such output from any
real device is much more likely to indicate that the device
is malfunctioning than that it "happened" to create that
output randomly.
Thus the practical rule is not to remove suspicious output,
but to disable the device altogether if such output appears,
pending some sort of fix or (re)validation.
JM
(I agree, however, with the theoretical point that removing
"non-random" output removes any guarantees we have that
are based on randomness. That is, if we *assume* that the
generator is performing to spec, then removing any output
based on its value, according to some rule, is detrimental.)
------------------------------
From: "Anon" <[EMAIL PROTECTED]>
Subject: Re: Delta patching of encrypted data
Date: Mon, 23 Apr 2001 21:36:19 -0000
Wow, I thought this thread had died!
I settled on a plaintext feedback mode. As you say, this does expose me
cryptographically, because anyone able to guess that a long repeating
section of ciphertext corresponds to a long repeating section of plaintext
(not hard) and that the repeating plaintext is zeroes (quite often) then has
a single example of a (not chosen) plaintext and ciphertext to work from.
However that's not (as I understand it) a major exposure on good algorithms.
To reword what I am trying to do:
I have a file as input. I wish to encrypt it.
At some later time I am given a new version of the file. I have my
algorithm and key, but I no longer have access to the original plaintext.
My aim is to choose an algorithm such that the delta patcher produces a
patch as small as possible without seriously compromising security. I
understand that the patch will not be as small as a patch to plaintext, if
nothing else because inserts will not compress!
Encryption speed and speed of producing the patch are not important. Fast
decryption is preferred.
Thanks to you all!
------------------------------
From: [EMAIL PROTECTED] (Joe H Acker)
Subject: Re: OTP WAS BROKEN!!!
Date: Mon, 23 Apr 2001 22:36:11 +0200
newbie <[EMAIL PROTECTED]> wrote:
> k belong to domain of all possible messages Xored with C.
>
> I compute this : Possible message Xor Cipher of the sender = possible k.
> I an list all the keys.
> But I still do not know which key was used.
> If you have the possible keys you can consequently test the key.
> It is very simple.
> You are sure that the key used to encipher belong to this domain.
> Consequently you can encipher another with your test-key.
> If your test-key = key used to encipher, it is like if the sender re-use
> the key.
> But the sender DID NEVER RE-USE HIS KEY.
Okay, what you call k now, I have called k' in my previous post you've
just replied to.
Please relax, take some time and go back to my previous post. Your
attack would be sensible if you had a way to approximate k' to k. That's
what I was asking for. You seem to believe that using the ciphertext in
some operation (like XORing it with some probable plaintext of PM(i),
and perhaps exploiting the ordering of PM(i) in some additional way) can
give you some information on how to approximate k' to k. If you don't do
this, you cannot determine which k'(i) is the correct key k, thus cannot
decide which of the probable messages PM(i) is the plaintext message.
It's exactly this step in your posts that remains unclear to me and
probably others. Consider this: Suppose that you have guessed the right
key k (i.e. k' = k). There's no way for you to *know* that you've
guessed the right key because you don't know k and the message is just
one message of PM(i), but you don't know that it's the right one.
Regards,
Erich
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: 1024bit RSA keys. how safe are they?
Date: Mon, 23 Apr 2001 20:42:17 GMT
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote in message
news:ek9C7IDzAHA.355@cpmsnbbsa07...
> I trust 1024-bit RSA enough that I would post my personal credit card
number
> to a hacker newsgroup protected by such a key (provided I knew certain
> additional constraints). And the credit card I have in mind has a credit
> limit that could buy someone a house. However I would make sure that the
> card expired in the next 5 years. Move it up to 2048-bit and I might
> actually trust it with my social security number.
>
> So to answer your question, yes, a 1024-bit RSA key is sufficient to
> maintain the privacy of a credit card number, as long as the private key
is
> not compromised, and the generation process was done properly. I would
> suggest that in order to make your system a bit more robust you use the
> largest RSA key you can, if you can afford the time for a 4096-bit key,
use
> a 4096-bit key, if you can afford a 128Kbit key, use it, etc.
> Joe
You fall for the numbers game. You say "I trust 1024-bit RSA enough that I
would post my personal credit card number ... provided I knew ...". You
should really say "I trust 1024-bit RSA when implemented correctly".
Just using big numbers doesn't make it secure!
Tom
>
> "George T." <[EMAIL PROTECTED]> wrote in message
> news:9c0956$ph0$[EMAIL PROTECTED]...
> > HI
> >
> > Does anyone has idea how safe RSA 1024 bit keys are? Are they safe
enough
> to
> > be used for encrypting credit card information, travelling over the
> internet
> > and or residing on servers (email) for more than 24 hours.
> >
> > If no, what encrypting method would be sufficient?
> >
> > Any help is greately appreciated.
> >
> > George
> >
> >
>
>
------------------------------
From: [EMAIL PROTECTED] (Joe H Acker)
Subject: Re: OTP WAS BROKEN!!!
Date: Mon, 23 Apr 2001 22:47:46 +0200
newbie <[EMAIL PROTECTED]> wrote:
> First of all, do you agree with my statement before continuing?
> Just this statement.
I can't speak for others, but I do agree. (You'd better call it
ciphertext instead of cipher, though.)
Now if you have all possible k'1..k'4. How would you find the right one?
That's what you haven't explained yet. C'est le probl�me!
Greetings,
Erich
> > Suppose a child that use only 4 words.
> > He use OTP to send a message. Ok
> >
> > I have the ciphertext 01001001010101
> >
> > I compute Word(1) Xor Cipher = k'1. I'm going to obtain a possible key
> > Word (2) Xor cipher= k'2
> > Word (3) Xor cipher = k'3
> > Word (4) Xor cipher = k'4
> >
> > It is sure that the key I'm looking is one of k'(i) i=1 to 4.
> >
> > Is that statement true???????
> >
>
>
> >
> >
> > Tom St Denis wrote:
> > >
> > > "newbie" <[EMAIL PROTECTED]> wrote in message
> > > news:[EMAIL PROTECTED]...
> > > > I'm going to be more clear.
> > > > If the sender re-use his key to encrypt any message, I will certainly
> > > > recover the 2 plaintext.
> > >
> > > If the sender "re-use his key to encrypt any message" then he's not
>>>using an
> > > OTP. Si le person utiliser leur clef deux fois ou plus ce n'est pas
>>> un OTP
> > > donc votre poste n'est pas applicable aux sujet de la poste. Is that
>>> clear?
> > > (my french is rusty...)
> > >
> > > > HE DID NOT. He use only once his PAD.
> > > > What I'm trying to exploit is nothing more than REUSING HIS OWN PAD.
> > >
> > > Then don't claim it as a break for an OTP. It's a break of a Vinegere
> > > cipher nothing more.
> > >
> > > Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: ok newbie here ya go
Date: Mon, 23 Apr 2001 20:51:31 GMT
Here's a lengthly (somewhat) ASCII message encrypted with a OTP (plain xor).
Decrypt it using your method!
35 53 5d 0a d3 2f b2 8c ef 08 8a 23 fa 2b 8a 0f
a2 8b 8c 58 6e 89 a5 71 5c e7 5b ed b9 05 fd 0d
cb 5b 0c c3 cf 9a 2f 53 28 c5 29 90 7d 3f 49 a3
b4 27 d0 32 b1 21 2b ac ff 88 ef a0 70 0a 72 63
12 fc d3 7a 93 dc 7e de 72 99 07 d9 1c a1 da 85
cf 91 7f a7 47 a0 2c 45 0d a3 f9 41 54 66 ea 7b
cb 08 97 ce 03 8a 8f c1 9a a1 55 93 11 7e 43 9c
68 c4 d9 c5 26 5b 69 6a 7f a0 87 82 62 10 80 49
f6 b4 ff 91 34 05 ac d6 c3
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: Ross Younger <[EMAIL PROTECTED]>
Subject: Re: SHA prng
Date: 23 Apr 2001 21:54:35 +0100 (BST)
Dobs <[EMAIL PROTECTED]> rearranged some electrons into article
<9c1hko$9c8$[EMAIL PROTECTED]> thus:
[ Generating a secure random number ]
>Can I just generate random number R by function
>srand( (unsigned)time( NULL ) ) instead of collecting entropy and than HASH
>(R).Would it be random number and would it be secure PRNG which could be
>used in cryptography aims?????
It would look random - but if you can predict the input, you can get
the output easily. There are only 3600 seconds in an hour; even if
you know the program was run, say, within the past six hours, there are
only 21600 possible values for an attacker to try. I would only call it
pseudo-random at best; it doesn't seem very good for crypto on its own.
>However I have a problem collecting entropy because it is really very
>difficult to make it use in my program.
As Tom observed, the less entropy you feed into your system, the easier
the output is to predict. Some programs collect entropy from multiple
sources; depending on what your program does, you might want to try
this, then feed it into SHA. For example, you could look at the least
significant bit of audio input, times between keystrokes, lengths of
mouse movements; perhaps the LSB or two from time(0) (could you hook a
Geiger counter up to your parallel port? :-) ) then feed it all into SHA.
Do take care, though; you might find strange `features' of your hardware,
like a mouse reporting its movements to the nearest /two/ pixels, or a
sound card which always reports zero when there isn't a microphone
connected to it....
If you have access to Schneier ("Applied Cryptography", ISBN
0-471-11709-9), section 17.14 has some ideas about collecting and
combining entropy.
HTH
Ross
--
Ross Younger news#[EMAIL PROTECTED] (if N fails, try N+1)
------------------------------
From: [EMAIL PROTECTED] (Joe H Acker)
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Mon, 23 Apr 2001 23:03:53 +0200
Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> I agree that the stand you take is far from provable, I am however rather
> biased, as I believe the statement to be false.
>
> The simple fact is that if you discard without examination no harm will be
> done to the sequence
Following your reasoning, I'd say you'd need to discard randomly.
"without examination" doesn't seem enough.
>, but if you discard based on examination you can and
> most likely will do harm to the sequence. There are a very few known methods
> of altering a stream like this based on examination that do not create
> problems.
Yes I agree, that's why I've taken back my first claim. But if you know
the method you use for discarding based on examination, aren't you able
to compute the maximum number of different sequences that will be
discarded if they are encountered in the output? Doesn't that mean that
you can compute the possible output sequences for a given sequence
length?
As an example: You examine a sequence of 128 bits. There should be 2^128
equally-weighted possibilities for an output of a tRNG. Now, if I
discard the all 1 and the all 0 sequence, there should be still 2^128-2
possible outputs, thus the change should be neglectable.
If you discard many more sequences that are really really bad for a
given application, you can still compute the number of possible outputs
(of the given sequence length examined). Isn't that enough to estimate
wether the tRNG is good enough for a given application?
Or is this wrong or too naive?
Regards,
Erich
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
