Cryptography-Digest Digest #543, Volume #14 Wed, 6 Jun 01 22:13:00 EDT
Contents:
Re: How good is steganography in the real world? ([EMAIL PROTECTED])
DES not a group proof (Patrick Aland)
Re: Quantum Computers with relation to factoring and BBS ("rosi")
Re: Knapsack security??? Ah....huh ("rosi")
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY)
Notion of perfect secrecy ("Tom St Denis")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.security.misc,talk.politics.crypto
Subject: Re: How good is steganography in the real world?
Date: Thu, 07 Jun 2001 00:15:12 GMT
On 8 Apr 2001 08:24:07 +0200, [EMAIL PROTECTED] (Paul Schlyter) wrote:
>In article <[EMAIL PROTECTED]>,
>SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
>
>> Another thought. We still have alot of people out of work here
>> you could hire some Navahos. And just let them communicate messages
>> to and from IRAQ. It worked in WWII.
>
>Yes, it worked in WWII because back then hardly anyone knew Navaho
>except the Navaho's themselves. And the situation was similar for
>most other Native American languages.
>
>However, this success of "Navaho encryption" during WWII spawned
>an interest in Native American langauges among linguists, and since
>then these langages have been investigated more than ever before.
>Therefore today "Navaho encryption" will be much less secure than
>it was during WWII.
==================================
snip
Navaho was chosen for two reasons. One was its obscurity.
The second is that it has many strange phonemes, and can only be
spoken properly by somebody that learned it as a small child. This
meant that spoofing was not possible, as all the receivers would
instantly detect any fake message.
------------------------------
From: [EMAIL PROTECTED] (Patrick Aland)
Subject: DES not a group proof
Date: 6 Jun 2001 17:17:53 -0700
Anyone got a link to the proof from Crypto '92 that showed that DES is
not a group? The links I seem to be finding are either dead or simply
reference it.
Thanks.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers with relation to factoring and BBS
Date: Wed, 6 Jun 2001 22:42:31 -0400
Your repeating that Bob is correct seems to suggest that I stated that
he
was not? No, no. I said he had not erred. It might be better if you had said
that I had said that Bob was correct.
I should take his comments seriously? Why not? I was DAMN serious!!!
(and do not excuse my language).
Way too serious. Let's do it lightly.
Crypto is perhaps the only discipline where you can work and have fun!
Let me tell you a story. There was this scientist (maybe fake as he
himself
suggested) giving advice to one in another discipline for which the
scientist
had limited respect. He told the girl to first carry out the experiment
which some
one else performed and for which she was to change conditions to see the
effect, and then actually change the circumstances to compare results. The
girl was all excited and went back to her great professor. A lot of people
may
already know this story and may feel bored if I go on, so I just skip the
end
of the story.
Now you can also do several simple experiments, or you can take the
results given to you by others and trust them. You can ask: is it in NP? and
you can change the question in form (only in form) with the spirit still
carried
in the questions, such as: is it in P? These I think are simple enough. Then
you may apply other things, such as the 'sutra' you quoted from somewhere.
Try to see if the thing you really want to know by asking the questions
would
still be there after the applications. Don't recite any more, just go and
perform
the simple experiments.
Reciting is by all means good means of doing scientific work. But that
is
just one of the many ways. And thanks for the recitation about NP's full
text.
I, quite unlike Bob, am not prone to giving advice. Bob may come next
and
tell you to read books. I, a lot of times, think that may not be necessary.
I can
often focus just on the things you know (well, if you say it, you must know
it.
logical?) Whether you read more is your cake of the day. But I am sure of
one thing. Next time around, when you assign probablistic uncertainty to a
well-defined, unambiguous definition, you will do a much better job.
You are still not bored with this NP stuff? :) I think it may be
appropriate that
we now draw such a small fullstop as to encompass all the 'bubbles' making
up the universe, so small that we can not see it.
Thanks.
--- (My Signature)
Nicol So wrote in message <[EMAIL PROTECTED]>...
>rosi wrote:
>>
>> Bob Silverman wrote in message
>> <[EMAIL PROTECTED]>...
>> >[EMAIL PROTECTED] (Bill Unruh) wrote in message
>> news:<9eu1ke$njh$[EMAIL PROTECTED]>...
>> >> In <9etv2h$4pn$[EMAIL PROTECTED]> "Scott Fluhrer"
>> <[EMAIL PROTECTED]> writes:
>> >> ]>
>> >> ]> 1. Do we know factoring is NP for certain?
>> >
>> ><snip>
>> >>
>> >> But asking "is a problem NP" is usually a shorthand for
>> >> "Is the problem NP but not P".
>> >
>> >Since when??? It most certainly is NOT such a shorthand.
>>
>> A little surprised to see 'most' instead of 'absolutely'.
>
>"Most certainly" means certainty to the highest degree. Bob was not
>expressing reservation or in any way qualifying his assertion.
>
>> So in your spirit, Bill is not really wrong? I can not help
wondering,
>> after seeing all those
>> discussions by thoughtful and intelligent people with such a variety of
>> opinions on such a
>> single issue, that maybe there is some reason. And I can hardly doubt
that
>> people, those
>> that are not uneducated, do ask the question in the sense Bill hinted.
>> Otherwise, 'it is in NP',
>> but so what?
>>
>> But please, I doubt if I ask in exactly the same sense, even though I
do
>> not think asking in
>> such a sense is such a big deal. It is alright to me. Not alright with
the
>> rest of the world? So
>> what? I do not think you have erred anywhere, but Bill certainly, in my
>> opinion, deserves being
>> defended whether he wants to be defended or not.
>>
>> > "Is a problem in NP?" is a well-defined, unambiguous question.
>>
>> Well-defined? Yes! Unambiguous? Sure! But how about replacing the
word
>> 'question'
>> with something else, for example, 'piece of ...'? :)
>
>What Bob said was correct. You should take his comment seriously.
>
>> Again, what NP stands for? :)
>
>NP stands for "non-deterministic polynomial-time". It is a well-defined
>class of languages. When a problem is phrased as a language recognition
>problem, either it is in NP, or it is not. So in that sense, the
>question is well-defined.
>
>--
>Nicol So, CISSP // paranoid 'at' engineer 'dot' com
>Disclaimer: Views expressed here are casual comments and should
>not be relied upon as the basis for decisions of consequence.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Knapsack security??? Ah....huh
Date: Wed, 6 Jun 2001 22:47:27 -0400
John & Merc,
Are you serious? I am still waiting.
cc'd onto your email addresses. they did not bounce back, must have
reached you.
Thanks
--- (My Signature)
John Bailey wrote in message <[EMAIL PROTECTED]>...
>On 3 Jun 2001 21:32:07 -0700, [EMAIL PROTECTED] (Merc42)
>wrote:
>
>>I was wondering if there are any knapsack systems that are still
>>secure. Any that don't use modular arithmatic to change the keys are
>>of special interest to me. Furthermore, if anybody does know of any,
>>could you please tell me some reference where i could learn more about
>>them. As always, any help is appreciated...
>
> I wonder too. This post in January on this news group did not get
>any responses.
>
>(quoting myself)
>I was amazed to note that the NTRU Public Key method:
>(reference)
>Public key cryptosystem method and apparatus
>http://www.delphion.com/details?pn=US06081597__
>is formally equivalent to a knapsack system.
>Referencing the last section of the NTRU tutorial
>http://www.ntru.com/technology/tutorials/pkcstutorial.htm
>e = r*h + m, where e is the encrypted message, h is a public key, r is
>randomly chosen and m is the message.
>The message m is recovered by finding f*e mod q mod p = m.
>In the NTRU case, e, r, h, m, and f are truncated polynomials
>whereas, in the cases mentioned at the beginning of this post, they
>would simply be large numbers. In either case, essentially the same
>modulo algebra applies, showing the recoverability of encrypted
>plaintext using private keys.
>
>Other knapsaci systems:
>A Comsat patent:
>Simple and effective public-key cryptosystem
>http://www.delphion.com/details?&pn=US04306111__
>and
>Diophantine encryption for public key encoding
>http://www.frontiernet.net/~jmb184/interests/sci.crypt/numerical_encryption
.html
>In this last one, an encrypted message e = r*h + m*k where e is the
>encrypted message, r is a random number, h and k are public key
>values, and m is the encrypted message (number) m is recovered by
>computing m = e*g mod p mod q where g, p, and q are calculated from
>the private keys.
>
>Simplified knapsack systems are easily implemented and would provide
>a nice means for simple, numeric only public key tasks such as
>symmetric key exchange except they have a history of being ultimately
>breakable.
>
>Quoting A. M. Odlyzko of Bell Labs:
>The rise and fall of knapsack cryptosystems,
>http://www.research.att.com/~amo/doc/crypto.html
>Abstract:
>Cryptosystems based on the knapsack problem were among the first
>public key systems to be invented, and for a while were considered to
>be among the most promising. However, essentially all of the knapsack
>cryptosystems that have been proposed so far have been broken. These
>notes outline the basic constructions of these cryptosystems and
>attacks that have been developed on them. (end quote)
>
>Assuming the NTRU system has a new twist, are there also other
>unexploited avenues in which the formalism for simple modulo knapsacks
>might lead to interesting public key systems? An example of such a
>system might use digital Fourier Transforms (FFT) to form knapsacks,
>along lines paralleling NTRU's use of truncated polynomials.
>
>John Bailey
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 03:34:00 +0200
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> :> : But if you have an OTP (a perfect one), you 'need' not
> :> : pad anything, for you already have perfect security
> :> : for the secret you want to communicate.
> :>
> :> The attacker can tell how long the plaintext is just byy looking at the
> :> cyphertext. He can eliminate vast numbers of possible plaintexts
> :> by a cursory examination. How is this "perfect".
>
> : So you are refuting Shannon, aren't you??
>
> I would have to read what Shannon wrote in more detail to say how what
> this thread is about relates to what he wrote.
>
> My main concern is with the definition and usage of the term
> "perfect secrecy" - I'd like to see what Shannon wrote,
> whether his proof relates to what he wrote, and whether others
> have followed his usage properly.
>
> That OTP's leak length information - and thus fail to conceal plaintexts
> properly is rather well known - indeed most other cyphers do this as well.
>
> Tom (and other posters) seem to have got the idea that the ordinary OTP
> is actually perfect at concealing information about the plaintext, given
> the cyphertext.
>
> That does /seem/ to be what Shannon said:
>
> ``The first definition of information-theoretic secrecy was given by
> Shannon, the founder of information theory. It is called perfect secrecy
> and means by definition that the plaintext is statistically independent
> of the encrypted data. This is equivalent to saying that the enemy
> cryptanalyst can do no better than guessing the plaintext without
> knowledge of the encrypted data, no matter how much time and computing
> power is used.''
>
> - http://www.inf.ethz.ch/department/TI/um/research/keydemo/Background.html
>
> ...but he is also supposed to have proved that the (conventional?) OTP
> has this property, which it does not. I'll resolve the apparent friction
> between these ideas by reading his actual words and proof.
>
> I'm curious to learn the historical roots of the (clearly mistaken) idea
> that conventional OTPs are perfect in this way. Is Shannon responsible?
> ...or those who came after him?
I sincerely look forward to learn what you are going
to find out.
Meanwhile I believe that the following is correct about
the issue: The OTP processing only guarantees that the
particular work that is performed doesn't give the opponent
any (more) information. It doesn't exclude however the
existence of other processing that could reduce the
information that he could otherwise have about the message.
As a special example, if any message is sent from my home,
the opponent knows that some person is present there (or
at least someone has programmed my computer to undertake
that action) at the particular time point. (That could
mean under circumstances quite a lot, e.g. when for
months no message had ever been sent.) No encryption
scheme, however 'perfect', could deprive him from
obtaining that knowledge. On the other hand, I could
manage to send the message from another place, in which
case he wouldn't have that information. Thus in a sense
the word 'perfect' in 'perfect security' is only to be
understood as one of terminology (definition) only and
does not have the common connotation of 'perfection'
(the ideal, the absolute best).
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: 7 Jun 2001 01:42:54 GMT
[EMAIL PROTECTED] (Mok-Kong Shen) wrote in
<[EMAIL PROTECTED]>:
>
>>
>> I would have to read what Shannon wrote in more detail to say how what
>> this thread is about relates to what he wrote.
Actually its Tommy and Mok that need to read up.
>>
>> My main concern is with the definition and usage of the term
>> "perfect secrecy" - I'd like to see what Shannon wrote,
>> whether his proof relates to what he wrote, and whether others
>> have followed his usage properly.
>>
>> That OTP's leak length information - and thus fail to conceal
>> plaintexts properly is rather well known - indeed most other cyphers
>> do this as well.
>>
>> Tom (and other posters) seem to have got the idea that the ordinary
>> OTP is actually perfect at concealing information about the plaintext,
>> given the cyphertext.
>>
>> That does /seem/ to be what Shannon said:
>>
>> ``The first definition of information-theoretic secrecy was given by
>> Shannon, the founder of information theory. It is called perfect
>> secrecy and means by definition that the plaintext is statistically
>> independent of the encrypted data. This is equivalent to saying that
>> the enemy cryptanalyst can do no better than guessing the plaintext
>> without knowledge of the encrypted data, no matter how much time and
>> computing power is used.''
>>
>> - http://www.inf.ethz.ch/department/TI/um/research/keydemo/Background.
>> html
>>
>> ...but he is also supposed to have proved that the (conventional?) OTP
>> has this property, which it does not. I'll resolve the apparent
>> friction between these ideas by reading his actual words and proof.
>>
>> I'm curious to learn the historical roots of the (clearly mistaken)
>> idea that conventional OTPs are perfect in this way. Is Shannon
>> responsible? ...or those who came after him?
>
>I sincerely look forward to learn what you are going
>to find out.
>
>Meanwhile I believe that the following is correct about
>the issue: The OTP processing only guarantees that the
>particular work that is performed doesn't give the opponent
>any (more) information. It doesn't exclude however the
>existence of other processing that could reduce the
>information that he could otherwise have about the message.
>As a special example, if any message is sent from my home,
>the opponent knows that some person is present there (or
>at least someone has programmed my computer to undertake
>that action) at the particular time point. (That could
>mean under circumstances quite a lot, e.g. when for
>months no message had ever been sent.) No encryption
>scheme, however 'perfect', could deprive him from
>obtaining that knowledge. On the other hand, I could
>manage to send the message from another place, in which
>case he wouldn't have that information. Thus in a sense
>the word 'perfect' in 'perfect security' is only to be
>understood as one of terminology (definition) only and
>does not have the common connotation of 'perfection'
>(the ideal, the absolute best).
>
No "perfect security" means what it says see my
other posts where I quote Shannon directly.
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!
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Notion of perfect secrecy
Date: Thu, 07 Jun 2001 02:08:16 GMT
Ok this has gone on too long.
Typically what you guys are missing is that the length of the message is not
the secret. It's the contents of the message.
In this case an OTP (despite what you think) fits the bill. If you use an
OTP all messages are equally probable (of the same length) which means you
can never ever ever ever never ever ever never tell the right message from a
wrong message by attacking the math.
That's not a guess, or trivial conjecture, it's a fact.
If the key is independent of the message you can't guess the message.
Even if you can narrow the message down by some other means all remaining
messages are equal likely.
Let's suppose you trap my bank account transactions and all money ammounts
are 32-bit integers. Obviously you can narrow the limit towards zero
dollars (I'm poor) so within 0 to 1000 dollars. Now I do a transaction and
you intercept the 32-bit OTP encrypted dollar amount. You guess that the
upper 32-11 bits are zero so you have 11 remaining bits to resolve.
Assuming no other knowledge all 11-bit amounts are equal probable which
means you can't tell if I sent 500 or 727 or 11 dollars more than random.
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.
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
** 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
******************************
