Cryptography-Digest Digest #744, Volume #13 Sun, 25 Feb 01 01:13:01 EST
Contents:
Re: Processing on cyphertext (Benjamin Goldberg)
Re: Simple, possibly flawed, stream cipher ("Scott Fluhrer")
Re: super-stong crypto, straw man phase 2 (George Weinberg)
Re: RSA - public key exponents and plain text. (Rich Wales)
Re: Really big numbers in C (Taylor Francis)
Re: RSA - public key exponents and plain text. (Tony L. Svanstrom)
Re: Simple, possibly flawed, stream cipher ("Henrick Hellstr�m")
Re: Simple, possibly flawed, stream cipher ("Scott Fluhrer")
Re: ECC implementation ("Michael Scott")
Re: RSA - public key exponents and plain text. (Rich Wales)
Am I doing something silly by including my gnupghome with my archive? (jtnews)
Re: "RSA vs. One-time-pad" or "the perfect enryption" ("Michael Brown")
Re: Random numbers from your sound card (CR Lyttle)
Re: super-stong crypto, straw man phase 2 (Nicol So)
Re: Life cycle of keys (Nicol So)
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Processing on cyphertext
Date: Sat, 24 Feb 2001 20:33:05 GMT
With simple modoalphabetic substitution, you can do just about any
processing on ciphertext, without having to decrypt it. Somehow though,
I doubt that this is quite what you want.
--
A solution in hand is worth two in the book.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Simple, possibly flawed, stream cipher
Date: Sat, 24 Feb 2001 13:02:51 -0800
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I've thought about this idea for the last couple of days, and I haven't
> yet figured out what kind of weakness(es) it has.
>
> uint8 state[8] = { key };
> uint8 sbox[256];
>
> for( i = 0, x = 1; i < 8; ++i )
> x ^= sbox[ state[i] += (x>>i) & 1 ];
> keystreambit := x;
>
> I can't help but think that there's got to be a flaw here somewhere,
> since it's so simple, but I can't see where.
Ok, here's another attempt at cryptanalysis.
We first notice that the cipher always increments state[0]. In other words,
after the cipher has generated k bytes, it has also incremented state[0] by
exactly k.
Consider the following scenario:
- It outputs keystream byte k0, using the state array state0
- It performs the iterations to create the next keystream byte, and updates
the state array (we'll call the updated state array state1). state0[0]+1 ==
state1[0], because that's what the cipher always does.
- By chance, (x>>i) &1 happens to be zero for 1<=i<8. Or, in other words,
state0[i]==state1[i] for 1<=i<8.
- It outputs keystream byte k1
Now, it appears that this has probability 2**-7 of happening, and when it
does:
k0 ^ k1 = sbox[state0[0]] ^ sbox[state1[0]] = sbox[state0[0]] ^
sbox[state0[0]+1]
Now, with a known sbox, we can xor adjacent outputs, and from that, we can
deduce what state[0] could be, if the above scenario occurs, and we can
translate that into what state[0] of the initial key was. Looking at
1001outputs (1000 pairs), we would expect approximately 1000 possible
guesses of what state0 was initially. An expected 8 of these guesses would
be accurate, while the reset (approximately 992) would be false hits. If we
expect these false hits to be effectively random, then the correct state[0]
value should get about 12 hits, while incorrect values should get about 4
hits. We can use this to distinguish the correct value.
Once we have state[0], (I think) we can use a similar procedure to determine
state[1], etc, until we reduce the key into bruteforcible size.
Now, with an unknown sbox, we can xor adjacent outputs, and at any offset x
mod 256, we would expect an overabundance (by probability 1/128) of
sbox[x+y] ^ sbox[x+y+1] (where y is the unknown state[0] value). If we have
2**24 outputs (or, in other words, 2**16 outputs at each offset), we would
expect this overabundance to be detectable, and this would allow us to
reconstruct x^sbox[i+y] (where x, y are unknown 8 bit values). Then, by
assuming x and y (2**16 effort), we can use the previous attack to rederive
the key.
Thoughts?
--
poncho
------------------------------
From: [EMAIL PROTECTED] (George Weinberg)
Subject: Re: super-stong crypto, straw man phase 2
Date: Sat, 24 Feb 2001 22:29:23 GMT
On Sat, 24 Feb 2001 17:22:20 GMT, William Hugh Murray
<[EMAIL PROTECTED]> wrote:
>> For almost all of the publicly known attacks, doubling
>> the number of rounds adds substantial protection.
>
>Careful. While it surely adds complexity, it may or may not add
>protection. For example, going from 15 to16 rounds for the DES adds
>both complexity and protection; going from 16 to 17 adds complexity but
>no additional protection. The upper bound of the protection comes from
>the brevity of the key. Complexity that exceeds that bound is
>gratuitous.
>
>
The second part seems pretty clear (once brute-force
works better than differential cryptanalysis, there's
not much point in trying to provide additional protection against
differential cryptanlysis), but I'm dubious about the first part.
I'm pretty confident that nobody has ever proven that
brute force is the most effective way to attack DES
(with any number of rounds),
and almost certain nobody has proven that this becomes true
right at 16 rounds. And I think it's unlikely that it's true.
George
------------------------------
From: [EMAIL PROTECTED] (Rich Wales)
Subject: Re: RSA - public key exponents and plain text.
Date: 24 Feb 2001 22:32:46 -0000
John Savard wrote:
> > Some people have used 257, or even 3. . . .
> > So, yes, the public exponent can be quite small.
Tony L. Svanstrom replied:
> But isn't it safer with a not too small a number?
Maybe, maybe not.
There does exist an attack on RSA that exploits small public exponents.
Basically, if someone encrypts the same message "e" times, with "e"
different RSA public keys, each of which uses the same public exponent
"e", then it's possible to reconstruct the original message without
knowing any of the secret keys involved.
This attack does =not= allow you to discover any given secret key --
and it doesn't have any practical application to PGP, because before
PGP encrypts anything with RSA, it always sticks some random data at
the start of the message before doing the encryption.
Rich Wales [EMAIL PROTECTED] http://www.webcom.com/richw/
PGP 2.6+ key generated 2000-08-26; all previous encryption keys REVOKED.
RSA, 2048 bits, ID 0xFDF8FC65, print 2A67F410 0C740867 3EF13F41 528512FA
------------------------------
From: Taylor Francis <[EMAIL PROTECTED]>
Subject: Re: Really big numbers in C
Date: Sat, 24 Feb 2001 17:07:43 -0600
> Then you cannot be using Visual C++ 6.0 but must be using Visual
> C++ 1.52 or earlier, since this was the last version of Visual C++
> which could generate DOS programs.
>
> If you use Visual C++ 6.0, then your so-called "DOS program" is
> really a Windows-32 Console Application. If you don't believe be,
> try to run your "DOS program" on a real DOS machine, with no
> Windows....
Agreed... that's what I'm doing...
BUT...I don't know how to program in Windows... just in C that runs
under 'DOS'...
------------------------------
Subject: Re: RSA - public key exponents and plain text.
From: [EMAIL PROTECTED] (Tony L. Svanstrom)
Date: Sun, 25 Feb 2001 00:37:59 GMT
Rich Wales <[EMAIL PROTECTED]> wrote:
> John Savard wrote:
>
> > > Some people have used 257, or even 3. . . .
> > > So, yes, the public exponent can be quite small.
>
> Tony L. Svanstrom replied:
>
> > But isn't it safer with a not too small a number?
>
> Maybe, maybe not.
>
> There does exist an attack on RSA that exploits small public exponents.
> Basically, if someone encrypts the same message "e" times, with "e"
> different RSA public keys, each of which uses the same public exponent
> "e", then it's possible to reconstruct the original message without
> knowing any of the secret keys involved.
>
> This attack does =not= allow you to discover any given secret key -- and
> it doesn't have any practical application to PGP, because before PGP
> encrypts anything with RSA, it always sticks some random data at the start
> of the message before doing the encryption.
Yeah, but this isn't about PGP... Basically I'm going to allow people to
send me encrypt messages by using RSA directly on it.
(That's the short story, but IRL this is more of a bridge that will
allow messages to move in and out of a network that can't be viewed as
safe; but people will have the option to encrypt the message before they
send it.)
/Tony
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: Simple, possibly flawed, stream cipher
Date: Sun, 25 Feb 2001 03:05:43 +0100
"Scott Fluhrer" <[EMAIL PROTECTED]> skrev i meddelandet
news:979805$ggb$[EMAIL PROTECTED]...
> Once we have state[0], (I think) we can use a similar procedure to
determine
> state[1], etc, until we reduce the key into bruteforcible size.
Yes, but you would have to focus on the one half of the positions in the
stream where you expect that state[1] should be incremented, given the
already derived initial value of state[0]. If you know that (x shr 1) will
be even when the loop is entered for i = 1, then it would be pointless to
count these positions as occurances in the frequency analysis. Hence, you
would need twice as much data to derive the values of state[1] to state[7]
with the same level of certainty as you derived the value of state[0].
Furthermore, for the average arbitrary sbox about half of the values x in
the interval [0..255] does not have a solution s in the equation x = sbox[s]
xor sbox[s+1]. This fact helps to eliminate some valid occurances without
necessarily counting their frequency.
Excellent work, btw.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Simple, possibly flawed, stream cipher
Date: Sat, 24 Feb 2001 18:09:30 -0800
Henrick Hellstr�m <[EMAIL PROTECTED]> wrote in message
news:979p9h$afm$[EMAIL PROTECTED]...
> "Scott Fluhrer" <[EMAIL PROTECTED]> skrev i meddelandet
> news:979805$ggb$[EMAIL PROTECTED]...
> > Once we have state[0], (I think) we can use a similar procedure to
> determine
> > state[1], etc, until we reduce the key into bruteforcible size.
>
> Yes, but you would have to focus on the one half of the positions in the
> stream where you expect that state[1] should be incremented, given the
> already derived initial value of state[0]. If you know that (x shr 1) will
> be even when the loop is entered for i = 1, then it would be pointless to
> count these positions as occurances in the frequency analysis. Hence, you
> would need twice as much data to derive the values of state[1] to state[7]
> with the same level of certainty as you derived the value of state[0].
I don't believe so. Yes, state[1] increments half as often, however, the
corresponding event (state[2] through state[7] do not get incremented)
happens twice as often (probability 2**-6), and hence you should need about
as much data to get the same number of detected events. Actually, somewhat
less should suffice, because there would be fewer false hits to confuse the
issue.
>
> Furthermore, for the average arbitrary sbox about half of the values x in
> the interval [0..255] does not have a solution s in the equation x =
sbox[s]
> xor sbox[s+1]. This fact helps to eliminate some valid occurances without
> necessarily counting their frequency.
However, other values of x have multiple solutions. If you choose x
randomly, the expected number of solutions corresponding to that x is
precisely 1. Hence, if you have 1000 potential values of x, you would
expect that to lead to about 1000 solutions. Or at least, such was my
reasoning.
>
> Excellent work, btw.
Thanks
>
> --
> Henrick Hellstr�m [EMAIL PROTECTED]
> StreamSec HB http://www.streamsec.com
>
>
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: ECC implementation
Date: Sat, 24 Feb 2001 20:24:43 -0600
Its actually quite easy to test if the implementation is OK. Generate a
random point P on the curve and check that r.P=0, where r is the number of
points on the curve, and "0" is the point at infinity.
Generate a small curve with a prime number of points using the "schoof"
utility available from http://indigo.ie/~mscott/
and use that for testing purposes.
Mike Scott
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Bob Day wrote:
> >
> > Benjamin Goldberg wrote:
> >
> > > I'm currently tring to implement ECC in java, using BigIntegers.
> > >
> > > I'll readily admit that I don't understand elliptic curves as well
> > > as I'd like to, so I'm almost certain that there are mistakes in
> > > various places throughout the code. Also, I haven't implemented
> > > everything yet.
> >
> > Here's my half done painting, but I'm too lazy to finish it, so
> > could you do it for me?
>
> More like, "Here's my half done painting, is there anything wrong with
> how I've done the two point perspective? I'll fill in the other details
> once I've gotten that part right." Or maybe, "I'm making a painting of
> Theodore Roosevelt in the middle of the forest. I haven't got the trees
> and plants done, but do I at least have his face and figure done right?"
>
> If it's irredeemably flawed from the start, then I'll start over, I
> guess. If not, I'll finish it.
>
> --
> A solution in hand is worth two in the book.
------------------------------
From: [EMAIL PROTECTED] (Rich Wales)
Subject: Re: RSA - public key exponents and plain text.
Date: 25 Feb 2001 03:01:06 -0000
Tony L. Svanstrom wrote:
> Yeah, but this isn't about PGP... Basically I'm going to allow
> people to send me encrypt messages by using RSA directly on it.
If you're going to use RSA directly, be sure you've studied it very
carefully (including recent research results) in order to avoid the
known security pitfalls.
Remember that RSA is slow in comparison with symmetric algorithms; this
is one reason why PGP doesn't use RSA to encrypt the actual cleartext.
Rich Wales [EMAIL PROTECTED] http://www.webcom.com/richw/
PGP 2.6+ key generated 2000-08-26; all previous encryption keys REVOKED.
RSA, 2048 bits, ID 0xFDF8FC65, print 2A67F410 0C740867 3EF13F41 528512FA
------------------------------
Date: Sat, 24 Feb 2001 22:09:34 -0500
From: jtnews <[EMAIL PROTECTED]>
Subject: Am I doing something silly by including my gnupghome with my archive?
I'm making CD-RW disks with encrypted archives
of my work with an unencrypted gnupghome
directory on it.
Am I doing something silly? I figured that
gpg encoded my passphrase enough so that someone
would have to spend a long time before hacking
it. Or is hacking it with a gnupghome very trivial?
ls -lR
.:
total 310029
-r--r--r-- 1 root root 316844205 Feb 22 19:27
archive-2001-02-22-19-13-35.tar.gz.gpg
dr-xr-xr-x 2 root root 2048 Feb 22 19:27 gnupghome
./gnupghome:
total 8
-r--r--r-- 1 root root 1147 Feb 12 13:39 pubring.gpg
-r--r--r-- 1 root root 0 Feb 12 13:37 pubring.gpg~
-r--r--r-- 1 root root 600 Feb 22 19:27 random_seed
-r--r--r-- 1 root root 1380 Feb 12 13:39 secring.gpg
-r--r--r-- 1 root root 2560 Feb 12 13:46 trustdb.gpg
--
My U.S. Federal Gov't Budget Proposal for 2001 and Beyond
http://geocities.com/jtnews_optonline_net/budget.html
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Sun, 25 Feb 2001 17:26:00 +1300
"Sundial Services" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> S. wrote:
> > Therefore OTP:s really are unbreakable,
> > provided the pad is truly random and secret.
>
> ... which, of course, is the Achilles heel of this system in practice.
> If you cannot keep a message secret, who's to say that you'll actually
> be able to keep the one-time pad secret, and safe from Mr. Murphy's Law?
Enter quantum cryptography :)
Michael
------------------------------
From: CR Lyttle <[EMAIL PROTECTED]>
Subject: Re: Random numbers from your sound card
Date: Sun, 25 Feb 2001 04:54:11 GMT
Matt Johnston wrote:
>
> [EMAIL PROTECTED] wrote:
>
> ---snip---
> > A few weeks ago i came up with an idea: Using sound input to
> > generate random numbers. When you record any piece of audio from an
> > analogue source to your computer, you will always hear some noise
> > that was never present in the original audio, this is the result of
> > Electro Magnetic Radiation picked up by the ADC (Analogue to
> > Digital Converter) in your sound card. In fact the few lowest bits
> > can be cosidered random, as they are full of White radio noise, and
> > can be used to generate random numbers.
>
> Damien Miller has already implemented something similar for linux, see
> http://www.mindrot.org/code/audio-entropyd.php3
>
> Using the input of a detuned fm radio has been suggested as a good noise
> source.
>
> Cheers,
> Matt Johnston.
Wouldn't an am radio be better? Make sure there are no voice/music
detectable in the signal. Even the background radiation of the Universe
isn't white (i.e. pure random), but it should be good enough.
--
Russ
<http://home.earthlink.net/~lyttlec>
Not powered by ActiveX
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: super-stong crypto, straw man phase 2
Date: Sun, 25 Feb 2001 00:10:39 -0500
Reply-To: see.signature
William Hugh Murray wrote:
>
> ... going from 15 to16 rounds for the DES adds
> both complexity and protection; going from 16 to 17 adds complexity but
> no additional protection. The upper bound of the protection comes from
> the brevity of the key. ...
I don't think we know enough about DES to be able to say that. There may
be more efficient attacks than currently known/published. And round 17
may make such attacks less effective or less efficient. Unless we know
that no such attacks exist, we really cannot say for sure that round 17
adds no protection.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Life cycle of keys
Date: Sun, 25 Feb 2001 00:38:07 -0500
Reply-To: see.signature
Mok-Kong Shen wrote:
>
> It is thus of interest to ask a practical question, which
> for concretness I like to formulate thus: How many MB can
> one safely encrypt with AES and a single (random) key of
> 128 bits?
>
> A variant of the question involves key management, which,
> again for concreteness, I suggest to consider a fairly
> primitive one that I described previously as follows: ...
>
> Naturally, only approximate answers could at best be
> expected. However, one should also have some idea of the
> actual applicatiom environment, if there can be any
> concrete answers at all. For that I suggest to consider the
> following: ...
The critical knowledge that is necessary for such an estimation (but is
not available) is: relative to the best attacks available to the
adversary, what is the relationship among (1) the quantity of available
ciphertext, (2) the probability of success, and (3) the resources
required to execute he attack.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
** 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
******************************
