Cryptography-Digest Digest #244, Volume #14 Fri, 27 Apr 01 00:13:00 EDT
Contents:
Running Time of Factoring Algorithms ("Jeffrey Walton")
Re: Running Time of Factoring Algorithms ("Tom St Denis")
Re: OTP WAS BROKEN!!! (16 bit ciphertext challenge) (Marc)
Re: Combining two plaintexts into ciphertext (Ken Savage)
Re: Censorship Threat at Information Hiding Workshop (Bryan Olson)
Re: There Is No Unbreakable Crypto ("Henrick Hellstr�m")
Re: Censorship Threat at Information Hiding Workshop (Terry Ritter)
Re: Combining two plaintexts into ciphertext (John Savard)
Re: impossible differentials ("Henrick Hellstr�m")
Re: Can this be done? (Benjamin Goldberg)
Re: RC4 Source Code (Bryan Olson)
Re: RC4 Source Code ("Tom St Denis")
Re: SHA PRNG (Tim Tyler)
Re: Running Time of Factoring Algorithms (Bryan Olson)
Re: SHA PRNG ("Tom St Denis")
Re: ANOTHER REASON WHY AES IS BAD (Tim Tyler)
Re: ANOTHER REASON WHY AES IS BAD (Tim Tyler)
----------------------------------------------------------------------------
Reply-To: "Jeffrey Walton" <[EMAIL PROTECTED]>
From: "Jeffrey Walton" <[EMAIL PROTECTED]>
Subject: Running Time of Factoring Algorithms
Date: Thu, 26 Apr 2001 22:18:29 -0400
Hello All,
The following question was posed during a cryptography class lecture.
If a factoring algorithm ran with the following upper bound, how would it
compare to the various methods that exist?
n = p * q
smallest of (p, q, p-q)
I apologize. I haven't taken an Algorithms class yet.
Jeff
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Running Time of Factoring Algorithms
Date: Fri, 27 Apr 2001 02:17:54 GMT
"Jeffrey Walton" <[EMAIL PROTECTED]> wrote in message
news:3ae8d667$0$[EMAIL PROTECTED]...
> Hello All,
>
> The following question was posed during a cryptography class lecture.
>
> If a factoring algorithm ran with the following upper bound, how would it
> compare to the various methods that exist?
>
> n = p * q
>
> smallest of (p, q, p-q)
>
> I apologize. I haven't taken an Algorithms class yet.
"Algorithms Class"?
Well I think Pollard-Rho works in the time you are talking about... Fermat
requires the |N^1/2 - q| time (q is the largest factor).
Things like NFS and QS are faster than your bound.
Tom
------------------------------
From: [EMAIL PROTECTED] (Marc)
Subject: Re: OTP WAS BROKEN!!! (16 bit ciphertext challenge)
Date: 26 Apr 2001 23:57:30 GMT
>OTP was broken!
>It is not a joke.
Then break this please, to demonstrate your approach:
0xb2 0x8f
It's an only 16 bit wide ciphertext, it should not allocate too
much of your precious time. I'll pay you 20 US dollars if you
succeed on the first attempt.
Good luck.
Marc.
------------------------------
From: Ken Savage <[EMAIL PROTECTED]>
Subject: Re: Combining two plaintexts into ciphertext
Date: Fri, 27 Apr 2001 02:27:51 GMT
Tom St Denis wrote:
> > > > Given:
> > > >
> > > > uint8 plain1, plain2;
> > > > uint8 key1, key2;
> > > > uint16 x;
> > > >
> > > > Is there a GOOD function f( x, key ) such that
> > > >
> > > > f( x, key1 ) == plain1
> > > > f( x, key2 ) == plain2
> > > >
> > > > and that f( x, anything_else ) is effectively a random uint8.
>
> I don't get this. If X is a combo of plain1 and plain2 then it must be a
> function of the two. The way you wrote it is backwards such that plain1 is
> a function of x and key1...
>
> You should write it as
>
> x = f(plain1, plain2, key1, key2).
There are two functions involved...
{
x = g( plain1, plain2, key1, key2 );
if( f( x, key1 ) == plain1 && f( x, key2 ) == plain2 )
success = true;
}
Ken
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: Thu, 26 Apr 2001 20:04:06 -0700
Terry Ritter wrote:
> Bryan Olson
> >"Donald L. Nash" wrote:
> >>
> >> Bill Unruh wrote:
> >>
> >> >It is not theft. Theft is depriving someone of some good.
>
> No, theft is commonly understood as simply taking without right or
> permission.
>
> >[...]
> >Can anyone cite where what is called "intellectual property
> >law" actually defines covered works as property, or
> >violations as theft?
>
> The dictionary first definitions:
So I guess that's a "no". I couldn't find such a definition
in law either.
> Theft -- the act or an instance of stealing
> Steal -- to take without right or permission
My dictionary's first definition:
Take -- to get by conquering; capture; seize
It's not the getting that's the crime; it's the subsequent
copying, or violation of some other exclusive right. That's
completely different from theft where the use is irrelevant.
So with both the dictionary and the law indicating that such
acts are "infringement" and not "theft", can we switch to the
proper word?
--Bryan
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: There Is No Unbreakable Crypto
Date: Fri, 27 Apr 2001 05:15:42 +0200
What if one branch of the binary tree is cut off at each step, i.e:
G(k) = G0(k)||G1(k), where G0(k) is direct output to the keystream and G1(k)
is feedback to the next step? Isn't this actually closer to the structure of
the "superstrong crypto", in the sense that you don't actually compute the
entire binary tree, but use each branch partly to encrypt/decrypt message
text, partly to compute the next key? (This is close to the basic structure
of PCFB-mode, anyway.)
As far as I understand the idea of length-doubling PRG, you have to compute
the entire tree in advance (or at least all N branches up to the first leave
for a message with N blocks) before you use any part of the keystream. Hence
you gain polynomial strength by performing a polynomial number of
computations. That's not really that counter-intuitive.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
"David Wagner" <[EMAIL PROTECTED]> skrev i meddelandet
news:9c9h42$4p0$[EMAIL PROTECTED]...
> Benjamin Goldberg wrote:
> >David Wagner wrote:
> >>
> >> Mok-Kong Shen wrote:
> >> >I continue to think, as said in another post, that this
> >> >means one can generate from, say, 128 random bits, a
> >> >secure bit string of infinite length, which seems to
> >> >be very counter-intuitive.
> >>
> >> Well, not infinite: only polynomial length, and only _if_
> >> you have a secure, length-doubling PRG. But yes, it's a
> >> marvelous, counter-intuitive, beautiful result.
> >
> >I don't suppose you could give a tiny demonstration, perhaps using an 8
> >bit key.
>
> No, because it's not secure with an 8 bit key. But with a 128 bit key...
>
> >What size is possible? You say, polynomial length... what kind of poly?
>
> polynomial in the security parameter. In other words, with
> a k-bit key and a PRG that is secure against all attacks that
> take poly(k) time, you can generate stretch the k-bit truly
> random key to poly(k) bits of pseudorandom keystream.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: Fri, 27 Apr 2001 03:21:26 GMT
On Thu, 26 Apr 2001 20:04:06 -0700, in
<[EMAIL PROTECTED]>, in sci.crypt Bryan Olson
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>> Bryan Olson
>> >"Donald L. Nash" wrote:
>> >>
>> >> Bill Unruh wrote:
>> >>
>> >> >It is not theft. Theft is depriving someone of some good.
>>
>> No, theft is commonly understood as simply taking without right or
>> permission.
>>
>> >[...]
>> >Can anyone cite where what is called "intellectual property
>> >law" actually defines covered works as property, or
>> >violations as theft?
>>
>> The dictionary first definitions:
>
>So I guess that's a "no". I couldn't find such a definition
>in law either.
Since when has sci.crypt become a courtroom?
Is sci.crypt more like a courtroom, or more like a classroom? And
when was the last time any of us saw an instructor retreat into
legalities to win a classroom point?
>> Theft -- the act or an instance of stealing
>> Steal -- to take without right or permission
>
>My dictionary's first definition:
>
> Take -- to get by conquering; capture; seize
>
>It's not the getting that's the crime; it's the subsequent
>copying, or violation of some other exclusive right. That's
>completely different from theft where the use is irrelevant.
>
>So with both the dictionary and the law indicating that such
>acts are "infringement" and not "theft", can we switch to the
>proper word?
The correct word is "theft."
"Theft" is a wholly appropriate common language term for the taking
without permission which constitutes copyright infringement under law.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Combining two plaintexts into ciphertext
Date: Fri, 27 Apr 2001 03:24:30 GMT
On Fri, 27 Apr 2001 00:12:49 GMT, Ken Savage <[EMAIL PROTECTED]>
wrote, in part:
>Given:
>uint8 plain1, plain2;
>uint8 key1, key2;
>uint16 x;
>Is there a GOOD function f( x, key ) such that
>f( x, key1 ) == plain1
>f( x, key2 ) == plain2
Well, one way to do that would be to encipher plain1 + plain2 by three
steps:
1) scramble the bits of plain1 and plain2 in order;
2) XOR them with a quantity;
3) perform a block cipher upon the 16 bit result.
Then, in deciphering, only the key of step 3 is the same for obtaining
both plain 1 and plain 2.
The key of step 2 can be anything, completely different for the two
plaintexts.
The key of step 1 would be complementary for the two plaintexts - and
the order of the eight bits for the other plaintext need not be
included in the key to recover one plaintext.
This would lead to no errors, but it wouldn't be quite as good as you
might like. Certainly, the method makes it obvious that there is room
for another plaintext in there, and knowing the key for one plaintext
leaves the other one very weakly enciphered.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: impossible differentials
Date: Fri, 27 Apr 2001 05:21:35 +0200
"Mike Rosing" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> > For example in
> >
> > outputdiff = F(x xor wrong_key) xor F(x xor wrong_key xor input_diff)
> >
> > Since F is not linear the "wrong_key" (which is the difference caused by
> > guessing the wrong key) does not commute and cancel out like it should
> > have...
> >
> > if F were linear than
> >
> > = F(x xor wrong_key) xor F(x xor wrong_key xor input_diff)
> > = F(x) xor F(x xor input_diff) xor wrong_key xor wrong_key
> > = F(x) xor F(x xor input_diff)
> >
> > Er is that right?
>
> Yup, the expectation that F is linear is what you're checking on.
> For a good cipher, F is not linear :-)
One might add that there is a good chance of finding a significant number of
impossible differentials in any random permutation. The existence of
impossible differentials is not per se a distinguisher for non-random
functions - only if they appear according to a suspicious pattern, as they
do if F is linear.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Can this be done?
Date: Fri, 27 Apr 2001 03:30:27 GMT
SCOTT19U.ZIP_GUY wrote:
>
> [EMAIL PROTECTED] (David Hopwood) wrote in
> <[EMAIL PROTECTED]>:
>
> >-----BEGIN PGP SIGNED MESSAGE-----
> >
> >Julian Morrison wrote:
> >> Alice sends messages to Bob. The messages are sent in clear, but
> >> Alice includes a "check hash" with each message that allows Bob to
> >> ascertain that (1) the message matches its hash, and (2) all the
> >> messages were generated by someone who knew some unspecified
> >> secret, said secret being provably the same for all the mesages.
> >>
> >> HOWEVER, Bob does not know this secret, he and Alice do not
> >> exchange any information (the flow of data is solely from Alice to
> >> Bob), nor can he nor anyone else listening in determine this
> >> secret. And, no-one without the secret can forge new hashes that
> >> falsely seem to have been created by Alice.
> >>
> >> The result being: all the messages are proven to come from the same
> >> place, despite that place remaining anonymous.
> >>
> >> Can this be done? If so, how?
> >
> >Yes. Alice generates a random key pair for a signature scheme, and
> >uses it to sign each message. Then she anonymously sends the
> >(message, signature, public_key) triples to Bob. Bob verifies each
> >message with the corresponding public key, and concludes that all the
> >valid messages that have the same public key, come from the same
> >source.
>
> All one could say is that all messages were created with same
> secret key. But the FBI putting a key log monitor in her PC could
> get her password and steal the key for themselves. So you really
> can't say for certain all the messages came from Alice.
And the TLN (Three Letter Name) could just as easily put a gun to
Alice's head and tell her to send the messages. So what? Remember that
"Alice" is anonymous. "She" is presumably sending everything via
anonymous remailers. How does the TLN know who "She" is, to find her
computer and put a logger on it or hold a gun to her head?
All the OP requires is to be able to prove that "all the messages were
generated by someone who knew some unspecified secret, said secret being
provably the same for all the mesages," and "no-one without the secret
can forge new hashes that falsely seem to have been created by
Alice."
Anyway, if the TLN somehow steals "Alice"'s secret, then the conditions
of the OP haven't been violated, and that's all we care about.
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: RC4 Source Code
Date: Thu, 26 Apr 2001 20:36:02 -0700
Tom St Denis wrote:
>
> "Dirk Mahoney" wrote
> > Can anyone point the way to RC4 source code written in C or C++?
Check out Crypto++
http://www.eskimo.com/~weidai/cryptlib.html
> Do you have a description of RC4 handy? If you can't implement it
> yourself you need some comp.sci classes.
I would recommend he look up the code. I remember one newbie who
posted multiple wrong RC4 implementations, while writing about
how easy it is to implement.
--Bryan
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: RC4 Source Code
Date: Fri, 27 Apr 2001 03:45:06 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
"Bryan Olson" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
> >
> > "Dirk Mahoney" wrote
>
> > > Can anyone point the way to RC4 source code written in C or
> > > C++?
>
> Check out Crypto++
> http://www.eskimo.com/~weidai/cryptlib.html
>
> > Do you have a description of RC4 handy? If you can't implement
> > it yourself you need some comp.sci classes.
>
> I would recommend he look up the code. I remember one newbie who
> posted multiple wrong RC4 implementations, while writing about
> how easy it is to implement.
Hmm I think that may be me... blush... Unfortunately I was also new
to C at the same time...
Tom
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>
Comment: Key at: http://tomstdenis.home.dhs.org/key.asc
iQA/AwUBOujrOAULrT+pXe8cEQKW5wCgn8rYhlsngxtUhFnFf8sR2UL35K0AoOha
A2qKY+XQn6yc+bqH7yrxYr5g
=6VO/
=====END PGP SIGNATURE=====
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: SHA PRNG
Reply-To: [EMAIL PROTECTED]
Date: Fri, 27 Apr 2001 03:40:32 GMT
Volker Hetzer <[EMAIL PROTECTED]> wrote:
: Peter Gutmann wrote:
[hash in counter mode?]
:> This PRNG isn't very good, see Bob Baldwin's analysis of the BSAFE 3.x
:> PRNG in an RSA labs bulletin dating from late 1998 (available from the
:> RSA labs web site) where he analyses this type of PRNG and explains
:> why BSAFE doesn't use it.
:
: The theory itself is good (after all it's a PRF used in counter mode
: and formally proven) but Bob didn't trust the hash functions available
: today (for good reasons).
Regardless of how good the hash is, such RNGs have no "forward secrecy" -
compromise of the state reveals all past and future outputs. This is not
always a desirable feature in a PRNG.
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Running Time of Factoring Algorithms
Date: Thu, 26 Apr 2001 20:51:36 -0700
Tom St Denis wrote:
>
> "Jeffrey Walton" wrote:
> > The following question was posed during a cryptography class lecture.
> >
> > If a factoring algorithm ran with the following upper bound, how would it
> > compare to the various methods that exist?
> >
> > n = p * q
> >
> > smallest of (p, q, p-q)
[...]
> Well I think Pollard-Rho works in the time you are talking about... Fermat
> requires the |N^1/2 - q| time (q is the largest factor).
Even trial division should run in time on the order of min(p, q).
Pollard is faster: order of about the square root of min(p, q).
(I'm neglecting a modest poly-logarithmic term in both.)
> Things like NFS and QS are faster than your bound.
Yup.
--Bryan
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: SHA PRNG
Date: Fri, 27 Apr 2001 03:56:34 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Volker Hetzer <[EMAIL PROTECTED]> wrote:
> : Peter Gutmann wrote:
>
> [hash in counter mode?]
>
> :> This PRNG isn't very good, see Bob Baldwin's analysis of the
> BSAFE 3.x :> PRNG in an RSA labs bulletin dating from late 1998
> (available from the :> RSA labs web site) where he analyses this
> type of PRNG and explains :> why BSAFE doesn't use it.
> :
> : The theory itself is good (after all it's a PRF used in counter
> mode : and formally proven) but Bob didn't trust the hash functions
> available : today (for good reasons).
>
> Regardless of how good the hash is, such RNGs have no "forward
> secrecy" - compromise of the state reveals all past and future
> outputs. This is not always a desirable feature in a PRNG.
The idea is to make the state large such that it cannot be
compromised. Also one should periodically re-seed the PRNG. If you
have a 256-bit seed in your PRNG it won't be guessed easily. The
most effective attack will be in forcing low entropy seed material
into it.
Tom
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>
Comment: Key at: http://tomstdenis.home.dhs.org/key.asc
iQA/AwUBOujt7gULrT+pXe8cEQI1mgCfYwGtmkEhMsGF5rfqEXAG64Zf4ucAnjDO
7jBpkJExGpQ5I+BaLr6dxCep
=utcr
=====END PGP SIGNATURE=====
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: ANOTHER REASON WHY AES IS BAD
Reply-To: [EMAIL PROTECTED]
Date: Fri, 27 Apr 2001 03:54:23 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
:> [EMAIL PROTECTED] (Darren New) wrote in <[EMAIL PROTECTED]>:
:> >SCOTT19U.ZIP_GUY wrote:
:> >> Actaully Tom as usually your quite wrong. If one looks at an OTP
:> >> you would have to think of the OTP data itself as part of the
:> >> encryption program or the program nesicessary to make the OTP sting.
:> >
:> >So why do you think that doesn't apply to the AES cyphers as well?
:>
:> Actaully I do think it should inculde the AES short keys of 256 bits.
:> Why do you think I mentioned scott19u and its key which is over a
:> million butes in length. [...]
: Why is a 256-bit key too short?
It's short compared to the OTP key or the scott19u key discussed.
"Too short" was not mentioned - except by you.
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: ANOTHER REASON WHY AES IS BAD
Reply-To: [EMAIL PROTECTED]
Date: Fri, 27 Apr 2001 04:01:39 GMT
[David Scott's small = weak proposal]
Small crypto is often simple crypto - and simple crypto is usually weak.
However, in the real world, cyphers need to work in confined spaces -
and we have seen that *fairly* small cyphers can be quite strong.
AES is quite small - but maybe it is large enough.
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
** 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
******************************
