Cryptography-Digest Digest #164, Volume #14 Tue, 17 Apr 01 00:13:00 EDT
Contents:
Re: There Is No Unbreakable Crypto ("Henrick Hellstr�m")
Re: LFSR Security ("Trevor L. Jackson, III")
Re: Distinguisher for RC4 ("Scott Fluhrer")
Re: Reusing A One Time Pad ("Mark G Wolf")
Re: LFSR Security ("Scott Fluhrer")
HOW THE HELL DO I FIND "D"?!?! ("Dopefish")
Re: Distinguisher for RC4 ("Scott Fluhrer")
Re: C code for GF mults (Rob Warnock)
Re: Function other than xor? ("Douglas A. Gwyn")
Primality Testing Algorithm ("Raymond Lee")
Re: HOW THE HELL DO I FIND "D"?!?! (pjf)
Re: C code for GF mults ("Tom St Denis")
Terminology (about the OTP issue and all) ("Tom St Denis")
Incomplete Blocks in Twofish ("Mike Moulton")
Re: There Is No Unbreakable Crypto (David Wagner)
----------------------------------------------------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: There Is No Unbreakable Crypto
Date: Tue, 17 Apr 2001 03:02:06 +0200
So far, so good. This theorem is entailed by the security proof of counter
mode, unless I am mistaken. You are perfectly right about this.
I rather had some doubts about the proposal to extend the function to
generate even longer PRG outputs, e.g. G'(k) = G(k1)|G(k2) where k1|k2 =
G(k). I don't find it obvious that G^(n)(k) is (t,e)-secure even if E is
(t,2^(n+1),e)-secure. In the case of G^(n)(k) the output will be the
concatenation of the output of several related members of E, so the security
proof of counter mode will not apply (at least not directly). You would
furthermore have to make 2^(2n+1) queries to different elements of E to
obtain the information possibly present in G^(n)(k).
You will have a similar problem in the case of "super-strong crypto", simply
because the keys change and that's not coherent with the security
assumptions. For short, I don't see that the first phase super-strong crypto
E_k0(m1|k1)|E_k1(m2|k2)|... would generally be stronger than e.g. the mode
E_k(m1|r1)|E_k(m2|r2)|..., where the key is unchanging and the block halves
r1, r2, ... are chosen randomly and simply discarded at decryption.
But then again, some block ciphers might be such that such solutions are
provably secure. I just question the generality.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
"David Wagner" <[EMAIL PROTECTED]> skrev i meddelandet
news:9bg0vo$ds1$[EMAIL PROTECTED]...
> Henrick Hellstr�m wrote:
> >But theorem 5.5.1 doesn't really apply, or have I missed something??? It
> >applies to length doubling pseudo random bit generators, but I don't find
it
> >obvious that G(k) = E_k(0)|E_k(1) is such a thing.
>
> Theorem. If E forms a (t,2,e)-secure PRP, then G(k) := E_k(0)|E_k(1)
> is a (t,e)-secure PRG.
> Pf. Suppose not, so that A is an adversary that breaks G.
> By definition, Pr[A(G(k))=1] - Pr[A(x)=1] > e, where x is a r.v.
> with the uniform distribution. Now consider the adversary B
> against E that queries its oracle on input 0 to get output y,
> on input 1 to get output z, runs A on y|z, and outputs whatever
> A does. Then Pr[B^E_k = 1] = Pr[A(G(k))=1], and
> Pr[B^\rho = 1] = Pr[A(x)=1] where \rho is a r.v. distributed
> uniformly on the set of all permutations. Consequently,
> Adv B = Adv A > e, so B distinguishes E from an ideal cipher
> with advantage e. Now note that since A has running time at
> most t, so does B, and moreover A queries its oracle on only
> two points, so if G is not (t,e)-secure, then E is not (t,2,e)-secure.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Tue, 17 Apr 2001 01:12:07 GMT
"Trevor L. Jackson, III" wrote:
> David Wagner wrote:
>
> > Trevor L. Jackson, III wrote:
> > >David Wagner wrote:
> > >> That's exponential-time.
> > >
> > >In pathological cases yes.
> >
> > Proof, please.
>
> If I had a mathematical proof you would already have seen it.
> Preliminary to finding a proof of good performance is finding a proof of
> correct output. Since I've not accomplished the latter, asking for the
> former is fruitless.
>
> > How do you know it's not exponential-time on average?
>
> I don't.
... But I should have mentioned that the Weidemann algorithm for sparse
matricies, and in particular the possibilities of pruning described in
"http://www4.ncsu.edu/~wlee1/oral.pdf" gave me reason to believe otherwise.
>
>
> >
> > Without a proof (and considering how many plausible-sounding claims
> > about this approach turned out to be false -- thanks, Ian!), I hope
> > you'll forgive me if I'm skeptical.
>
> Forgiven. If I manage to find a better than exponential solution I'll
> deliver a formal ", but not forgotten". ;-)
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Distinguisher for RC4
Date: Mon, 16 Apr 2001 18:47:03 -0700
Michael Lee <[EMAIL PROTECTED]> wrote in message
news:9be91a$2va0$[EMAIL PROTECTED]...
> > Mark Wooding <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > >
> > > At the RSA Conference last week, Adi Shamir claimed that he'd found a
> > > way to distinguish the output of RC4 from random data with about 200
> > > bytes. (This is quite scary. It's put my right off the idea of using
> > > RC4 for anything serious.)
>
> Can anyone please point me towards an article or paper about this
> distinguisher (either written by Shamir or someone else). Thanks
Well, you can't get this yet, but:
_A Practical Attack on Broadcast RC4_, by Mantin and Shamir, presented at
FSE 2001.
--
poncho
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Mon, 16 Apr 2001 20:57:36 -0500
> However I can tell you that you can do something akin to this. Simply keep
a
> pointer to the next unused bit in the large pad. It becomes a OTP as
> commonly envisioned. If you do not do this and instead choose a random
> location in the large randblock at random you will very quickly reduce
your
> security to 0. In particular once you reach sqrt(length randblock) bits
> encrypted there is already a 50% likelihood that an attacker can read at
> least one bit.
Well if I wasn't going to reuse the pad that's obviously what I'd do but...
if I intend on reusing the pad I wouldn't want to do it in a predictable
way.
And one bit dose not a useful message make. Nor two, or three...
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Mon, 16 Apr 2001 19:01:35 -0700
Ian Goldberg <[EMAIL PROTECTED]> wrote in message
news:9bfcfi$9ol$[EMAIL PROTECTED]...
> In article <9bdo0c$ij8$[EMAIL PROTECTED]>,
> Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> >Of course, having 2n consecutive bits aren't the only was to get n-1 such
> >consecutive series -- if we are given 2 series of 3n/2 consecutive bits,
> >each series has (n-1)/2 such sets of consecutive bits, and so they both
give
> >us the requisite n-1 series, and so the same Gaussian Elimination
approach
> >works.
>
> You can get cases where your equations are not linearly independednt
> (see below).
Yeah, I know. However, if we model the equations we do get as "random"
(which isn't true), then the expected dimensions of the linear subspace
generated by the linear equations is small, and more importantly, the
expection is (I believe) bounded independant of n. Hence, it is small
enough to search through in "constant" time. Or so one hopes...
>
> >One obvious way to extend this is to make the wild claim that, if the
> >keystream bits you do have, there exists a a_0 < a_1 < ... < a_{n+1} and
n-1
> >distinct r_0, ..., r_{n-2}, you know the keystream output for b_{a_i +
r_j}
> >for all i, j, then you can derive the taps for a virtual LFSR (which
> >hopefully isn't too hard to translate back into the normal form).
>
> You'll have to add more conditions; what you've got isn't enough.
>
> For example, n=3, a_0 = 0, a_1 = 1, a_2 = 2, a_3 = 3, a_4 = 7, a_5 = 8,
> r_0 = 0, r_1 = 1.
>
> So you get to learn b_{0,1,2,3,4,7,8,9}, which I tell you is:
>
> 01110??011
>
> In fact, I'm going to tell you some more bits:
>
> 01110??01110??01110??01110
>
> Now you can see that, although you have at least two groups of at least
> 3n/2 bits (2n-1 in fact), your resulting equations are not linearly
> independent, so you don't have enough information.
>
> In fact, there are two differernt LFSRs (for n=3) which produce the
> above pattern.
>
> B-M says that if you have 2n consecutive bits, that always determines a
> unique LFSR.
Ok, so we can't quite do as good. As you point out, sometimes there isn't a
unique solution with the problem I'm solving. Since that is an artifact in
the problem space, and not my particular solution, I'm not too concerned
(just as long as we can enumerate all the possible solutions in a reasonable
amount of time).
>
> Now perhaps I've cheated, since with n=3, you know (well, for primitive
> connection polynomials) that the period will be 7. So those extra bits
> I gave you weren't actually "new". But you'll have to talk that into
> account in your statement.
Strictly speaking, that ain't cheating, because I never specified otherwise.
It'd be nice if I could prove something to the effect that 'if the equations
don't come from different periods, the dimension of the subspace will be
bounded by X', but since I don't know how to prove that, I'll stay away from
making a claim, and just call this a 'heuristic'.
--
poncho
------------------------------
From: "Dopefish" <[EMAIL PROTECTED]>
Subject: HOW THE HELL DO I FIND "D"?!?!
Date: Mon, 16 Apr 2001 21:31:09 -0500
i have been reading "The Mathematics of RSA"
(http://dslab.csie.ncu.edu.tw/~lucas/rsamath.HTM) and after working out all
of the stuff, i can figure out how to encrypt a message (which is extremely
easy, "c=m^e mod n") but i cannot find how to get d (the decryption key)
that would give you "m=c^d mod n." I am using a TI-89 calculator to work
out this stuff and i am intending to write a program for it. also, how
would i go about encrypting a string of letters? would i have to take the
ASCII code for each letter, encrypt it,then display the letter that
corrisponds to the encrypted ASCII code, or is there an easier way to do
this?
thanks, james
--
======BEGIN SIGNATURE======
A.K.A "Dopefish" or "fish" for short on Usenet.
Microsoft? Is that some kind of toilet paper?
"Rockin' the town like a moldy crouton!"
- Beck (Soul Suckin' Jerk - Reject)
"Help me, I broke apart my insides. Help me,
I've got no soul to sell. Help me, the only thing
that works for me, help me get away from
myself."
- Nine Inch Nails (Closer)
=====BEGIN GEEK CODE BLOCK=====
Version: 3.12
GO dpu s++:++ a---- C++++ U--->UL
P L+ E? W++ N+++ o+ K--- w+>w+++++
O--- M-- V? PS+++ PE Y-- PGP t 5--
X+ R tv b+ DI D+ G-- e- h! r z
======END GEEK CODE BLOCK======
(www.geekcode.com)
======END SIGNATURE======
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Distinguisher for RC4
Date: Mon, 16 Apr 2001 19:26:39 -0700
<[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Scott Fluhrer" <[EMAIL PROTECTED]> writes:
> > Actually, it shouldn't. The idea is that you examine the second byte of
200
> > different RC4 keystreams (generated by 200 different keys). It turns
out
> > that RC4 has a probabilty 1/128 of making the second value output after
key
> > setup take on the value 0.
>
> Is this really true? I'm doing some numerical simulations and I don't
> see it. Actually I see a dearth of zeros on the second byte, so far,
> but it's not statistically significant yet and may be a fluke.
>
> Has anyone verified this? Anyone have a prove or argument why it is so?
Yes, I just tried it on 256,000 keys, and I saw a zero as the second byte
1926 times.
Here's why it works: suppose, immediately after key setup, S[2]==0. Then,
if S[1]=X, then the first iteration sets j to X. Then, on the second
iteration, i is set to 2, j remains X (because S[i]=0), S[i] and S[j] are
swapped (which sets S[j] to 0 and S[i] to X), and then S[S[i]+S[j]] = S[X +
0] = 0 is output. Actually, there are a few values of X where this won't
work, but usually it does. This happens about 1/256 of time.
Then, if S[2]!=0, then RC4 acts essentially randomly, and outputs 1/256 of
the time.
Hence, the probability of a zero output is about 1/256+1/256 = 1/128
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Rob Warnock)
Subject: Re: C code for GF mults
Date: 17 Apr 2001 02:38:25 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
+---------------
| Just to show what a GF mult looks like here is my code I generally use...
+---------------
[...long-running bit-wise C code imitted...]
Hmmm... I tend to use stuff more like this:
/* multiply a and b in GF(2^r) mod p */
GF gf_multiply(GF a, GF b, int n, int p_log_table[], GF p_antilog_table[]) {
int log_a, log_b;
if (a == 0 || b == 0)
return (GF)0;
else {
log_a = p_log_table[a];
log_b = p_log_table[b];
return p_antilog_table[(log_a + log_b) % n];
}
}
When "n" (a.k.a. sizeof(p_antilog_table)]) gets too big for comfort,
break the log/antilog tables into pieces, and do it piecewise. But in
any case, it's a heck of a lot faster than stepping through the *bits*!!
-Rob
=====
Rob Warnock, 31-2-510 [EMAIL PROTECTED]
SGI Network Engineering <URL:http://reality.sgi.com/rpw3/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Function other than xor?
Date: Tue, 17 Apr 2001 02:47:53 GMT
newbie wrote:
> Bit-string it is not single variable.
It sure as heck was in your original posting.
I repeat: I don't think you're correctly using standard
mathematical terminology. That makes it too much trouble
to try to help find you an answer.
------------------------------
From: "Raymond Lee" <[EMAIL PROTECTED]>
Subject: Primality Testing Algorithm
Date: Tue, 17 Apr 2001 03:01:28 GMT
I have a question about Primarlity Testing algorithm, hope u can give me
some hints, I really don't know what's going on.
There are 4 integers: 10111, 11111, 11101 and 12329 that we want to test if
they are prime. And we need to apply probabilistic primarlity testing
algorithm to each one by choosing 5 witness that sum to the candidate prime.
What I am confused here is what's the purpose of witness? And what's the
approach of this problem? Still confused after reading some reference book.
Thanks.
------------------------------
From: [EMAIL PROTECTED] (pjf)
Subject: Re: HOW THE HELL DO I FIND "D"?!?!
Date: Tue, 17 Apr 2001 03:02:06 GMT
You have to use the Extended Euclidian Algorithm, which is listed
about halfway down that page.
Or you can just try plugging in numbers (slow) for small values of p,
q, and e.
-pjf
--
[EMAIL PROTECTED]
http://www.staticengine.com
Developer, Know Wonder Inc.
Musician, Static Engine
---
Digital Certificates provide no actual security for
electronic commerce; it's a complete sham.
-Bruce Schneier, Secrets & Lies
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: C code for GF mults
Date: Tue, 17 Apr 2001 03:30:31 GMT
"Rob Warnock" <[EMAIL PROTECTED]> wrote in message
news:9bgab1$pv9r$[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> +---------------
> | Just to show what a GF mult looks like here is my code I generally
use...
> +---------------
>
> [...long-running bit-wise C code imitted...]
>
> Hmmm... I tend to use stuff more like this:
<snip>
While your method is neat (any papers on the subject? I have seen a few but
I have lost the urls...) my code is more generic...
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Terminology (about the OTP issue and all)
Date: Tue, 17 Apr 2001 03:41:08 GMT
Plaintext: Original message
Ciphertext: Encrypted or Randomized Message
Symmetric Key: Short key shared between parties for transmitting messages
over insecure mediums
Asymmetric Key: A key split into two parts, one public and one private.
The public key is used to send messages to the owner of the private key.
Block Cipher: An algorithm that transforms a fixed size message to and from
ciphertext/plaintext.
Stream Cipher: [aka Keystream Generator] an algorithm that produces an
arbitrary length stream of bits that are mixed typically linearly with the
ciphertext/plaintext to perform the desired trasnformation.
An OTP is a version of a stream cipher where a symmetric key is used that is
the length of the message. If you re-use the key in any fashion than it's
not an OTP, or a pseudo-OTP (which is meaningless btw). It's a new system.
For example, a LFSR can produce a large stream of bits but it isn't an OTP
simply because key is smaller than the message size. Note that a n-bit LFSR
and and n-bit message can be considered an OTP if the original LFSR is
randomly seeded. If you use the n+1 bit of the LFSR output then it's not an
OTP any more...
So ... dudes... common. If you take a run of bits and re-use them don't
call it an OTP. Call it something else.....
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: "Mike Moulton" <[EMAIL PROTECTED]>
Subject: Incomplete Blocks in Twofish
Date: Mon, 16 Apr 2001 23:32:39 -0400
I've been in the process of testing and modifying the reference
implementation of Twofish to meet my needs, and I'm wondering what is the
process of encrypting incomplete blocks. What technique should I use
considering that I am going to be running it in ECB for Encryption and CBC
as a MAC? Should I pad the ECB encryption like MD4/MD5 with a string of
zero's and a the length of the padding, or use ciphertext-stealing? After
having read through Stinson/HAC/Schneier and the Twofish Book/Paper the only
one to even mention it was Applied Cryptgraphy by Schneier. Perhaps there
was a mention somewhere else about an *official* way to implement padding in
Twofish. If so I'd be grateful for the reference.
Thanks,
Mike Moulton
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: There Is No Unbreakable Crypto
Date: 17 Apr 2001 04:01:26 GMT
Henrick Hellstr�m wrote:
>I rather had some doubts about the proposal to extend the function to
>generate even longer PRG outputs, e.g. G'(k) = G(k1)|G(k2) where k1|k2 =
>G(k). I don't find it obvious that [...]
I never said it was obvious. It's a pretty marvelous result, in fact,
and it is the meat of the theorem. But while you're reading the proof
of it, you can see my other post for some partial intuition.
Note that to prove this, you don't need to know anything about the
structure of G (for instance, you can forget about the fact that it's
constructed using E). The above fact is true in general of all PRG's.
My advice is that if you want to understand this, reading the proof is
going to be the most effective way to do so. Really.
------------------------------
** 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
******************************
