Cryptography-Digest Digest #551, Volume #14 Thu, 7 Jun 01 13:13:01 EDT
Contents:
Re: Best, Strongest Algorithm (gone from any reasonable topic)
([EMAIL PROTECTED])
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
Re: Notion of perfect secrecy ("Paul Pires")
Re: Notion of perfect secrecy ([EMAIL PROTECTED])
Re: Notion of perfect secrecy (John Savard)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: Humor, "I Must be a Threat to National Security" (Douglas Hurst)
Re: shifts are slow? ("Tom St Denis")
Re: MD5 for random number generation? ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: OTP WAS BROKEN!!! ("Paul Pires")
Re: Humor, "I Must be a Threat to National Security" ("Chaotic")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
----------------------------------------------------------------------------
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
From: [EMAIL PROTECTED]
Date: 07 Jun 2001 12:19:24 -0400
Tim Tyler <[EMAIL PROTECTED]> writes:
>
> OK - so can you identify one bit in that stream which is *not*
> significant?
Everything after the final ``1''. Just read what he does with those
bits: he throws them out.
Len.
--
The Yanomamo Indians employ only three numbers: one, two, and more
than two. Maybe their time will come.
-- Warren Buffett, 1979
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 18:20:52 +0200
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
>
> :> Traffic analysis information is indeed often present -
> :> but we are talking about once a message exists, does
> :> the attacker gain anything by looking at the cyphertext.
> :>
> :> That's what the definition of "perfect secrecy" talks about.
> :>
> :> Perfect secrecy applies to encryption devices. Time of
> :> message transmission etc is considered to be outside its scope.
> :>
> :> A conventional OTP, [...] does not
> :> have Shannon's perfect secrecy property.
>
> : I am not of the opinion that size is 'inherently' different
> : from time etc. in the present context.
>
> Well, you should be. Length is a property that can be used to
> distingush between elements of the set of possible plaintexts -
> while time cannot be so used.
Why not? I could well agree with my partner that if
a mail (of any innocent content) is sent between 9 and
10 o'clock it means one thing while between 10 and 11
o'clock it means the opposite. At least one bit can
be transmitted that way. (More could be done by
more sophisticated agreement.)
M. K. Shen
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Notion of perfect secrecy
Date: Thu, 7 Jun 2001 09:22:11 -0700
Tim Tyler <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
>
> :> The OTP leaks information about the length of the plaintext.
> :>
> :> This is a clear security hazzard, and it may be necessary
> :> to take stops to prevent this information being used by the attacker.
> :>
> :> Also, it violates Shannon's perfect secrecy (which is what this
> :> thread is about).
> :>
> :> The OTP that is proven perfectly secure is in a system where only
> :> plaintexts of a given length are possibilities. That is not the
> :> OTP as commonly used.
>
> : By your logic the TIME you send the message leaks just as much information
> : as the LENGTH of the message.
>
> : Can BICOM go back in TIME to send the message?
>
> : Also WHO is sending the message leaks info too ...etc..
>
> Perfect secrecy is a property of a device that translates between
> plaintext and cyphertext.
>
> It asks what information about the plaintext is present in the cyphertext.
>
> Traffic analysis information is outside the scope of "perfect secrecy"
> as Shannon defined it.
>
> : Shannon was looking at the OTP in an abstract model where the a priori (what
> : exactly does that mean)... er... previous known distribution of messages
> : cannot be used to solve the system.
>
> I believe "a priori" translates roughly as "before knowledge", if that helps.
>
> This isn't about previous messages. Simple knowledge of the cyphertext
> and the machinery it was encrypted with is enough to reveal information
> about the plaintext. Previous messages have nothing to do with it.
>
> : Let's say you have a 13 byte OTP message where the plaintext was in ASCII.
> : Obviously you can rule out OTPs that would lead to non-ascii stuff. If you
> : know it's english you can eliminate OTPs that lead to non-english text. Out
> : of the possible 2^104 possible OTP pads only say 2^24 remain. But if you
> : have no other knowledge of the message your chance of success is now 1 /
> : 2^24.
>
> : How is that a weakness?
>
> If there are more than 2^24 possible plaintexts that might have been
> transmitted then this narrows things down.
>
> Perfect secrecy says that knowledge of the cyphertext must not allow the
> space of possible plaintexts to be narrowed down at all.
The space of the possible plaintexts hasn't been narrowed down
by the application of the OTP. This narrowing is a characteristic of the
message, not the method. By this logic no system could have perfect
secrecy since that would require the method to have control over the
composition of all possible messages before encryption. Nothing is
leaked that was not already plain. No compromise has occured by
the application of the OTP. It is perfect without the constraint you
are proposing.
This is one clear piece stable ground in a murky field. One thing you can
know. I don't see how this complex distinction you are proposing aids
in understanding or what it gets you from a practical sense. OTP's can
leak the message length. As Tom pointed out, they also can leak the point
in time, the relative sequence of messages, the sender and reciever.
These and other issues can be dealt with by protocol, seperate from OTP
if they are worrysome. Dealing with them (or not) does not modify
underlying proof of secrecy of the OTP.
Paul
> --
> __________
> |im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
Subject: Re: Notion of perfect secrecy
From: [EMAIL PROTECTED]
Date: 07 Jun 2001 12:36:28 -0400
"Paul Pires" <[EMAIL PROTECTED]> writes:
>
> I don't see how this complex distinction you are proposing aids in
> understanding or what it gets you from a practical sense. OTP's can
> leak the message length.
Note that the information is not useless. *IF* I know that the message
must be one of k known plaintexts, each having different lengths, then
I can use the length to deduce which plaintext is being sent.
Note further, however, that this properly belongs to traffic analysis:
I already knew what the message said; what I *didn't* know was who the
recipient was. So the information is in general useful when I'm most
interested in knowing the recipient--for example, which battalion is
receiving the ``retreat'' order, and which is receiving the ``advance''
order.
Len.
--
Frugal Tip #61:
Increase the equity of your home by installing a solid gold laundry sink
or building a backyard 'gator farm.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Notion of perfect secrecy
Date: Thu, 07 Jun 2001 16:38:04 GMT
On Thu, 07 Jun 2001 02:08:16 GMT, "Tom St Denis"
<[EMAIL PROTECTED]> wrote, in part:
>Typically what you guys are missing is that the length of the message is not
>the secret. It's the contents of the message.
>At any rate if the length is important just pad the message. Make the
>message fit to be a multiple of say 64 bytes or something.
Well, I'm quite in agreement that the problem with the length of the
message doesn't *disprove the OTP* or anything like that.
However, it might actually be a difficult question to determine 'is
the length important' in a particular case. So it isn't impossible
that an OTP user might carelessly give important information away by
forgetting about that point.
Note, though, that this has *nothing* to do with compression
algorithms, since one assumes the adversary knows what compressor is
used. I think that's the point you were making - and that is right.
John Savard
http://home.ecn.ab.ca/~jsavard/frhome.htm
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Jun 2001 16:31:15 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
:>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 [...]
:>
:>IMO, Shannon has it right - while Bruce seems a bit uncertain about
:>whether the length is included or not.
: No wonder people are confused. Shannon was an expert and then
: Mr BS comes along and do to his lack of knowledge. [...]
Yes, that appears to have been more-or-less what has happened.
Shannon got it right - but it looks like his proof didn't prove what those
who came after him thought it had proved.
It seems that he proved that a Vernam cypher (e.g. a OTP) had perfect
secrecy when it was used to encrypt infinite streams.
This is a bit different from the "normal" use of an OTP.
Now people talk about the ordinary OTP as though it is what Shannon proved
had perfect secrecy.
We get Bruce Schneier saying:
``Believe it or not, there is a perfect encryption scheme. It's called a
one-time pad [...]'' A.C. p.15
He goes on to describe the ordinary OTP before saying:
``this scheme is perfectly secure''.
I expect Shannon would not have approved of this usage of the word "perfect".
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Douglas Hurst <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc
Subject: Re: Humor, "I Must be a Threat to National Security"
Date: 7 Jun 2001 16:37:14 GMT
Did everyone else on this thread fail to notice the HUMOR opening??
In sci.crypt David G. Boney <[EMAIL PROTECTED]> wrote:
> My frustrations with trying to find a job in government service are summarized in an
>essay I have posted that is titled, "I Must be a Threat to National Security". I have
>also placed my rejection letters from the CIA and NSA on-line.
> http://www.seas.gwu.edu/~dboney/security.html
> If anyone knows of any computer or network security engineer positions open,
>developer or administrator, in the Washington, DC area, that are commercial,
>non-government, non-government contractor, and don't require a clearance, please drop
>me a line. You can surf my home page to get a picture of my qualifications. Resume
>available upon request.
> --
> Sincerely,
> David G. Boney
> mailto:[EMAIL PROTECTED]
> http://www.seas.gwu.edu/~dboney
--
Douglas Hurst
3rd Year Comp Sci hopeful
U of A
"I re-coded that.Didn't I send you the new one?"
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: shifts are slow?
Date: Thu, 07 Jun 2001 16:45:05 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
> :> : "Joseph Ashwood" <[EMAIL PROTECTED]> wrote in message
>
> :> :> In order to shift by X takes X clocks.
> :>
> :> : This is so wrong. I can shift a 512-bit register 211 bits in one
cycle.
> :> : (Just re-wire the outputs).
> :>
> :> You're talking about rewiring a P4?
> :>
> :> Are you going to do this while it's running? ;-)
>
> : You're kidding right?
>
> Thus the smiley - but you *did* seem to be suggesting rewiring a P4 -
> not a terribly practical task regardless of whether it is running or not.
I meant in hardware typically logical shifts can be done via re-wiring the
inputs and outputs.
I dunno how the Athlon does it but they get rotates and shifts at a rate of
1/2 which is good enough for me :-)
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: MD5 for random number generation?
Date: Thu, 07 Jun 2001 16:48:38 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> 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
Yeah, you have to make sure though, that your PRNG is forward and backwards
safe.
I.e if the output is X X A Y B X X ...
And you know Y, you shouldn't find B or A with any advantage over the size
of the blocks.
This can be done via
H[i] = HASH(H[i - 1] || SEED || i)
Where SEED is your initial private seed, i is the counter. You can mix in
H[i - 1] to get a bit more bits mangled, but in theory you don't have todo
that. So you could just use
H[i] = HASH(SEED || i)
Which is essentially a CTR mode of operation.
Of course SEED should be at least 256 bits, and you should throw away the
SEED every so often. I would as a matter of security re-seed SEED each time
you make a new key. For example with RSA you may need 10kbits of PRNG data
but before you make the first bit you should reset the PRNG.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 16:53:17 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> :> OTP processing gives the opponent information about the length of the
> :> plaintext.
> :>
> :> Before he looked at the cyphertext, he did not have this information.
> :>
> :> That violates Shannon's perfect secrecy.
>
> : Any more information about the plaintext. The length does not reveal
the
> : plaintext.
>
> ...but it /does/ reveal some information about its identity.
>
> : By your argument [other systems] can't possibly be secure now because I
> : know that you sent a message at 7:15am.
>
> That doesn't violate the definition of perfect secrecy.
>
> Perfect secrecy is considered to be a property of a cryptosystem - i.e.
> a device for translating between plaintexts and cyphertexts.
>
> The time of message transmission is outside the scope of the definition.
I don't think you can have it both ways.
For example, the timing of the messages may be more important. Let's say I
want to find out when Hacker-Bob is breaking into an account. I don't care
about the data, I just want to know when.
In this case "perfect secrecy" is lost.
Shannon was talking from an information theoretic standpoint. Not some
esoteric view. If you have M possible messages and the prob of any one
message being the correct one is 1/M, then shannon (and any finite student)
would conclude you have perfect secrecy from a math related attack.
Think of M as a dice. M=6. Now you know there are 6 possible faces but you
don't know better than 1/6 which will turn up. Now let's say you add the
face of the dice modulo 6 to a message (which is broken into parts modulo 6
for some reason). Since you can't guess which face will turn up better than
1/6 you can't guess which original message was the real one better than 1/6.
That is to correctly solve for the message you need to solve two unknowns
from one known, which is clearly impossible.
Let's suppose M=2, i.e a coin toss ....
So I think you guys have to move onto some communication related security
not information theoretic.
Tom
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Thu, 7 Jun 2001 09:40:19 -0700
Al <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Hey newbie...
>
> 23490123489234934789945892348234234765784567234623784623784682346238462378468723
(234) (90) (1234) (89) (234) (9) (34) (789)
(9) (45) (89) (234) (8) (234) (234) (765) (78)
(4567) (234) (6) (23) (78) (4)(6) (237) (8) (4)
(6) (8) (234) (6) (23) (8) (4) (6) (23) (78) (4) (687) (23)
>
> Which I'm sure you'll understand LOL
I understand that you banged two hands (not just one) on the number
strip above the keys and not the num pad, avoided the tilda
key (very few 1's) and didn't try real hard to be pseudo-random.
Next time, just let the cat walk on the keyboard.
Paul
------------------------------
From: "Chaotic" <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc
Subject: Re: Humor, "I Must be a Threat to National Security"
Date: Thu, 07 Jun 2001 16:53:28 GMT
No I saw it, and I thought the same thing no one seemed to see the humour
bit.
Chaotic.
Douglas Hurst <[EMAIL PROTECTED]> wrote in message
news:9foajq$d9i$[EMAIL PROTECTED]...
> Did everyone else on this thread fail to notice the HUMOR opening??
>
> In sci.crypt David G. Boney <[EMAIL PROTECTED]> wrote:
> > My frustrations with trying to find a job in government service are
summarized in an essay I have posted that is titled, "I Must be a Threat to
National Security". I have also placed my rejection letters from the CIA and
NSA on-line.
>
> > http://www.seas.gwu.edu/~dboney/security.html
>
> > If anyone knows of any computer or network security engineer positions
open, developer or administrator, in the Washington, DC area, that are
commercial, non-government, non-government contractor, and don't require a
clearance, please drop me a line. You can surf my home page to get a picture
of my qualifications. Resume available upon request.
>
>
> > --
> > Sincerely,
> > David G. Boney
> > mailto:[EMAIL PROTECTED]
> > http://www.seas.gwu.edu/~dboney
>
>
>
>
> --
> Douglas Hurst
> 3rd Year Comp Sci hopeful
> U of A
> "I re-coded that.Didn't I send you the new one?"
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 16:57:41 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> :> JPeschel <[EMAIL PROTECTED]> wrote:
>
> :> "perfect secrecy is defined by requiring of a system after a
> :> cyptogram is intercepted by the enemy the a posteriori probabilites
> :> of this cryptogram representing various messages be identaically the
> :> same as the a priori probabilites of the same message before the
> :> interception."
> :>
> :> If the length of the plaintext is revealed by the cyphertext, this
> :> condition does not hold.
>
> : How? [...]
>
> It is obvious how the length of the plaintext is revealed by the
> cyphertext.
>
> The length of the plaintext is the same as the length of the cyphertext.
How does the length give you information about the message outside of the
length? You don't know the CONTENTS of the message.
> : If you have an 8-bit ciphertext all 256 plaintexts are equally
> : probable. That follows this distribution.
>
> I am not considering a system with only 256 possible plaintexts.
> That's a toy system, with no practical use.
I disagree. RC4 only has 256 possible plaintexts and it's not a TOY cipher.
> : You're idea of security only works if your cipher can produce infinite
> : length ciphertexts.
>
> Not so. Finite plaintexts can produce perfect secrecy.
Not so. According to you the length must be unbounded (i.e unknown) for
perfect security. If the length of the ciphertext were not from
0...infinity, then the length must be known. Just because #plaintext !=
#ciphertext doesn't mean you don't know the length.
For example, only so many 1-byte plaintexts will map to a 3-byte ciphertext
under BICOM. This means if I get a 3-byte ciphertext I know it's length
must be 1,x,y,z ... [some finite #]...,w [end of list]. If this is the case
then I know the length must be within some bound.
If I cannot know the length of the plaintext then the length must be within
0,1...oo
Thus, you must be prepared to send infinite length ciphertexts.
> : (of course your idea of security is vastly flawed)
>
> How so, pray tell?
>
> : I would hate to use 1.7 x 10^55 bytes of ram to send a 10 byte message
> : home....
>
> No - that is not correct. You could send a 10 byte message home while
> retaining prefect secrecty - assuming a genuinely random shared key was
> available.
Hence OTP.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 17:04:13 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (Tom St Denis) wrote in
> <Z2IT6.49208$[EMAIL PROTECTED]>:
> >
> >No perfect secrecy is defined as having no ability to tell one plaintext
> >from another. Who cares if you know the entire set of plaintexts (hint
> >you will always know the set), you won't know which is the right one.
>
> No perfect secrecy is dedined for a closed system where any possible
> encrypted message recieved can map back to all possible input messages.
> if you have as part of the input set messages of various lengths,
> That you apply a one time pad to and send. If I get a short cipher
> text. And its assumed I know all about your method and the set of
> possible input messages. Then you have told me its not the longer
> message. Its actually quite clear.
If you're so bloody smart solve this system.
55 = P + K mod 256
What is P and K?
That's what we are talking about. P is the message and K is the key. If
you can't solve for P (which I know you can't) then I have obtained perfect
secrecy since no matter how much work you put on it you can't uniquely solve
for P.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 17:08:57 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
> : [EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
>
> :>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 [...]
> :>
> :>IMO, Shannon has it right - while Bruce seems a bit uncertain about
> :>whether the length is included or not.
>
> : No wonder people are confused. Shannon was an expert and then
> : Mr BS comes along and do to his lack of knowledge. [...]
>
> Yes, that appears to have been more-or-less what has happened.
How dare you two say this. These people you so easily belittle are actual
cryptographers. Just because you're too slow, ignorant and mean to figure
out things when people repeatedly try to set you straight doesn't mean
others are as stupid as you are.
You're notions of "what is right" are so off base it's almost sad. I bet
if you guys ever got a job as a network security type you would get fired
within 3 minutes after proposing vastly inefficient and hoky-poky systems.
You have no proof that BICOM (or scottu, or...) are any better than anything
else proposed thus far. In fact it has been shown that something like CTR
with a decent underlying block cipher is vastly more efficient and has more
features than BICOM.
Take my words for what you won't, but you're not winning any popularity
contests. Most people just reply to you because we're bored and like to
pick fights. (Let's off steam). The real pros (Like Wagner, whom you
belittle as well) have real jobs doing real work and don't care much for
your lame-ass poke-fun at-all attitude.
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
******************************
