Cryptography-Digest Digest #653, Volume #12 Mon, 11 Sep 00 08:13:01 EDT
Contents:
Re: PRNG ("NP")
Re: CRC's as MAC's (Dido Sevilla)
Re: MAC (Dido Sevilla)
Re: Losing AES Candidates Could Be a Good Bet? (Runu Knips)
Re: RSA?? (Runu Knips)
Re: Camellia, a competitor of AES ? (Runu Knips)
Re: Camellia, a competitor of AES ? (Runu Knips)
Re: MAC ([EMAIL PROTECTED])
Re: MAC ([EMAIL PROTECTED])
Re: Known Plain Text Attack (Runu Knips)
Re: RSA public exponent (Mark Wooding)
Re: PRNG (Tim Tyler)
Re: Scottu19 Broken (Tim Tyler)
Re: Camellia, a competitor of AES ? (David Blackman)
Re: MAC (Ragni Ryvold Arnesen)
Re: Dangerous holiday reading? (pgp651)
Re: MAC ([EMAIL PROTECTED])
R: PRNG ("Cristiano")
Re: MAC (Ragni Ryvold Arnesen)
Re: RSA public exponent ([EMAIL PROTECTED])
Re: Losing AES Candidates Could Be a Good Bet? (Helger Lipmaa)
----------------------------------------------------------------------------
From: "NP" <[EMAIL PROTECTED]>
Subject: Re: PRNG
Date: Mon, 11 Sep 2000 10:14:26 +0200
Thanks Cristiano and others,
> The sequence to test must be of 20000 bits, so I don't understand the
> meaning of: "FIPS1402 4 fails at runs test for 1000 blocs tested".
I pass 1GBytes of random in FIPS140-2, and I see some PRNG fail !
-> rand()%255 for example :-)
I can see 1000 blocs of 20000 bits pass with no fail then 8 consecutive
FAILS.
So fails depend on initialisation of the PRNG.
So 1 bloc analyse is no enought...
In addition I analyse Gauss distribution for Byte and word collision.
NP Nicolas
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: CRC's as MAC's
Date: Mon, 11 Sep 2000 16:34:08 +0800
Bryan Olson wrote:
>
> Dido Sevilla wrote:
> >
> > I've been shopping for a MAC algorithm these days and have not been
> > fortunate enough to find an algorithm that provides reasonable defense
> > against forgery and modification detection while not being an
> > unreasonable algorithm to implement on a low-powered embedded
> > microcontroller. All the well-known ones are too expensive.
>
> What's your platform and what speed/code-size/memory-size
> could you live with?
>
The target embedded system is a 16-bit 80186 family microcontroller.
Half of its 20-bit address space is RAM (512K), and the other half is
flash. All of the MAC algorithms I've been able to find, HMAC-SHA1,
HMAC-MD5, HMAC-RIPEMD, UMAC, and hash127 all seem to be optimized for
32-bit processors and are painfully slow on machines with word sizes
smaller than that. I could use my good 'ol block cipher in CBC MAC
mode, but that won't work well because that's like encrypting the data
twice over, and I don't like the sound of that...
<snip>
>
> Fast MAC's have come a long way in the last several years.
> If you state your efficiency requirements, maybe someone
> can point you in a more promising direction.
>
My only criteria are that it be reasonably efficient on 16-bit x86 and
reasonably safe against forgery for messages of length less than 2^40
bits in length. My efficiency criterion roughly means that operations
are either byte-oriented or oriented towards 16-bit words as far as
possible. Most especially NO 32-BIT ROTATIONS! Almost all the MAC
algorithms I found use that, which is inordinately expensive on my
platform, not counting the prefetch cycle time and other things like
that; it requires at least four cycles for each one bit rotation,
meaning that for SHA-1, the 80 35-bit rotations take an aggregate total
of 11200 clock cycles, provided I can find a way to place all the
results that need rotation in the meager number of registers the x86
provides, which is highly unlikely...
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
PGP Key available at http://home.pacific.net.ph/~dido/dido.pgp
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: MAC
Date: Mon, 11 Sep 2000 16:46:12 +0800
[EMAIL PROTECTED] wrote:
>
> Hi all,
>
> I have just been reading one of the post about MAC. However, i have no
> idea what a MAC is? Could anyone explain it to me in a few lines?
>
MAC stands for Message Authentication Code. Basically, it's a keyed
hash of the transmitted data that is supposed to guarantee that the
message really comes from where it was expected to come and that the
data has not been modified on the way to its destination, provided that
the key used for the MAC is known only to the sender and receiver. It
is supposed to be intractable to make modifications to the data without
causing the MAC to change, and equally intractable to compute a correct
MAC on arbitrary data without knowing the key. It's basically similar
to the well-known message digest algorithms MD5 and SHA-1, except that
not only do these algorithms try to prevent people from making
modifications to the data without being detected, they also try to
ensure that the data could have only originated from a party which
possesses the correct key.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
PGP Key available at http://home.pacific.net.ph/~dido/dido.pgp
------------------------------
Date: Mon, 11 Sep 2000 11:06:40 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Losing AES Candidates Could Be a Good Bet?
[EMAIL PROTECTED] wrote:
> Really, who cares what the heck you think.
At least you care about it because you answer
his postings.
------------------------------
Date: Mon, 11 Sep 2000 11:16:34 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: RSA??
Big Boy Barry wrote:
> Can any government in the world crack it?
I _BELIEVE_ not. Nobody really knows. Mathematicans
believe that RSA is as hard as factoring, which is
a really hard problem, but AFAIK they still haven't
prooved that.
You should use key lengths of at least 768 bits,
however. 512 bits have been factorized.
------------------------------
Date: Mon, 11 Sep 2000 11:24:45 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Camellia, a competitor of AES ?
David A Molnar wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > NTT and Mitsubishi will propose Camellia in response to
> > calls for contributions from ISO/IEC JTC 1/SC27 and are
> > aiming at adoption as a international standard.
>
> This is nice, but does it tell us whether Camellia will be released to the
> public domain ? i.e. does the ISO require standardized algorithms to be
> unpatented?
I believe I've read recently in Bruce Schneiers Applied Crypto
that ISO standardization only guarantees that the algorithm
exist. But I don't have the book at hand and I might of course
be wrong.
------------------------------
Date: Mon, 11 Sep 2000 11:29:41 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Camellia, a competitor of AES ?
[EMAIL PROTECTED] wrote:
> 1. Because the US has, by far, the largest online economy. If the ISO
> simply ignored the existing US standard, we'd have the reverse
> situation to digital signatures. (Where the US standard is DSA, and
> the ISO standard RSA).
An argument for the dustbin. The largest nation in the internet
will be China. they just have more people than anyone else.
> 2. Because, overall, AES canidates have received _much_ more analysis
> than any other canidtaes.
THAT is an argument.
> 3. Because it's unlikely, in my opinion, that anything superior would
> suddenly crop up if submissions were solicited world wide.
Yep.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: MAC
Date: Mon, 11 Sep 2000 09:19:52 GMT
Thank you very much for your help.
Brice.
In article <[EMAIL PROTECTED]>,
Dido Sevilla <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> >
> > Hi all,
> >
> > I have just been reading one of the post about MAC. However, i have
no
> > idea what a MAC is? Could anyone explain it to me in a few lines?
> >
>
> MAC stands for Message Authentication Code. Basically, it's a keyed
> hash of the transmitted data that is supposed to guarantee that the
> message really comes from where it was expected to come and that the
> data has not been modified on the way to its destination, provided
that
> the key used for the MAC is known only to the sender and receiver. It
> is supposed to be intractable to make modifications to the data
without
> causing the MAC to change, and equally intractable to compute a
correct
> MAC on arbitrary data without knowing the key. It's basically similar
> to the well-known message digest algorithms MD5 and SHA-1, except that
> not only do these algorithms try to prevent people from making
> modifications to the data without being detected, they also try to
> ensure that the data could have only originated from a party which
> possesses the correct key.
>
> --
> Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
> ICSM-F Development Team, UP Diliman +63 (917) 4458925
> PGP Key available at http://home.pacific.net.ph/~dido/dido.pgp
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: MAC
Date: Mon, 11 Sep 2000 09:21:27 GMT
So what hashing algorithm would one use in practice to implement MAC?
Brice.
In article <[EMAIL PROTECTED]>,
Dido Sevilla <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> >
> > Hi all,
> >
> > I have just been reading one of the post about MAC. However, i have
no
> > idea what a MAC is? Could anyone explain it to me in a few lines?
> >
>
> MAC stands for Message Authentication Code. Basically, it's a keyed
> hash of the transmitted data that is supposed to guarantee that the
> message really comes from where it was expected to come and that the
> data has not been modified on the way to its destination, provided
that
> the key used for the MAC is known only to the sender and receiver. It
> is supposed to be intractable to make modifications to the data
without
> causing the MAC to change, and equally intractable to compute a
correct
> MAC on arbitrary data without knowing the key. It's basically similar
> to the well-known message digest algorithms MD5 and SHA-1, except that
> not only do these algorithms try to prevent people from making
> modifications to the data without being detected, they also try to
> ensure that the data could have only originated from a party which
> possesses the correct key.
>
> --
> Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
> ICSM-F Development Team, UP Diliman +63 (917) 4458925
> PGP Key available at http://home.pacific.net.ph/~dido/dido.pgp
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Mon, 11 Sep 2000 11:41:14 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Known Plain Text Attack
[EMAIL PROTECTED] wrote:
> Is there any possibility to use known plain text attack for the
> following situation : a have a file in the original form and the
> encrypted one and I also have the password. What else do I need? I need
> to find out the method it was use to encrypt the original file with
> this key (probably a hash was substract from this key).
Hmm. Getting the algorithm is normally done using disassembling,
or analyzing hardware, etc.
Finding the algorithm is impossible; you can only test if one
of the algorithms known to you yield the same results, but you
can still not be sure the attacker used the same algorithm.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: RSA public exponent
Date: 11 Sep 2000 09:41:44 GMT
Ed Pugh <[EMAIL PROTECTED]> wrote:
> When generating keys, we can "set" one exponent to a specific number
> and let the algorithm find the other exponent. Both exponents must
> be relatively prime to phi(N) (as stated elsehwere).
Better stated: if your chosen exponent isn't relatively prime to
\lambda(n) then the other exponent doesn't exist.
> Now, if the chosen exponent is small (in comparison with N), then the
> other exponent will most likely be large (AFAIK; someone please correct
> me if I am wrong about this). Therefore, it is best to choose the
> public exponent to be relatively small, so that the secret exponent
> will be large.
If one exponent is small, the other must be (fairly) large; else e d
won't be greater than \lambda(n). If you choose (say) e large, the
probability that d will be small is negligible.
> Since it is actually the secret exponent that we want to keep from
> being found, I am not really sure that the size of the public exponent
> has much bearing on the security of the secret key.
As described elsewhere, a plaintext can be recovered if it's sent to e
different keys all with the same public exponent e. This doesn't happen
in practice, because a message is padded with separate random data for
each recipient.
> It is (AFAIK) currently believed that factoring N is the easiest way
> to find the secret exponent of a RSA key. I often wonder, however, if
> there may be an easier attack available, given the fact that there are
> infinitely many possible secret exponents.
There is no such attack. Knowing both exponents allows efficient
factoring of the modulus (you discover a nontrivial square-root of -1).
Hence, finding a private exponent is as hard as factoring.
-- [mdw]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: PRNG
Reply-To: [EMAIL PROTECTED]
Date: Mon, 11 Sep 2000 09:17:05 GMT
S. T. L. <[EMAIL PROTECTED]> wrote:
: /* DIEHARDC ok (no 0.00 no 1.00) */
: This is not the way to interpret DieHard results.
It seemed like a pretty fair statement. Unless you use the version with
the automated summary, it's fair to conclude that test results with no
entries < 0.01 or > 0.99 pass.
Of course there are other ways to pass as well, but this is one of them.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Scottu19 Broken
Reply-To: [EMAIL PROTECTED]
Date: Mon, 11 Sep 2000 09:26:34 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote:
:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:> : [EMAIL PROTECTED] wrote:
:> :> [EMAIL PROTECTED] wrote:
:> :> : I heard that the NSA broke Scottu19, is that true?
:> :>
:> :> Is http://www.deja.com/threadmsg_ct.xp?AN=666637659 the source of
:> :> your information? The only other mention recently here appears to
:> :> be http://x60.deja.com/threadmsg_ct.xp?AN=666850697.1
:>
:> : Both posters are in fact me. [...]
:>
:> You mean you post under "John Myre <jmyre[at]sandia.gov>" sometimes,
:> signing yourself as "JM"?
: No, I was 'phreakerboy'. [...]
Hmm. It's not common to anonymously spread FUD about someone else's
technology - and then to subsequently confess (without any sign of
duress being applied) that you're actually someone with a known
distaste for the author.
Oh well, full marks for revealing phreakerboyz' identity, anyway.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: Camellia, a competitor of AES ?
Date: Mon, 11 Sep 2000 20:49:27 +1100
Runu Knips wrote:
> > 3. Because it's unlikely, in my opinion, that anything superior would
> > suddenly crop up if submissions were solicited world wide.
>
> Yep.
Better than that even. AES did solicit for submissions world wide. And
in fact 2 of the 5 finalists are not from the USA.
------------------------------
From: Ragni Ryvold Arnesen <[EMAIL PROTECTED]>
Subject: Re: MAC
Date: Mon, 11 Sep 2000 12:09:23 +0200
[EMAIL PROTECTED] wrote:
> So what hashing algorithm would one use in practice to implement MAC?
Any (reasonably good) encryption algorithm in MAC mode would do the trick. A
common approach is to use the same algorithm both for encryption and MAC
generation, only in different modes and with different keys. Very useful if
memory is limited, e.g. in mobile phones.
-Ragni
------------------------------
Date: 11 Sep 2000 10:15:05 -0000
From: pgp651 <Use-Author-Address-Header@[127.1]>
Subject: Re: Dangerous holiday reading?
Very good writing, in general.
This one is very, very good. Thanks.
And it is often advisable in life to demonstrate an IQ that is lower than the
one your actually have.
On Sun, 10 Sep 2000, Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>The best is to read such books (or any books on the 'index'
>if you are acquianted with religion) and have the information
>stored in your brain so that you don't need to carry them
>with you on your journey anywhere. The scientists working
>in the project of Orwell haven't yet got the breakthrough
>necessary for reading out the bits on your biological
>storage medium. And it is often advisable in life to
>demonstrate an IQ that is lower than the one your actually
>have.
>
>M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: MAC
Date: Mon, 11 Sep 2000 10:58:00 GMT
So why not just use the old public key system to sign your message then?
The MAC method implies that the sender and receiver share a common
secret key. What are the benefits of MAC over standard signature using
public key encryption?
Brice.
In article <[EMAIL PROTECTED]>,
Ragni Ryvold Arnesen <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
>
> > So what hashing algorithm would one use in practice to implement
MAC?
>
> Any (reasonably good) encryption algorithm in MAC mode would do the
trick. A
> common approach is to use the same algorithm both for encryption and
MAC
> generation, only in different modes and with different keys. Very
useful if
> memory is limited, e.g. in mobile phones.
>
> -Ragni
>
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: R: PRNG
Date: Mon, 11 Sep 2000 13:25:59 +0200
NP wrote:
> > The sequence to test must be of 20000 bits, so I don't understand the
> > meaning of: "FIPS1402 4 fails at runs test for 1000 blocs tested".
>
> I pass 1GBytes of random in FIPS140-2, and I see some PRNG fail !
> -> rand()%255 for example :-)
>
> I can see 1000 blocs of 20000 bits pass with no fail then 8 consecutive
> FAILS.
>
If you want to get a number lower than the maximum range of a PRNG, you need
this (from an old message):
" Suppose you used a generator that put out uniformly distributed
numbers between 0 and 255, and you wanted numbers from 0 to 99. You could
get this by discarding any generator outputs greater than 199, and taking
the acceptable outputs modulo 100. In general, if you have random numbers
ranging from 0 to a-1, and you need numbers from 0..b-1, assuming a > b, you
need to throw out all the random numbers greater than or equal to (a div b)
* b."
This is my implementation (in this case r250() put out integers between 0
and 2^32-1):
(ULONG is unsigned long)
// Return ULONG in the range 0...n-1
ULONG RND(const ULONG n)
{
const ULONG S=4294967296./n,X=S*n;
ULONG x;
if(X)
do x=r250(); while(x>=X);
} else x=r250();
return x/S; // A little bit faster than x%n
}
In my tests I have found far good also r250()>>24 (but this is not the
proper way).
I think that to get a number between 0...254, rand()%255 is the worst way
(probably you will have many collisions).
> So fails depend on initialisation of the PRNG.
For many PRNG the initialization is very important especially for those
which have an initialization vector (not just a seed).
> So 1 bloc analyse is no enought...
Sure. To get a rasonable analysis of a PRNG you need tens of trials and may
be useful to see the mean and the standard deviation of those trials.
> In addition I analyse Gauss distribution for Byte and word collision.
Can you be a little bit clear?
Cristiano
------------------------------
From: Ragni Ryvold Arnesen <[EMAIL PROTECTED]>
Subject: Re: MAC
Date: Mon, 11 Sep 2000 13:41:13 +0200
[EMAIL PROTECTED] wrote:
> So why not just use the old public key system to sign your message then?
>
> The MAC method implies that the sender and receiver share a common
> secret key. What are the benefits of MAC over standard signature using
> public key encryption?
Less memory and CPU costs, no need for PKI, you can use the same algorithm
to ensure both confidentiality and integrity.
MACs are particularly useful in mobile phones or other devices with very
limited memory, computational capabilities and bandwidth. For an example,
see the algorithm specifications for 3G/UMTS:
http://www.etsi.org/dvbandca/3GPP/3gppspecs.htm
KASUMI is the cipher algorithm, f8 is the confidentiality algorithm
(encryption mode) and f9 is the integrity algorithm (MAC mode).
-Ragni
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA public exponent
Date: 11 Sep 2000 07:55:48 -0400
Mark Wooding <[EMAIL PROTECTED]> wrote:
> There is no such attack. Knowing both exponents allows efficient
> factoring of the modulus (you discover a nontrivial square-root of -1).
> Hence, finding a private exponent is as hard as factoring.
On the other hand, has it been proven that there is no other more
efficient crack (other than finding the secret key)?
(for e=2: rabin: finding square roots mod n is equivalent to factoring n)
(for e=3: Finding a corresponding private key actually lets you find some
square roots. But instead of finding a private key, might there
be some more efficient way of finding cube roots (without
enabling square roots) (NOTE: This would not factor n.
Has it been proven that finding cube roots mod n is not much
easier than finding square roots which is as hard as factoring?]
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: Losing AES Candidates Could Be a Good Bet?
Date: Mon, 11 Sep 2000 17:05:49 +0300
"Douglas A. Gwyn" wrote:
> > AES conference, Rijndael has at least as good a chance to be
> > chosen as any of the other algorithms, even though it has one
> > of the lowest security margins among the finalists.
>
> It isn't clear that the "security margin" has any actual
> significance. In fact for both DES and Skipjack, it has
> been suggested that the slimness of such a margin is an
> indication that the designers knew what they were doing.
At one conference, early in the AES process, I was talking to one of the
authors of one of the remaining AES finalists. One of the subjects in
our discussion was Rijndael vs. Crypton. Both ciphers are based on the
cipher Square, the first cipher being authored by the authors of Square,
while Crypton was constructed by some Korean guys. Interestingly,
Rijndael has less rounds for 128-bit keys than Crypton. Our mutual
conclusion was that the Korean guys did not have that much of inner
knowledge of this structure and therefore decided to add more rounds to
the cipher. On the other hand, the authors of Rijndael are very
confident of their design.
Later it was demonstrated that Crypton has several weaknesses Rijndael
doesn't.
Helger
http://www.tml.hut.fi
------------------------------
** 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
******************************
