Cryptography-Digest Digest #150, Volume #14 Sun, 15 Apr 01 11:13:01 EDT
Contents:
Re: Remark on multiplication mod 2^n ("Tom St Denis")
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: LFSR Security ("Trevor L. Jackson, III")
Re: Note on combining PRNGs with the method of Wichmann and Hill ("Tom St Denis")
Re: Remark on multiplication mod 2^n (Mok-Kong Shen)
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: Note on combining PRNGs with the method of Wichmann and Hill ("Tom St Denis")
Re: Announcing A New Rijndael Encryption Algorithm Implementation (Kent Briggs)
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: Announcing A New Rijndael Encryption Algorithm Implementation ("Tom St Denis")
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: LFSR Security ("Trevor L. Jackson, III")
Re: Note on combining PRNGs with the method of Wichmann and Hill ("Tom St Denis")
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: Note on combining PRNGs with the method of Wichmann and Hill ("Tom St Denis")
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Remark on multiplication mod 2^n
Date: Sun, 15 Apr 2001 14:13:06 GMT
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
> >
> > "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> > >
> > >
> > > Tom St Denis wrote:
> > > >
> > > > "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> > >
> > > > > You seemed to have ignored my word 'simplicity' and
> > > > > no intention of 'perfection'. What if W is 32 or 64?
> > > >
> > > > W can be anything. And GF mults are simple (albeit not super fast).
In
> > my
> > > > "yet to be submited for SAC" cipher design I use GF mults
> > extensively....
> > > > :-)
> > >
> > > Certainly W can be anything. But compare the computing
> > > effort. A Mercedes is better than a small Austin,
> > > but you have also to pay more.
> >
> > A W-bit GF mult takes W loops thru a small function... where there are W
> > xors, shifts and "and" operations.
> >
> > The result is certainly much better than mults in Z mod 2^W ...
>
> Didn't I wrote the word 'better'??
Oh yeah I forgot you strive for bad designs.... sorry for trying to be
helpful.
Tom
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Sun, 15 Apr 2001 16:11:11 +0200
Tom St Denis wrote:
>
> "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> >
> > Tom St Denis wrote:
> > >
> >
> > > One could idea is to think of 0..1 as 0..65535 (i.e fixed point of 0.16)
> > > It's mathmatically similar and provides reasonably more efficient study.
> > > In this case you see that you don't perform (prng)/(2^w) to get 0..1 you
> > > just take the output directly (note the attacker could just mult your
> value
> > > by 2^w to get the real values.)
> >
> > PRNGs in numerics are commonly standardized to [0, 1),
> > even they are at the base generating integers. And
> > in the general (for crypto more interesting) cases,
> > they have different integer ranges.
>
> My point was that conceptually they are the same but without going to
> decimals is easier to cryptanalyze (mainly just faster). It's like say
> "1+1+1+1+1" instead of just "5". The result is conceptually the same (and
> this case numerically) but the method is diff. Bydoing
>
> a/b, it's the same thing (if you are analyzing a) as ab/b = a since in this
> case 'b' is known and fixed it doesn't skew the prng bias much if any at all
If a PRNG is based on integer relations, one does the
division as you said in order to get the output in [0, 1).
This is a known and trivial fact. Thus they are 'inherently'
the same thing. What is your point in the context of
the present thread? (Anything new you want to express?)
M. K. Shen
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 14:18:00 GMT
David Wagner wrote:
> Trevor L. Jackson, III wrote:
> >It appears to me that the unknown irregular samples and unknown taps (and
> >unknown initial state) is hopeless for reasons already mentioned.
>
> I haven't see any evidence either way
> (short of "well, I can't see how to do it" -- which isn't very convincing).
There is more to it that that. Consider the collections of unknowns: the taps,
the gap positions, the gap values, and the initial state. We don't even know N.
So, any non-degenerate LFSR can be sampled to match any desired output (set of
sample posistions and values). Given a desired output the simplest LFSR that
produces it will always have two bits, one tap (!), and an initial state with a
zero and a one. Note that this trivial result is also reasonably efficient in
that it requires no long gaps. On average we'd expect to sample 2/3rds of the
underlying bitstream. Worst case we'd sample half of it.
The problem is so underdetermined that the trivial case always works.
Only when some other constraint is imposed do we need to consider nontrivial
constructs.
Now when N is known but the taps and initial state are not, the system is still
so underdetermined that almost any configuration with at least one tap and and
initial state with at least one '1' and one '0' can be sampled to produce the
desired output. So the simplest system has one tap and a single '1' bit in the
initial value.
If the initial state is known (which also gives N) but the taps are not known
the system is still so loose that only a few cases are necessary to produce any
possible output. But there is some room for interpretation of the concept of
simplest generator. I assume it means the shortest register with the least
number of taps rather than the register that produces the densest sampling.
So, if the initial state is not all ones then the simplest configuration has one
tap and the system is an N-bit version of the completely underdetermine case.
If the initial state is all ones then the problems gets mildy interesting. If
the desired sample sequence is all ones the trivial one-tap system is enough.
If the sample sequence is all zeros then two taps at the output of the register
suffice to produce a degenerate cycle of all zeros. If the sample sequence is
not uniform the number of taps must be odd, so three suffice.
Since known taps and known initial state makes the sampling instantly obvious,
only known taps with unknown initial state and gaps make a hard problem.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Sun, 15 Apr 2001 14:24:10 GMT
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
> >
> > "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> > >
> > > Tom St Denis wrote:
> > > >
> > >
> > > > One could idea is to think of 0..1 as 0..65535 (i.e fixed point of
0.16)
> > > > It's mathmatically similar and provides reasonably more efficient
study.
> > > > In this case you see that you don't perform (prng)/(2^w) to get 0..1
you
> > > > just take the output directly (note the attacker could just mult
your
> > value
> > > > by 2^w to get the real values.)
> > >
> > > PRNGs in numerics are commonly standardized to [0, 1),
> > > even they are at the base generating integers. And
> > > in the general (for crypto more interesting) cases,
> > > they have different integer ranges.
> >
> > My point was that conceptually they are the same but without going to
> > decimals is easier to cryptanalyze (mainly just faster). It's like say
> > "1+1+1+1+1" instead of just "5". The result is conceptually the same
(and
> > this case numerically) but the method is diff. Bydoing
> >
> > a/b, it's the same thing (if you are analyzing a) as ab/b = a since in
this
> > case 'b' is known and fixed it doesn't skew the prng bias much if any at
all
>
> If a PRNG is based on integer relations, one does the
> division as you said in order to get the output in [0, 1).
> This is a known and trivial fact. Thus they are 'inherently'
> the same thing. What is your point in the context of
> the present thread? (Anything new you want to express?)
My point was that for analysis you could leave the prng output in Z instead
of R to simplify the task. I am speaking from a practical sense. Floating
point numbers loose precision over use which is not ideal for an attack.
And generally if all you're doing is something like a/65536(for example) to
get a floating point value then you can mult the float by 2^16 to get back
to Z.
It's nothing "new"....IMHO.
Tom
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Remark on multiplication mod 2^n
Date: Sun, 15 Apr 2001 16:25:48 +0200
Tom St Denis wrote:
>
> "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> >
> > Tom St Denis wrote:
> > >
> > > "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> > > >
> > > >
> > > > Tom St Denis wrote:
> > > > >
> > > > > "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote:
> > > >
> > > > > > You seemed to have ignored my word 'simplicity' and
> > > > > > no intention of 'perfection'. What if W is 32 or 64?
> > > > >
> > > > > W can be anything. And GF mults are simple (albeit not super fast).
> In
> > > my
> > > > > "yet to be submited for SAC" cipher design I use GF mults
> > > extensively....
> > > > > :-)
> > > >
> > > > Certainly W can be anything. But compare the computing
> > > > effort. A Mercedes is better than a small Austin,
> > > > but you have also to pay more.
> > >
> > > A W-bit GF mult takes W loops thru a small function... where there are W
> > > xors, shifts and "and" operations.
> > >
> > > The result is certainly much better than mults in Z mod 2^W ...
> >
> > Didn't I wrote the word 'better'??
>
> Oh yeah I forgot you strive for bad designs.... sorry for trying to be
> helpful.
There is a saying that the world is all nails if one is
a hammer. I was not considering the case where one is
minutely doing the work of designing a specific part of a
cipher, but the commonly encountered case where one has
two streams of words (say 32 bits) and want to get a new
stream rather simply and cheaply. Whether the trade-off
is fine, depends on the situations at hand. And I am not
doing the multiplication in Z_2^n as you said above, but
I modified it to get another value as the result, as stated
in (and is the content of) the original post.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Sun, 15 Apr 2001 16:27:16 +0200
Tom St Denis wrote:
>
[snip]
>
> It's nothing "new"....IMHO.
Then why your posts?
M. K. Shen
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Sun, 15 Apr 2001 14:32:48 GMT
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
> >
> [snip]
> >
> > It's nothing "new"....IMHO.
>
> Then why your posts?
Well I am just making a suggestion.
DOWN WITH THE NSA. UP WITH COMUNISM (with the bad spulling!) PhReAkErS
RuLeZ!!!!!!
There is that more of your liking?
For geez sake. You try to be helpful and your hit in the head over and
over... wow....
Tom
------------------------------
From: Kent Briggs <[EMAIL PROTECTED]>
Subject: Re: Announcing A New Rijndael Encryption Algorithm Implementation
Date: Sun, 15 Apr 2001 09:34:53 -0500
bloopa wrote:
> What makes VSpace Encrypted Chat so secure?
> Under the United States Federal Regulations concerning domestic encryption,
> all cipher systems intended for public use must be inspected and approved by a
> government agency. These systems must also have a documented back door so that
> law enforcement will be able to break the cipher.
Exportable crypto software does require a one-time review but the "back door"
comment is totally false.
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Sun, 15 Apr 2001 16:31:53 +0200
Mok-Kong Shen wrote:
>
> Tom St Denis wrote:
> >
> [snip]
> >
> > It's nothing "new"....IMHO.
>
> Then why your posts?
Addendum: One trouble with directly using the integers is
that, as I said, these have (in the general case) different
ranges for the different PRNGs. The standardization
simplifies matters.
M. K. Shen
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Announcing A New Rijndael Encryption Algorithm Implementation
Date: Sun, 15 Apr 2001 14:38:25 GMT
"Eric Lee Green" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Sun, 15 Apr 2001 03:06:15 GMT, bloopa <[EMAIL PROTECTED]> wrote:
> >VSpace Encrypted Chat
>
> Yawn. After seeing the various disclaimers about export I could care
> less. It's permissible to export virtually anything from the United
> States nowdays -- my own employer exports 128-bit Rijndael and the
> export license was granted virtually instantaneously (and I will
> personally state, as the author of most of the cryptographic
> components in that piece of software, that there are no back doors and
> that if we were contacted by the NSA to put one in, I certainly never
> heard about it). Anybody who says you can't export their crypto
> product is either lazy, or, well, incompetent. Either way...
>
> (Oh darn, here I go again, next thing you know these people will have
> me on THEIR enemies list too, why can't I keep my mouth shut when
> I see silliness? :-).
Tisk tisk... they put the back door in when you went for a coffee break...
you know like in the movies... all I have todo is hit three keys and wham I
hacked into the DNDOSPQATR (add letters if the movie is getting short...).
DOWN WITH THE TRUTH, UP WITH INSANITY.
Madness takes its toll, please have exact change... etc...
Tom
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Sun, 15 Apr 2001 16:38:25 +0200
Tom St Denis wrote:
>
> DOWN WITH THE NSA. UP WITH COMUNISM (with the bad spulling!) PhReAkErS
> RuLeZ!!!!!!
>
> There is that more of your liking?
>
> For geez sake. You try to be helpful and your hit in the head over and
> over... wow....
Please put stuffs not relevant to discussion, in case
you want to post them, in the the 'signature' part,
I mean after your name.
M. K. Shen
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 14:45:00 GMT
David Wagner wrote:
> Trevor L. Jackson, III wrote:
> >It appears to me that the unknown irregular samples and unknown taps (and
> >unknown initial state) is hopeless for reasons already mentioned.
>
> I haven't see any evidence either way
> (short of "well, I can't see how to do it" -- which isn't very convincing).
>
> >However,
> >the unknown irregular samples together with known taps (and unknown initial
> >state) may be interesting.
>
> As I mentioned in a previous post, there are interesting tricks for
> handling this case. For a simple version, let f(Z,L) be 1 if you can
> delete some positions in L to get Z, and 0 otherwise. Note that this
> function can be computed efficiently using dynamic programming. Also,
> if Z be the observed keystream and L is the undecimated LFSR sequence,
> then f(Z,L) = 1, whereas for a random sequence L we expect f(Z,L) = 0.
> Suppose we have a cipher where LFSR1 produces L and LFSR2 produces the
> clocking bits. Then you can guess the initial fill of LFSR1 and test
> your guess by computing f(Z,L) without needing to guess LFSR2's initial
> fill. Consequently, this attack is exponential in the size of the
> LFSR1, but much faster than brute-force search. Isn't that clever?
Yes, the embedding predicate is useful, but in this construct it relies up the
defined configuration of LFSR2. So this can generate a smaller subset of
LFSR1's output than an arbitrary sampling. We only have 2^(N1+N2) possible
subsets of LFSR1's output sequence. The technique reduces the search space to
2^N1, but we seem to need a reduction from an arbitrarily large space.
The only interesting bounds on the sampling I can think of would be to limit the
known samples to a single period of the generator or some polynomial function of
N, say N^2.
>
>
> (The above idea can---I think---be extended to handle the case where
> you just have a correlation between Z and a decimated version of L.
> However, I don't know if there are extensions that work in polynomial
> time, even for the above simple case.
It seems like there ought to be a way to spend some memory to reduce the
exponentiality. An elegant encoding might support some ruthless pruning of the
search tree. Given a leading sequence of known bits, an arbitrary gap and the
value of the following bit there should be a minimization of the gap length that
indicates the required the initial value. A kind of greedy algorithm.
> I'm not expert on stream ciphers.)
Hah! Far be it from me to denigrate your undue modesty, but I'm just an
engineer, not a crypto expert at all.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Sun, 15 Apr 2001 14:46:58 GMT
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
> >
>
> > DOWN WITH THE NSA. UP WITH COMUNISM (with the bad spulling!) PhReAkErS
> > RuLeZ!!!!!!
> >
> > There is that more of your liking?
> >
> > For geez sake. You try to be helpful and your hit in the head over and
> > over... wow....
>
> Please put stuffs not relevant to discussion, in case
> you want to post them, in the the 'signature' part,
> I mean after your name.
Ok you can't even tell when someone is being sarcastic....
*PLUM*
Tom
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Sun, 15 Apr 2001 16:58:56 +0200
Tom St Denis wrote:
>
> Ok you can't even tell when someone is being sarcastic....
>
> *PLUM*
We have discussed in another thread about desirability
of being serious in posts to this group. Not everyone has
the IQ needed to detect different forms of sacarcism
or other similar stuffs and foreigners of English
may have more difficulties in that. Others may not have
the time to do so. To avoid misunderstandings etc. it
is highly desirable in my view to keep to the proper
discussions. Please kindly re-read my follow-up in the
thread 'I got accepted' of sci.crypt of Fri, 13 Apr 2001
10:56:40 +0200.
M. K. Shen
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Sun, 15 Apr 2001 15:08:45 GMT
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
> >
>
> > Ok you can't even tell when someone is being sarcastic....
> >
> > *PLUM*
>
> We have discussed in another thread about desirability
> of being serious in posts to this group. Not everyone has
> the IQ needed to detect different forms of sacarcism
> or other similar stuffs and foreigners of English
> may have more difficulties in that. Others may not have
> the time to do so. To avoid misunderstandings etc. it
> is highly desirable in my view to keep to the proper
> discussions. Please kindly re-read my follow-up in the
> thread 'I got accepted' of sci.crypt of Fri, 13 Apr 2001
> 10:56:40 +0200.
I don't have that message any more but I appreciate the "serious"ness
desired. But it has to work both ways (well multi-ways when you consider we
are not the only users...). If I (or anyone else) posts a serious question
they deserve a serious reply, not some quable over penis sizes.... seriously
that's all this thread is good for sometimes...
Tom
------------------------------
** 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
******************************
