Cryptography-Digest Digest #215, Volume #14 Mon, 23 Apr 01 12:13:01 EDT
Contents:
CHES 2001 Preliminary Program (Andre Weimerskirch)
RSA-like primes p and q ("Dobs")
generated sequence ("Dobs")
compare PRNG ("Dobs")
SHA prng ("Dobs")
Re: Why re-using the pad is not secure? ("Tony T. Warnock")
Re: First cipher (Mark Wooding)
Re: RSA-like primes p and q ("Tom St Denis")
Re: generated sequence ("Tom St Denis")
Re: compare PRNG ("Tom St Denis")
Re: 1024bit RSA keys. how safe are they? ("Tom St Denis")
Re: SHA prng ("Tom St Denis")
Re: counter intuative primes! (Walter Hofmann)
Re: OTP WAS BROKEN!!! (newbie)
----------------------------------------------------------------------------
From: Andre Weimerskirch <[EMAIL PROTECTED]>
Crossposted-To:
sci.crypt.random-numbers,comp.arch.fpga,comp.arch.arithmetic,comp.arch.embedded
Subject: CHES 2001 Preliminary Program
Date: Mon, 23 Apr 2001 11:00:36 -0400
Please find below the preliminary program for CHES 2001.
****************************************************************
PRELIMINARY PROGRAM
Workshop on Cryptographic Hardware and Embedded Systems
CHES 2001
Espace Saint Martin, Paris, France, May 13-16, 2001
http://www.chesworkshop.org
for registration information, check CHES web site above
****************************************************************
SUNDAY, May 13, 2001
****************************************************************
Pre-registration and reception 16:00 - 20:00
****************************************************************
MONDAY, April 14, 2001
****************************************************************
Registration 8:00 - 9:15
Welcome Remarks 9:15 - 9:30
Cetin Koc, David Naccache, Christof Paar
Invited Speaker 9:30 - 10:30
Ross Anderson, University of Cambridge, U.K.
Protecting Embedded Systems - the Next Ten Years.
******************** BREAK, 10:30-10:50 *********************
Side Channel Attacks I 10:50 - 12:10
Louis Goubin.
A sound method for switching between boolean and
arithmetic masking.
Eric Brier, Helena Handschuh, and Christophe Tymen.
Fast primitives for internal data scrambling in tamper
resistant hardware.
D. May, H. L. Muller, and Nigel Smart.
Random register renaming to foil DPA.
Manfred Aigner and Elisabeth Oswald.
Randomized addition-subtraction chains as a countermeasure
against power attacks.
******************** LUNCH, 12:10 - 13:30 ********************
Rijndael Hardware Implementations 13:30 - 14:30
Henry Kuo and Ingrid Verbauwhede.
Architectural optimization for a 3Gbits/sec VLSI
Implementation of the AES Rijndael algorithm.
Maire McLoone and J. V. McCanny.
High performance single-chip FPGA Rijndael algorithm
implementations.
Viktor Fischer and Milos Drutarovsky.
Two methods of Rijndael implementation in reconfigurable
Hardware.
Random Number Generators 14:30 - 15:10
Nick Howgrave-Graham, Joan Dyer, and Rosario Gennaro.
Pseudo-random number generation on the IBM 4758 secure
crypto coprocessor.
Werner Schindler.
Efficient online tests for true random number generators.
******************** BREAK 15:10-15:40 ********************
Elliptic Curve Algorithms 15:40 - 16:40
Nigel Smart.
The Hessian form of an elliptic curve.
Katsuyuki Okeya and Kouichi Sakurai.
Efficient elliptic curve cryptosystems from a scalar
multiplication algorithm with recovering y-coordinate
on the Montgomery-form.
Erkay Savas, Tom Schmidt, and Cetin K. Koc.
Generating elliptic curves of known order.
****************************************************************
TUESDAY, May 15, 2001
****************************************************************
Invited Speaker 9:30 - 10:30
Adi Shamir, The Weizmann Institute, Israel
New Directions in Croptography (no typo)
******************** BREAK, 10:30-10:50 *********************
Arithmetic Architectures 10:50 - 12:10
Leone Manuel.
A new low complexity fast parallel multiplier for a
class of finite fields.
Pradeep Dubey, Vijay Kumar, Atri Rudra, Charanjit Jutla,
Josyula R. Rao, and Pankaj Rohatgi.
Efficient implementations of Galois field arithmetic.
Alexandre F. Tenca, Georgi Todorov, and Cetin K. Koc.
High-radix design of a scalable modular multiplier.
Johann Groszschaedl.
A bit-serial unified multiplier architecture for finite
fields GF(p) and GF(2^m).
******************** LUNCH, 12:10 - 13:30 ********************
Cryptanalysis 13:30 - 14:30
Mike Bond.
Attacks on cryptoprocessor transaction sets.
Adam Young and Moti Yung.
Bandwidth-optimal kleptographic attacks.
Karine Gandolfi, Christophe Mourtel, and Francis Olivier.
Electromagnetic analysis: Concrete results
Embedded Implementations and New Ciphers 14:30 - 15:10
Daniel V. Bailey, Daniel Coffin, Adam Elbirt,
Joseph H. Silverman, and Adam D. Woodbury.
NTRU in Constrained Devices
Thomas Pornin.
Transparent harddisk encryption.
******************** BREAK, 15:10-15:40 ********************
Side Channel Attacks II 15:40 - 16:40
Colin Walter.
Sliding windows succumbs to big mac attack.
Christophe Clavier and Marc Joye.
Universal exponentiation algorithm: A first step towards
provable SPA-resistance.
Mehdi-Laurent Akkar and Christophe Giraud.
An implementation of DES and AES, secure against some
attacks.
******************** BANQUET ********************
****************************************************************
WEDNESDAY, May 16, 2001
****************************************************************
Hardware Implementations of Symmetric and Asymmetric Ciphers
9:30 - 10:50
Palash Sarkar and Subhamoy Maitra.
Efficient implementation of large stream cipher systems.
Ocean Cheung, K. H. Tsoi, Philip Leong, and Norris Leong.
Tradeoffs in parallel and serial implementations of the
International Data Encryption Algorithm IDEA.
Gerardo Orlando and Christof Paar.
A scalable GF(p) elliptic curve processor architecture
for programmable hardware.
Hanae Nozaki, Masahiko Motoyama, Atsushi Shimbo, and
Shinichi Kawamura.
Implementation of RSA Algorithm based on RNS Montgomery
Multiplication.
******************** BREAK, 10:50-11:20 *********************
Side Channel Attacks on Elliptic Curve Cryptosystems
11:20-12:20
Marc Joye and Christophe Tymen.
Protections against differential analysis for elliptic
curve cryptography: An algebraic approach.
Pierre-Yvan Liardet and Nigel Smart.
Preventing SPA/DPA in ECC systems using the Jacobi form.
Marc Joye and Jean-Jacques Quisquater.
Hessian elliptic curves and side-channel attacks.
**************** CONCLUDING REMARKS, 12:20 *******************
------------------------------
From: "Dobs" <[EMAIL PROTECTED]>
Subject: RSA-like primes p and q
Date: Mon, 23 Apr 2001 16:28:32 +0200
In one of the algorithm there was written that I need RSA-like primes p and
q . What does 'RSA-like' mean.
Does it only mean that I need big primes numbers (at least 512
bits)???????????????????????
------------------------------
From: "Dobs" <[EMAIL PROTECTED]>
Subject: generated sequence
Date: Mon, 23 Apr 2001 16:39:15 +0200
In Micali -Schnorr PRBG the output of the sequence is
z1||z2||z3..........||zl
In BBS the output is z1,z2,z3,.......,zl
What is the difference. Do I need in BBS generator to put comma every
generated bits (every iteration)
Why cannot I do it like Micali-Schnor PRBG and just to concatenate generated
bits?????????????????
------------------------------
From: "Dobs" <[EMAIL PROTECTED]>
Subject: compare PRNG
Date: Mon, 23 Apr 2001 16:50:49 +0200
How can I decide that one PRNG is better and more secure than other . Do I
have to test them for randomness. Is it true that the more random the number
is the more secure PRNG is?
------------------------------
From: "Dobs" <[EMAIL PROTECTED]>
Subject: SHA prng
Date: Mon, 23 Apr 2001 17:06:43 +0200
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: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Why re-using the pad is not secure?
Date: Mon, 23 Apr 2001 09:39:03 -0600
Reply-To: [EMAIL PROTECTED]
One can look at the Venona pages to get an idea of how some of this
works.
Given plaintexts P1 and P2 both encrypted with a single OTP (k) we have
C1=P1.XOR.k and C2=P2.XOR.k. We can construct a sequence by combining
cyphertexts C1.XOR.C2 which (as XOR is self-inverse, associative and
commutative) C1.XOR.C2=P1.XOR.P2. The key k has disappeared. The
statistics of C1 and C2 should be uniform whereas the statistics of
P1.XOR.P2 will not be uniform. This can be tested statistically. If the
OTP is combined with another combiner, the inverse of that combiner may
be used. Even if P1 and P2 are in different natural languages, the
statistics of their sum will not be uniform.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: First cipher
Date: 23 Apr 2001 15:41:00 GMT
[EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
> Mark Wooding wrote:
> >
> [snip]
>
>
> Your last post was helpful.
Good. This means we're not wasting our time, and you seem to be a quick
study.
> Two more questions:
>
> 1.) Would a separate SP network in the key schedule be a good way of
> confusing the relationship between the subkeys? (I don't mean
> modifying the cipher I posted, I'm asking in a general sense.)
If you're thinking about the related-key slide, that's not actually
related to the complexity of either your key schedule stepping function
or the Feistel F-function.
The attack works because of the structure of your key schedule. For
each round i, the current key schedule state k_i is processed in some
way to produce the round key z_i and a next key schedule state k_{i+1};
i.e., there exists some key evolution function G such that (z_i,
k_{i+1}) = G(k_i). If, for your initial state k_0 there exists some
k_{-1} such that (z, k_0) = G(k_{-1}), and the input key corresponding
to state k_{-1} is related in some reasonable way to the state for k_0,
then cipher is vulnerable to a related-key slide.
The cipher I proposed a few weeks ago, Gift, is *almost* vulnerable to
this attack. It's saved because its structure is slightly nonuniform:
it has whitening steps around the main Feistel core. I've not come up
with a way of applying Paul Onions' differential sliding technique[1] to
the related-key situation yet. (Anyone else feel like having a go?)
> 2.) Due to your excellent explanation, I think I understand the
> general idea of differential analysis. Are programs generally
> used to take care of the plug and chug? Are there cryptanalysis
> programs available or is is basically "roll your own"? Does
> anyone use MATLAB for cryptanalysis applications?
I tend to write quick programs in C or Perl to do the analysis on
S-boxes. I stick to C for more complicated things (like whole cipher
structures).
A fair while ago, a Feistel network which used only XOR-with-key,
substitutions and bit-permutations in its F-function was presented here.
The S-boxes were generated to resist differential attacks. The
structure of the cipher had a weakness, though. I wrote a program to
find the best differential through the entire cipher. I don't have a
copy left here, and Google's archive doesn't go back that far yet; maybe
someone else has a copy of the program.
[1] Against uniform Feistel networks with pre- and post-whitening;
presented at RSA 2001.
-- [mdw]
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: RSA-like primes p and q
Date: Mon, 23 Apr 2001 15:47:53 GMT
"Dobs" <[EMAIL PROTECTED]> wrote in message news:9c1hkl$9c8$[EMAIL PROTECTED]...
> In one of the algorithm there was written that I need RSA-like primes p
and
> q . What does 'RSA-like' mean.
> Does it only mean that I need big primes numbers (at least 512
> bits)???????????????????????
>
Where the heck did you hear "rsa-like primes"? It's a meaningless term.
RSA just requires two large primes...
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: generated sequence
Date: Mon, 23 Apr 2001 15:48:55 GMT
"Dobs" <[EMAIL PROTECTED]> wrote in message news:9c1hkm$9c8$[EMAIL PROTECTED]...
> In Micali -Schnorr PRBG the output of the sequence is
> z1||z2||z3..........||zl
> In BBS the output is z1,z2,z3,.......,zl
> What is the difference. Do I need in BBS generator to put comma every
> generated bits (every iteration)
> Why cannot I do it like Micali-Schnor PRBG and just to concatenate
generated
> bits?????????????????
>
Why not give it some thought, they are just using diff wordage.
You're not asking any sensible questions today my friend.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: compare PRNG
Date: Mon, 23 Apr 2001 15:49:14 GMT
"Dobs" <[EMAIL PROTECTED]> wrote in message news:9c1hkn$9c8$[EMAIL PROTECTED]...
> How can I decide that one PRNG is better and more secure than other . Do I
> have to test them for randomness. Is it true that the more random the
number
> is the more secure PRNG is?
You analyze the algorithm not the output.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: 1024bit RSA keys. how safe are they?
Date: Mon, 23 Apr 2001 15:50:31 GMT
"AY" <[EMAIL PROTECTED]> wrote in message
news:9c1fup$bsp$[EMAIL PROTECTED]...
>
> >Simpler answer: If all is done well a 1024-bit RSA key is sufficient for
a
> >long time assuming the key is not compromised.
>
>
> Also the assumptions of the lack of breakthrough in factoring, and success
> in building a "real" quantum computer, or at least a quantum circuit that
> implements quantum factoring.
Well true, but any breakthrough in factoring that can factor 1024-bit
numbers would be a major huge breakthrough.
> Not to mention "they" might be breaking 1024-bit RSA key for god knows how
> long. Whilst I believe this not to be the case, you'll never know... in
any
> case that's what they want you to belive...
Who's they? They shriners? I know they've been upto no good!
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: SHA prng
Date: Mon, 23 Apr 2001 15:52:45 GMT
"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.
Wrong. if R is not random then neither is HASH(R). The hash will at best
compress the entropy in R downto a shorter string.
> 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?????
You really should read more texts before writting any secure programs.
You're obviously new to the scene (which is cool). Unfortunately too many
people get hold of super DES or something and feel they can write their own
secure applications.
If you made your string R with only (about) 32-bits of entropy I could guess
the output of the hash prng with about 2^32 work which is not a heck of
alot.
Tom
------------------------------
From: [EMAIL PROTECTED] (Walter Hofmann)
Subject: Re: counter intuative primes!
Date: Mon, 23 Apr 2001 17:21:17 +0200
Reply-To: [EMAIL PROTECTED]
On 22 Apr 2001 15:06:54 -0700, Paul Rubin <[EMAIL PROTECTED]> wrote:
>
>"Tom St Denis" <[EMAIL PROTECTED]> writes:
>> Then I thought, well if the number is of the form N = MK + 1 where K is the
>> product of all 16 first primes, then N can't possibly be divisible by any of
>> them. This is true but this method takes longer to make primes then the
>> naive method.
>
>That means N=1 mod 3,5,7, etc. So it's not uniformly distributed among
>primes of its size.
No. Dirichlet's theorem on arithmetic progression says that the primes
are uniformly distributed in all prime residue classes.
If q is the product of the first 16 primes, Dirichlet's theorem says
that the probability (actually density) of finding a prime with the new
method is phi(q)/q times the probability of finding a prime with the
naive method.
Walter
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Mon, 23 Apr 2001 11:58:37 -0300
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.
HE DID NOT. He use only once his PAD.
What I'm trying to exploit is nothing more than REUSING HIS OWN PAD.
I do not wich key he used.
But if I re-use every time, the key obtained by Xoring PM (i) and his
ciphertext. I make this hypothesis : if the key I re-use is IDENTICAL to
HIS KEY, I'm sure that is the key he used. And the plaintext is
uncovered.
But my testing-key k' is different from k, than P ( is his plaintext )
Xor (k Xor k') will with high probability give a text with no sense.
I exploit 2 things :
- matching my hypothetical key with his key
- the probability that any text (with sense) if Xored with random key (
k Xor k'; k different from k') will not give me NECESSARLY A text (with
sense). If k' is equal to k , I'm sure 100 % that I could obtain by
simplification his PLAIN-TEXT.
What that mean?
I have the way to select few possible words. Inside this set, I'm sure
that the plaintext I try to uncover belong to this set.
I simulate the re-using of the key, that is the core of my strategy.
I do like if the sender re-use his own key.
Just a simulation. I can add another simulation with K' = K^(-1) ( the
inverse of k ). K' Xor K = 111111111111
With second test I will isolate P.
John Savard wrote:
>
> On Sun, 22 Apr 2001 16:13:13 -0300, newbie <[EMAIL PROTECTED]>
> wrote, in part:
>
> >Let encipher with truly random key a message M.
> >M is a plaintext
> >M =( M1 M2 M3 .... Mn)
> >K is a Keystream
> >K = ( K1 K2 K3......Kn)
> >C is a Ciphertext
> >C = ( C1 C2 C3 .... Cn)
>
> >What I know before breaking is C.
>
> >What I could know using extra-information is the specific langugage used
> >in my ciphertext
> >Sample : military communication. If I know that I can still assign a
> >high probability to occur to
> >all the words and and sentences used by militaries in their mails.
>
> So far, so good.
>
> >So I'm going to use a specific database to break my ciphertext.
> >I'm going to show you that even I have not extra-information, it makes
> >my breaking more difficult but not impossible.
>
> >If I try all 2^128 possible messages without any constraint, a large
> >part of them have no sense.
>
> >That means that only a low percentage of the 2^128 possible messages has
> >a sense.
>
> This also makes sense.
>
> >I still do not know wich of PM(i) is the "right one".
> >All are equiprobable. But I had limited the number of possible
> >solutions.
>
> And the claim is that you will _never_ know which one is right.
>
> >2.1 I choose the first PM(1) in the previous list (1.3)
>
> >2.2. I compute Output 1 ( K'(i) =Ouput (i) ).
>
> >K' (1) = PM(1) Xor C(1)
>
> The trouble is, K'(1) will be a perfectly good random one-time-pad!
>
> >2.3 I choose a plaintext of 128 bits ( 16 letters ) that have a sense.
>
> >Choosen plaintext = CHP= "I am an amateur!"
> >I can choose any plaintext of 128 bits that have a sense.
> >I can use the same text in all my next operations.
>
> OK, so CHP is *not* the same as PM(1). This is where it gets
> confusing.
>
> >2.4. I compute a second "ciphertext"
>
> >C'(1) = K'(1) Xor CHP.
>
> >C'(1) will allow me to find the solution.
>
> No, it won't.
>
> >C1 = M1 Xor K1 (1)
> actual ciphertext = most likely message xor hypothetical key
>
> >C'(1) = K'(1) Xor CHP (2)
> second ciphertext = hypothetical key xor standard message
>
> Oh, but K1 isn't the same as K'(1)? Oh dear, then this isn't making
> sense, it seems.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
** 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
******************************
