Cryptography-Digest Digest #549, Volume #14 Thu, 7 Jun 01 11:13:00 EDT
Contents:
Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY)
Re: Best, Strongest Algorithm (gone from any reasonable topic)
([EMAIL PROTECTED])
Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and Large Primes
(Richard Wash)
Re: Best, Strongest Algorithm (gone from any reasonable topic)
([EMAIL PROTECTED])
Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and Large Primes
(Bob Silverman)
Re: Best, Strongest Algorithm (gone from any reasonable topic)
([EMAIL PROTECTED])
Re: MD5 for random number generation? (Phil Carmody)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Phil Carmody)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: MD5 for random number generation? (Tim Tyler)
Re: OTP WAS BROKEN!!! (Al)
Re: RSA's new Factoring Challenges: $200,000 prize. (Sergei Lewis)
Re: Brute-forcing RC4 ("Scott Fluhrer")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: 7 Jun 2001 13:26:33 GMT
[EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
snap...
>To see how a particular 8 bit cyphertext could map to more than 256
>different plaintexts, just get an 8 bit cyphertext, decrypt it with
>BICOM under a number of keys.
>
>You will see *many* different plaintexts come out - not just 256.
Mok likes to talk but getting him to actually do anthing
is quite impossible. He would rather say its impossible than
actually check it out. A lot like TOMMY. Sometimes I think
He and Tommy are not real people. Since if they were you would
think Wagner who at least pretends to know something about
crypto would set them straight. Why he does not bother to
make an honest useful comment on a thread like this makes
me wonder just how much he wants the average person to know
about crypto. He could help people like TOMMY on these concepts
but refuses any useful real help. WHY??
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
From: [EMAIL PROTECTED]
Date: 07 Jun 2001 09:44:55 -0400
Tim Tyler <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] wrote:
>: Tim Tyler <[EMAIL PROTECTED]> writes:
>:> Tom St Denis <[EMAIL PROTECTED]> wrote:
>:>: Or if you just pad the bloody thing to a multiple of say 64 bytes. [...]
>:>
>:> Still not enough for perfect secrecy :-(
>:
>: Right--no matter what ``a multiple'' means.
>
> That's correct - so long as no restraints are placed on the set of
> possible plaintexts.
Exactly. So why do you keep switching premises? Specifically:
1. When somebody says, ``OTP on padded messages gives (Tim Tyler's
definition of) perfect secrecy,'' you reply, ``No, because no
amount of padding is enough.'' In other words, you assume that the
space of plaintexts is infinite.
2. When somebody replies, ``Okay: if the space of messages is infinite,
then (your definition of) perfect secrecy is impossible to achieve.''
You reply, ``No, because the space of messages is actually finite.''
(Or alternately, ``...has cardinality 2 in my universe.'')
3. Of course, if the space of messages is finite, then padding your
plaintexts *is* enough to achieve (your definition of) perfect
secrecy...
It's impossible to draw any useful conclusions if you keep changing
your mind about the set of possible plaintexts: first it's infinite;
then it's finite; then there are only two possible messages; then it's
infinite again. Once you make up your mind, one of two things becomes
true (with your definition of ``perfect secrecy''):
a. Perfect secrecy is impossible.
OR
b. Perfect secrecy is achieved using OTP on padded messages.
You keep denying *BOTH* statements, because whenever somebody makes
one statement, you start by assuming whichever hypotheses contradict it.
Len.
--
We also believe candor benefits us as managers: the CEO who misleads
others in public may eventually mislead himself in private.
-- Warren Buffett, 1983
------------------------------
From: Richard Wash <[EMAIL PROTECTED]>
Subject: Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and Large
Primes
Date: 07 Jun 2001 09:46:23 -0400
"Tom St Denis" <[EMAIL PROTECTED]> writes:
> "Bob Silverman" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> news:<XRcT6.38998$[EMAIL PROTECTED]>...
> > Replying to "sisijojo":
> >
> > You need a certain minimal background and mathematical maturity
> > before tackling hard problems. You need experience in knowing
> > what works and what doesn't work. The idea that some naiive "kid"
> > will pop out of nowhere and solve a hard problem "BECAUSE HE HAS
> > NOT LEARNED THE WRONG APPROACH" is ludicrous.
>
> I don't see a big argument for this. Most "great" mathmetiticans
> were teens when they invented stuff. The prime number theorem was
> written by a 15 yr old.
>
> Thus I disproved your notion.
Unfortunately, this is wrong. Just because they "were teens" does not
mean that they did not have a minimal background and mathematical
maturity. Some people can achieve this maturity much quicker and at a
much earlier age than the average person. Thus, they can do
interesting and important work at an early age.
To point out the specific flaw in your argument, you are trying to
prove that a *naive* kid can solve hard problems, and no where in your
'proof' do you make the assertion that the kids you are talking about
are naive.
Personally, I agree that is does take a certain amount of mathematical
maturity to be able to really understand mathematics to significantly
contribute to the field. I also believe that it is possible for some
special kids to develop this maturity at a very early age.
Rick
------------------------------
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
From: [EMAIL PROTECTED]
Date: 07 Jun 2001 10:03:40 -0400
Tim Tyler <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] wrote:
>: Tim Tyler <[EMAIL PROTECTED]> writes:
>:
>:> ``...a finitely odd stream...is an infinitely long sequence of
>:> bits, but with the last 1 bit at a position finitely far from
>:> the beginning...''
>:
>: Complete red herring; in the material you posted, that ``infinite
>: sequence of 0s'' is not used for anything.
>
> Who are you to call it a "red herring"?
A mathematician who can read English. (Don't forget where the burden
of proof lies, BTW.)
Specifically, the definition of a ``finitely odd stream'' is completely
irrelevant, because everything from the final 1 on is discarded. It would
work equally well to define a ``finitely periodic stream'' as ``a stream
in which the first N bits are repeated infinitely'', and then perform the
next step on ``finitely periodic streams''.
Or perhaps a ``finitely-non-zebra stream'' which constitutes a stream
such that after finitely many bits, the stream represents a gif of a
zebra repeated indefinitely. In the obvious way, one throws away everything
that doesn't look like a zebra before encrypting.
Note further that you have no way of telling in finite time whether a
given stream is in fact a ``finitely odd stream''. You can't simply watch
for a sequence of zeros, because *my* ``finitely odd stream'' might have
terabytes of zeros all in a row...followed by that final 1.
The only way to be sure you've got a ``finitely odd stream'' is to
create it yourself, knowing that you've started with a finite-sized
input and then padded it with infinitely many zeros. (And if you hand
it to somebody who doesn't know the size of the input, then he can never
determine the size in finite time.)
> The day before yesterday you didn't even know what BICOM was.
Hmmm. Ain't literacy a powerful force? Read something and *BANG*! You
know what it says!
> So, what was it about "all bits are significant to the output" that you
> missed?
Nothing. What *you* missed is the fact that all but finitely many bits
are in fact completely irrelevant. They could be digits of PI for all it
matters. Or gifs of zebras.
Len.
--
Frugal Tip #52:
Beat up third graders for their lunch money.
------------------------------
From: [EMAIL PROTECTED] (Bob Silverman)
Subject: Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and Large
Primes
Date: 7 Jun 2001 07:05:52 -0700
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:<%ZwT6.45549$[EMAIL PROTECTED]>...
> "Bob Silverman" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> news:<XRcT6.38998$[EMAIL PROTECTED]>...
> > > "sisi jojo" <[EMAIL PROTECTED]> wrote in message
> > > news:[EMAIL PROTECTED]...
> > > > "Joseph Ashwood" <[EMAIL PROTECTED]> wrote in message
> news:<ebvtZ6S7AHA.201@cpmsnbbsa09>..
> > > >
> > > > I don't have much time to write long messages today. But here's my
> answer
> > > >
> > > > Maybe the approach is wrong. That's why nobody can solve it.
> > > >
> > > > You go through years of education to learn the wrong approach, which
> is
> > > > proven to be not useful. That's something funny about our education
> system.
> > > >
> > > > If you want a problem to be solved, show it to a kid and let him
> develop
> > > > an answer fresh from the beginning.
> >
> > Replying to "sisijojo":
> >
> > You need a certain minimal background and mathematical maturity before
> > tackling hard problems. You need experience in knowing what works and
> > what doesn't work. The idea that some naiive "kid" will pop out of nowhere
> > and solve a hard problem "BECAUSE HE HAS NOT LEARNED THE WRONG APPROACH"
> > is ludicrous.
>
> I don't see a big argument for this. Most "great" mathmetiticans were teens
> when they invented stuff. The prime number theorem was written by a 15 yr
> old.
Tom opens his mouth and shows his ignorance once more.
PNT was proved in the late 1800's by Hadamard and Vallee-Poussin. Neither
were teens.
And of course you can back up your assertion about "great mathematicians"?
I suggest you give some examples. While Gauss may have discovered a few
things while he was a teenager, this was very early in the history of modern
math. The math involved is considered somewhat elementary. Most of the
great mathematicians were born in the 20th century. Please cite examples
where stuff was invented by "teens". Can you even NAME 10 Fields Medalists??
Mathematics today is such that it requires a great deal of background to
understand it, let alone invent new stuff.
------------------------------
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
From: [EMAIL PROTECTED]
Date: 07 Jun 2001 10:07:00 -0400
[EMAIL PROTECTED] writes:
>
> Or perhaps a ``finitely-non-zebra stream'' which constitutes a stream
> such that after finitely many bits, the stream represents a gif of a
> zebra repeated indefinitely. In the obvious way, one throws away everything
> that doesn't look like a zebra before encrypting.
That should be, ``everything that looks like a zebra''. With the typo,
of course, the sentence explains how to carve a zebra.
--Len.
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: MD5 for random number generation?
Date: Thu, 07 Jun 2001 14:10:51 GMT
Toby Sharp wrote:
>
> I've heard of people using MD5 for random number generation. But, as far as
> I can tell, MD5 is a one-way hash algorithm. How is this used for random
> numbers? What is the input and output? Any guidance appreciated.
A first guess is that it is used to hash a selection of
not-on-their-own-particularly-random values together, and use that as a
seed for a more traditional generator? (e.g. Process ID, CPU tick count,
time, IP stack activity, detuned frame-grabber input.)
Phil
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 14:30:19 GMT
Tim Tyler wrote:
>
> Tim Tyler <[EMAIL PROTECTED]> wrote:
> : Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> : : From what you said, I don't think it is valid to consider
> : : that the constant length of messages underlies the
> : : proof of Shannon (unless one can demonstrate the
> : : contrary).
>
> : Without such an assumption, there's no proof of perfect secrecy,
> : because the system doesn't exhibit it.
>
> I looked up what Bruce Schneier has to say about perfect secrecy in
> A.C.
>
> He says this:
>
> ``There is such a thing as a cryptosystem that achives perfect secrecy:
> a cryptosystem in which the cyphertext tields no possible information
> about the plaintext (except possibly its length).''
>
> He goes on to give Shannon's theory that perfect secrecy is only possible
> if the number of possible keys in the cryptosystem is equal to the number
> of possible messages.
>
> IMO, Shannon has it right - while Bruce seems a bit uncertain about
> whether the length is included or not.
The length carries information. If you know that the enemy are either
going to retreat or send new troop-advancement commands, then an 8 byte
cyphertext _does_ tell you which of the two they're going to do.
> I suppose if Bruce isn't clear about the issue, that probably explains why
> other folk are not clear about it either.
>
> Certainly if you see a 1-byte cyphertext, you know that most possible
> plaintexts have a probability of zero.
>
> This means that an OTP that preserves length information does not conceal
> plaintext information as well as is possible to do. If anyone has been
> calling this is perfect secrecy, they really ought to consider the fact
> that systems which better hide the identity of the plaintext are available.
However, this not-perfect secrecy becomes closer to perfect again if the
length is not knowable. i.e. if the messages are padded in such a way
that 'all probable messages' have indestinguishable lengths. This of
course may not always be possible. However, one can reverse the
probabilities (usual entropy equation) to find out how many bits of
information have been leaked. (i.e. if every message is 1000 octets
long, the leak is 0 bits; if it's 50/50 for 1000bytes/2000bytes, then
the've leaked 1 bit.)
Phil
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Jun 2001 14:34:05 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: Since if they were you would think Wagner who at least pretends to know
: something about crypto would set them straight. Why he does not bother
: to make an honest useful comment on a thread like this makes
: me wonder just how much he wants the average person to know
: about crypto. He could help people like TOMMY on these concepts
: but refuses any useful real help. WHY??
Most of the time I'm on David Wagner's fan list. He has personally
set me straight or offered me assistance on a number of occasions.
I don't think you can take a lack of usenet posts as evidence of bad
character. Generally I'm happy that he visits sci.crypt at all.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: MD5 for random number generation?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Jun 2001 14:42:19 GMT
Toby Sharp wrote:
> I've heard of people using MD5 for random number generation. But, as far as
> I can tell, MD5 is a one-way hash algorithm. How is this used for random
> numbers? What is the input and output? Any guidance appreciated.
The RSAREF PRNG uses MD5, driven by a counter.
You can read about that in the paper you can download from:
http://www.counterpane.com/pseudorandom_number.html
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: [EMAIL PROTECTED] (Al)
Subject: Re: OTP WAS BROKEN!!!
Date: 7 Jun 2001 07:49:28 -0700
Hey newbie...
23490123489234934789945892348234234765784567234623784623784682346238462378468723
Which I'm sure you'll understand LOL
------------------------------
From: Sergei Lewis <[EMAIL PROTECTED]>
Subject: Re: RSA's new Factoring Challenges: $200,000 prize.
Date: Thu, 07 Jun 2001 15:58:26 +0100
Michael Brown wrote:
> I hadn't actually noticed this but that's probably because I'm substituting in
> a2=1, b2=0 quite early on due to laziness :)
Don't see how that leads to a general solution ^^;;
> > You can set one bit arbitrarily for exactly one of these, since you know
> > the two factors are different and exactly one bit is set; this on its
> > own doesn't help resolve all of them.
> Correct.
You can't, actually. This assumes equal length factors. If the factors
are not the same length in bits, the bits you haven't worked out yet
could be the same in both factors. You have to try the method for every
combination of factor lengths - there's 2logn of them.
> > Deductions of the form "bit x cannot be set in both factors because of
> > box y", "bit x must be set in both factors because of box y", and "bit x
> > must be set in neither factor because of box y" can be used to resolve
> > these, as Michael's page describes, but you need some really nasty hairy
> > logic to do this.
> Dead right. This is where I get stuck too :)
Quite doable, actually :)
Don't use 2-input 2-output stages. Use 3-input 2-output stages instead.
The truth table for three-bit addition is
in out
000 00
001 10
010 10
011 01
100 10
101 01
110 01
111 11
- that is, each five bits, and hence each entry in a long multiplication
table can only be one of 8 possible states.
Let each entry in the long multiplication table be the state of a
three-bit adder, with its inputs being the output of the adder above,
the carry of the adder to the right, and the appropriate bits of the two
factors multiplied together.
Keep track of which bits of state are unknown at any time. Start with no
bits known.
Form a long multiplication table, that is, a table of i x j states,
where i is your guess at the bitlength of one factor, and j is your
guess at the bitlength of the other factor, eg.
sss
sss
sss
Set the outputs along the bottom and right edges to be known, and to
equal the bits of your composite number.
let a be the factor represented by the rows of the multiplication table,
and b the factor that the nth row is multiplied by the nth bit of.
repeat
for every state s with unknown bits
find the set of all valid states consistent with the bits we do
know
(that is, that are present in the truth table,
and have no bits known in s differ from s)
you can deduce that every bit in those states that has the same
value
for all of them must also have that value for s
determine known bits of a by examining known bits of the states in the
rows
propagate known bits of a across all rows that have factor bits set,
since they
necessarily represent a known set bit of b
zero all rows that do not have bits set known to be set in a, since
they
necessarily represent a known bit of b which is not set
until the body of the loop produces no new previously unknown bits.
There are 2logn possible combinations of the two factor lengths this
must be repeated over until factors are found.
This method is equivalent to yours, since a three-bit adder can be built
using several of your two-bit adders.
This method does not work, since it produces arbitrarily many cases
where a state has an output carry of 0, an output of 1, and it cannot be
determined whether this output is from a previous carry, a previous
output, or the current bit of a. Trying every possible valid combination
of these states is no faster than trial divison :(:(:(
> I noticed that you were doing the deductions programatically. Your way's a lot
> clearer than using a lookup table, where the information is all hidden as to
> what is happening. However, the lookup table would be a lot faster (which
> doesn't really matter at the moment, though).
The one can be used to generate the other.
> > Hope all that helps someone ^^;; if I've misunderstood something,
> > Michael, please correct me ^-^
> This summarises the algorithm very well. Mind if I use it on the site as a
> summary page?
It's not a complete summary, nor does it work, as shown above :(
--
Sergei Lewis - http://members.tripod.co.uk/~Folken
"I'm not falling - this is how I fly.."
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Brute-forcing RC4
Date: Thu, 7 Jun 2001 07:51:01 -0700
Ichinin <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Hi.
>
> S Degen wrote:
> >
> > Howmuch time would it take to brute-force a 40 bit RC4 key? (Ofcourse
> > depending on the processor-speed, but lets say a PIII 500)
>
> Don't really know about a P3/500, but compare
>
> In my home lab i did a brute force estimate once on RC4
> (including all key setups and guessing).
>
> Using:
>
> 1 x P1/133 acting as a job server
> 1 x P2/266 - slave client
> 1 x AMD K6/350 - slave client
> 1 x P3/700 (Bus can be clocked to 117 Mhz; == ~819 Mhz)
>
> ..i estimated that with a C++ plugin for each slave
> client, i could brute force a 2^40 key in roughly 180
> days.
>
> The computing power could be compared to 2 to 2.5 P3/500,
> so, if my guess is correct, around 180 x 2 (or 2.5) days.
I haven't actually run any expirements, but that doesn't sound right to me.
An iteration of the RC4 key setup takes 7 operations by my count (counting
loads/stores/adds-mod-256 as one operation), and is somewhat parallizable.
It happens 256 times for each key, and then there are a few operations to
generate the first byte of keystream, test it, and then step to the next
key. All this (because of the parallizability) should be quite doable in
7*256 cycles or 3.5usec, and possibily half that. A complete keysearch
should then take 3.5 * 2^40 = 4 * 10^12 usec = 44 days, with the expected
time being half that.
Were you using any fancy C++ classes in the key setup? That'd get in the
way.
>
> >
> > This is the case:
> > You have a 128 bit (ASCII) text, and the encyphered version of it. This
> > version is encyphered with a 64 bit secret key, but of those 64 bits, 24
> > bits are known. (Leaving 40 unkown bits)
>
> Is this text always 128 bits? Are there fixed fields or headers in it?
> Then there are a more efficient attack.
>
> > I would like to know how long it would approximately take to calculate
> > the 40 bit secret key.
>
> Calculating the K and guessing (by brute force) are 2 separate things.
>
> > (Worst case scenario)
>
> Worst case scenario is bruteforce.
> >
> > Thank you if you can help me.
>
> NP.
>
> .Reg's,
> Ichinin
------------------------------
** 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
******************************
