Cryptography-Digest Digest #769, Volume #13 Thu, 1 Mar 01 05:13:01 EST
Contents:
Re: what is the use for MAC(Message Authentication Code ), as there can be digital
signature? ("Scott Fluhrer")
Re: How to find a huge prime(1024 bit?) ("david Hopkins")
Re: Sad news, Dr. Claude Shannon died over the weekend. ("John A. Malley")
Re: Again on key expansion. (Paul Crowley)
Re: how long can one Arcfour key be used?? (Paul Crowley)
Re: HPRNG ("Matt Timmermans")
Re: encryption and information theory (Mok-Kong Shen)
Re: How to find a huge prime(1024 bit?) (Mok-Kong Shen)
Question about MD5,CRC and SHA(1). (Zeljko Vrba)
Rijndael decryption (Panu =?iso-8859-1?Q?H=E4m=E4l=E4inen?=)
Re: Improved stream cipher? (was: Re: Simple, possibly flawed, stream cipher)
("Henrick Hellström")
Re: Keystoke recorder (Frank Gerlach)
Re: Rijndael decryption ("ajd")
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: what is the use for MAC(Message Authentication Code ), as there can be
digital signature?
Date: Wed, 28 Feb 2001 22:14:03 -0800
John Savard <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Wed, 28 Feb 2001 19:41:53 GMT, "david Hopkins"
> <[EMAIL PROTECTED]> wrote, in part:
>
> >Why use for MAC(Message Authentication Code ),
> >as there can be digital signature?
>
> Without a MAC, a digital signature would have to be a public-key
> encipherment (or, rather, a private-key encipherment) of the entire
> message. With a MAC, just the MAC needs to be enciphered to sign a
> long message.
Technically speaking, in that case, you don't use a MAC to preprocess the
message before signing it, you use a secure hash.
--
poncho
------------------------------
From: "david Hopkins" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: How to find a huge prime(1024 bit?)
Date: Thu, 01 Mar 2001 06:35:08 GMT
I find a easy way to find a huge prime in Java (see bottom). But I don't
know whether it is
secure enough.
public BigInteger(int bitLength,
int certainty,
Random rnd)
Constructs a randomly generated positive BigInteger that is probably prime,
with the specified bitLength.
Parameters:
bitLength - bitLength of the returned BigInteger.
certainty - a measure of the uncertainty that the caller is willing to
tolerate. The probability that the new BigInteger represents a prime number
will exceed (1 - 1/2certainty). The execution time of this constructor is
proportional to the value of this parameter.
rnd - source of random bits used to select candidates to be tested for
primality.
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Sad news, Dr. Claude Shannon died over the weekend.
Date: Wed, 28 Feb 2001 22:58:59 -0800
"Douglas A. Gwyn" wrote:
[...]
> Shannon in fact
> wrote an earlier version of his paper(s) for one of the wartime
> cryptologic agencies; it's in the US National Archives, and
> my own assessment is that he knew about decibans etc. and
> organized and systematized the ideas in formulating his theory
> of information.
That's why I hold Dr. Shannon's work in high esteem. In my opinion,
Claude Shannon is to information theory what Sir Isaac Newton is to
physics.
Newton's Laws of Motion and the Law of Gravity united the observations
of Galileo Galilei and the Three Laws of Planetary Motion of Johannes
Kepler with a logically consistent framework. Newton gave us our first
working model of force and gravity for engineering purposes.
Shannon's Mathematical Theory of Communication united the results of Dr.
Harry Nyquist (the Nyquist Sampling Theorem) and R. V. L. Hartley (the
concept of efficient encoding of messages with respect to their
information given by H = n log s, n = number of selected symbols and s =
number of possible symbols) in a logically consistent framework.
Shannon gave us our first working model of communications that (1)
related the information measure H to the probability of the symbol's
occurrence and (2) showed the existence of coding schemes maximizing
transmission bit rates through noiseless and noisy communications
channel. Shannon went on to apply the communications model to
cryptanalysis and cryptography - what a wonderful way to validate
aspects of the model!
John A. Malley
[EMAIL PROTECTED]
------------------------------
Subject: Re: Again on key expansion.
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Thu, 01 Mar 2001 06:33:42 GMT
"Cristiano" <[EMAIL PROTECTED]> writes:
> This sound a little strange in the world of cryptography, where averything
> is possible :-)
If only :-)
> I have thought about to use the elliptic curve (as posted in other message),
> but I have not received any comment...
What's the advantage of this method over the method described by
Schneier?
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: how long can one Arcfour key be used??
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Thu, 01 Mar 2001 06:34:00 GMT
Bryan Olson <[EMAIL PROTECTED]> writes:
> Yes, see Paul Crowley's page at:
> http://www.cluefactory.org.uk/paul/rc4/
A much more detailed analysis of the bias in RC4 can be found in Scott
R Fluhrer and David A McGrew, "Statistical Analysis of the Alleged RC4
Keystream Generator", Fast Software Encryption Seventh International
Workshop. I don't know if this paper is available online though -
Scott?
Their distinguisher requires 2^30.6 bytes of output.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: HPRNG
Date: Thu, 01 Mar 2001 07:05:41 GMT
Fine idea, but you'll have trouble telling when a photon is actually
emitted -- You can make devices that produce on photon at a time, but as far
as I know you can't produce exactly one on demand. Also, it would be
absorbed by the first filter 50% of the time.
It would be better to use one of those nifty crystals (I don't know what
they're made of) that sends the photon either left or right depending on its
polarization. You can place separate detectors in each path and use the
left/right decision as your 0/1 bit. As i've mentioned in another thread
(on OTP) this system has the nice property that you can place a strong lower
bound on the amount of entropy you get per bit by measuring the physical
properties of the system.
Radioactive decay is also a fine source of real entropy, because half-lives
for radioactive elements are will defined. You can get nice radioactive
bits for free from fourmilab any time you want them:
http://www.fourmilab.ch/hotbits/
I use this service every day, to generate unique IDs for the #ifndef XXXXXX
... #endif pairs that make sure my C++ headers only get included once.
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Here's an idea for a TRNG, which uses components which are used in
> Quantum Cryptography. Get a device which produces one photon at a time,
> send it through a polarizer. Follow this with a second polarizer at 45
> degree angle from the first. Photons will go through the first 100% of
> the time, and through the second exactly 50% of the time. Measure
> photon/no photon as your bit of randomness. I call the system a
> Heisenburg Random Number Generator, or HRNG. Bits might be slightly
> biased, if the mirrors aren't exactly 45 degrees apart, but they should
> not be correlated in any way, shape, or form.
>
> --
> I used to drive a Heisenburgmobile, but every time I looked at the
> speedometer, I got lost.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: encryption and information theory
Date: Thu, 01 Mar 2001 08:19:49 +0100
Benjamin Goldberg wrote:
>
> Mok-Kong Shen wrote:
> >
> > Benjamin Goldberg wrote:
> > >
> > > Mok-Kong Shen wrote:
> > > >
> > > > John Savard wrote:
> > > > >
> > > > [snip]
> > > > >
> > > > > More precisely: if the message contains N bits of information,
> > > > > and occupies M bits of bandwidth, and the K is K bits long, the
> > > > > entropy of the encrypted message is N+K bits, *or* M bits,
> > > > > whichever is less.
> > > > >
> > > > > In the case of RSA encryption, given that you know the public
> > > > > key, no increase of entropy takes place.
> > > >
> > > > In the sense of crypto, entropy is related to the difficulty
> > > > for the opponent to decrypt, I suppose. How does one explain
> > > > that a key enhances entropy in the symmetric case but not in
> > > > the asymmetric case, as you stated above? Thanks.
> > >
> > > Because RSA encryption is a known transformation which has an
> > > inverse.
> > >
> > > Also, you can 'break' RSA encryption [by factoring] without even
> > > having a message to look at.
> > >
> > > With symmetric encryption, breaking the system [by brute force]
> > > effectivly consists of subtracting the entropy of the plaintext from
> > > the entropy of the ciphertext, producing the entropy of the key.
> >
> > From the point of view of the opponent, I don't see
> > any 'inherent' difference between breaking, say, RSA and
> > AES. Both require 'efforts'.
>
> Yes, but entropy is a measure of randomness/unpredictability/
> information, not of how hard it is to break.
But what is more difficult to predict is certainly
positively correlated to what is hadrder to break, isn't
it? My first follow-up was asking to explain the issue
sketched with consideration of this fact.
>
> > I think that one has in the asymmetic case to consider the
> > 'entropy' of the private key. For, while in the symmtric
> > case one has a single key, in the asymmetric case it is
> > the ensemble of the public and the private key that
> > constitutes the 'key' that we have to consider in the
> > current context.
>
> Consider the case when we are encrypting purely with PK, rather than
> using PK to encrypt a symettric key. Is there any information that is
> added to the message during encryption that the attacker does not know?
> No. The only information added is that of the public key, which the
> attacker does know.
>
> Consider symettric encryption. Is there information added to the
> message during encryption which the attacker does not know? YES, the
> secret key is added, and the attacker does not know the secret key.
>
> Thus, no randomness, no unpredictability, no unknown information, no
> entropy is added in the case of PK encryption.
>
> The fact that work is required to find the method for removing the
> public key information is needed does not make the public key have
> entropy.
>
> Consider any fixed length string that has been produced by a TRNG. Does
> the string have entropy? Not after you know it. Information sources
> produce entropy, but known pieces of information do not contain entropy.
>
> We can predict (before they're seen) that the first X bits of data
> produced by a TRNG will have X bits of entropy. However, once those X
> bits have been seen, they have no entropy.
>
> This might be strange, but entropy is a measure of information. If
> someone tells you something you already know, his message contains no
> information -- thus no entropy. Once you've seen [once you know] a
> piece of data, then that data has no more entropy (unless you forget
> it).
I refer to what I wrote above and like to add that to
the sender of a symmetric system, the processing also
adds no 'entropy', since he 'knows' the key. Note also
what Douglas Gwyn wrote, which I quote in the following:
Entropy, like every kind of knowledge, is contextual,
i.e. it must be measured relative to some state of knowledge.
Basically, the ciphertext is much more entropic for the
enemy eavesdropper than it is for the legitimate recipient.
The difference is essentially the entropy of the key.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: How to find a huge prime(1024 bit?)
Date: Thu, 01 Mar 2001 08:30:10 +0100
david Hopkins wrote:
>
> I find a easy way to find a huge prime in Java (see bottom). But I don't
> know whether it is
> secure enough.
>
> public BigInteger(int bitLength,
> int certainty,
> Random rnd)
> Constructs a randomly generated positive BigInteger that is probably prime,
> with the specified bitLength.
> Parameters:
> bitLength - bitLength of the returned BigInteger.
> certainty - a measure of the uncertainty that the caller is willing to
> tolerate. The probability that the new BigInteger represents a prime number
> will exceed (1 - 1/2certainty). The execution time of this constructor is
> proportional to the value of this parameter.
> rnd - source of random bits used to select candidates to be tested for
> primality.
You generate primes that are highly probably (not certainly)
prime. Plenty of people do that, if I don't err. Could you
tell whether there are something novel/particular in your
scheme, either in generation of the random numbers or in
testing for primality etc.? Thanks.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Zeljko Vrba)
Subject: Question about MD5,CRC and SHA(1).
Date: 1 Mar 2001 07:40:02 GMT
Let f(x) be a message-digest function; MD5, CRC, SHA or SHA1.
Do any of these functions have a fixed point; i.e. does there exist a value
X such that f(X) == X? If there exists a fixed point, what is it? If it
doesn't can you point me to some proof that it doesn't?
Thanks!
------------------------------
From: Panu =?iso-8859-1?Q?H=E4m=E4l=E4inen?= <[EMAIL PROTECTED]>
Subject: Rijndael decryption
Date: Thu, 01 Mar 2001 10:01:03 +0200
Hello,
A while ago I was asking how to implement the Rijndael S-box inverse by using
the encryption S-box in order to save some space. I got it now: a table look up
is used for the multiplicative inverse in GF(2^8) and this can be shared between
encryption and decryption. Some extra logic is only needed for the affine
transformation and its inverse as the specification says (I'm talking about a
hardware implementation here).
I found the affine mapping at byte level in Brian Gladman's code and my
encryption is working ok now. However, I have problems with the inverse affine
(the shifts and xors). Does someone know how to do it?
In addition, the round key calculation in decryption troubles me. Right now I'm
calculating the encryption round keys "on the fly", which saves area and also
the overhead of calculating all the round keys in advance. I was thinking of
saving only the last encryption round key and use it to calculate the decryption
round keys. If decryption is always done after encryption (with the same key),
this also saves the key calculation overhead in decryption. However, if I
understood it right, this requires extra logic for the inverse of the encryption
key calculation to enable rolling back to the previous encryption keys.
Any suggestions? What is the best way considering area/performance? Is it
reasonable to calculate the round keys in advance also in encryption, store them
and then use the stored round keys in both encryption and decryption? Or to
calculate the encryption keys on the fly, store them, and use the stored keys
only in decryption? Or to save only the last encryption round key and calculate
the decryption round keys from it?
-- Panu Hämäläinen
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: Improved stream cipher? (was: Re: Simple, possibly flawed, stream cipher)
Date: Thu, 1 Mar 2001 09:24:45 +0100
"Henrick Hellström" <[EMAIL PROTECTED]> skrev i meddelandet
news:97jo9b$m2p$[EMAIL PROTECTED]...
> "Benjamin Goldberg" <[EMAIL PROTECTED]> skrev i meddelandet
> news:[EMAIL PROTECTED]...
> > In fact, we may even be able to find some [fixed!] chosen plaintext
> > which causes the cipher state to synchornize to some particular value,
> > or which will cause the exact state [or a trivially reversible transform
> > of it] to be outputed.
>
> Hm, no, such an a attack would be provably impractical. Synchronization
just
> _might_ happen as a result of a chosen plain text or chosen cipher text
> attack, but only with the same probabiltity as if it would occur by
chance.
However, if I am not mistaken, if you find a particular eight byte plain
text/cipher text pattern at two different positions, then you know that the
value of state will be the same at both positions. I.e. If PT(j) =
PT(k),...,PT(j+7) = PT(k+7), CT(j) = CT(k),...,CT(j+7) = CT(k+7), then
state(j+8) = state(k+8).
Now suppose that you have prior knowledge of PT(j),...,PT(j+m),
CT(j),...,CT(j+m) and would like to forge the message PT(j),...,PT(j+m).
Then "all" you have to do is to wait for the pattern PT(j),...,PT(j+7),
CT(j),...,CT(j+7) to occur at some position k, and substitute
CT(k+8),...,CT(k+m) for CT(j+8),...,CT(j+m). I guess you could perform the
same attack against any 64-bit block size cipher in ECB, CFB, CBC or OFB
mode with a fixed key.
This attack would probably be feasible for an organization with huge
recording capabilities and the ability to intercept, process and manipulate
data transmissions at a very high rate. Conclusion: Let the SBox be key
dependent (or increase the size of state, but that would be less efficient).
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: Keystoke recorder
Date: Thu, 01 Mar 2001 10:04:56 +0100
nemo outis wrote:
>
> To respond to only one of the many interesting points you raise, I daily do an
> MD5 hash of every executable and near-executable (dll, vxd, etc.) on my system
> and compare them to "known-good" values. (Also look for new or deleted ones!)
> Takes about 15 minutes on my 20-gig drive (just right for enjoying that first
> cup of coffee). The hash program and the known-good values are on a (securely
> stored) encrypted CD.
>
> This is a very effective method unless/until the OS and major programs have
> backdoors built into them. But that's what's meant by trust models and why
> known-good was in quotation marks :-)
Ah, and whatabout this attack: Store malicious code in the mail folder
of your Mail Client. Employ a buffer-overflow in the inbox reading code
of the mail client. Initial intrusion was through a buffer overflow in
the html parser.
(The same approach works for and Operating System and it's swap file)
Does your method protect against this ?
I think you just put a big stick into the ground, and knowledgable
people will find a way around it.
------------------------------
From: "ajd" <[EMAIL PROTECTED]>
Subject: Re: Rijndael decryption
Date: Thu, 1 Mar 2001 09:37:19 -0000
Panu,
By doing some of the stages slightly differently, you can use the same
expanded round keys for both encryption and decryption. This may be better
in hardware (I presume you're talking FPGA here).
What is the structure of your final architechture? Would you really gain
from doing the round keys on the fly?
Andrew
"Panu Hämäläinen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Hello,
>
> A while ago I was asking how to implement the Rijndael S-box inverse by
using
> the encryption S-box in order to save some space. I got it now: a table
look up
> is used for the multiplicative inverse in GF(2^8) and this can be shared
between
> encryption and decryption. Some extra logic is only needed for the affine
> transformation and its inverse as the specification says (I'm talking
about a
> hardware implementation here).
>
> I found the affine mapping at byte level in Brian Gladman's code and my
> encryption is working ok now. However, I have problems with the inverse
affine
> (the shifts and xors). Does someone know how to do it?
>
> In addition, the round key calculation in decryption troubles me. Right
now I'm
> calculating the encryption round keys "on the fly", which saves area and
also
> the overhead of calculating all the round keys in advance. I was thinking
of
> saving only the last encryption round key and use it to calculate the
decryption
> round keys. If decryption is always done after encryption (with the same
key),
> this also saves the key calculation overhead in decryption. However, if I
> understood it right, this requires extra logic for the inverse of the
encryption
> key calculation to enable rolling back to the previous encryption keys.
>
> Any suggestions? What is the best way considering area/performance? Is it
> reasonable to calculate the round keys in advance also in encryption,
store them
> and then use the stored round keys in both encryption and decryption? Or
to
> calculate the encryption keys on the fly, store them, and use the stored
keys
> only in decryption? Or to save only the last encryption round key and
calculate
> the decryption round keys from it?
>
> -- Panu Hämäläinen
------------------------------
** 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
******************************
