Cryptography-Digest Digest #187, Volume #14 Thu, 19 Apr 01 21:13:01 EDT
Contents:
Re: OTP breaking strategy ("Paul Pires")
Re: OTP breaking strategy ("Tom St Denis")
Re: OTP breaking strategy ("Paul Pires")
Re: OTP breaking strategy ("Paul Pires")
Re: A practical idea to reinforce passwords (Tony L. Svanstrom)
Re: "I do not feel secure using your program any more." (Roger Fulton)
Re: Minimal Perfect Hashing (Paul Rubin)
Re: Can this be done? (John Wasser)
Re: "UNCOBER" = Universal Code Breaker ("Paul Pires")
Diffie-Hellman signatures now described (John Savard)
Re: Basic AES question (John Savard)
Re: "UNCOBER" = Universal Code Breaker (John Savard)
Re: Diffie-Hellman signatures now described ("Tom St Denis")
Re: "UNCOBER" = Universal Code Breaker (John Savard)
Re: Diffie-Hellman signatures now described (John Savard)
Re: Diffie-Hellman signatures now described ("Tom St Denis")
Re: Minimal Perfect Hashing (David Formosa (aka ? the Platypus))
Re: All One Polynomail ("Andre")
----------------------------------------------------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Thu, 19 Apr 2001 15:39:26 -0700
newbie <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> You wrote :
> > No that is a way to find that you know nothing about the inputs except the
> > probabilities you knew before. I suggest you try my challenge, I think it
> > would be enlightening for you.
>
> I'm still waiting for decryption of my encrypted-message "crack it".
> It was a single cipher. But not decrypted at date.
> I can not challenge you, I'm nothing more than newbie that has a lot to
> learn.
Begin.
You've had many different answers, good ones too so let's try this.
1, If your key is the same size as your message, there is no difference
between guessing the key and guessing the message.
2, If you can prove that the only way an adversary can solve for
your key is by guessing then 1 above applies.
3, If the key is the product of a random process and is secret,
it cannot be solved for faster than by guessing. If it could be, it
wouldn't be random.
4, If you have never used that key before and if your plain message is
kept secret, the key will remain a secret and the message is safe from
decryption (This is the One Time part)
5, If you use any part of the pads sequence again, you have introduced
the certainty that the security has been correspondingly reduced. Since
there are now provable methods that can get some information about
the key if this occurs. [*]
6, You might ameliorate the above defect by chosing how to re-use the
pad cleverly.
7, Any repair you have now made is a function of your cleverness
and has nothing to do with the underlying proof of the OTP.
8, To my best recollection, No one has published a proof of cleverness.
Not even Shannon. I did once but I was not smart enough to
understand it.
[*] I don't think I have this part completely right but it's close enough for
the topic at hand.
Paul
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Thu, 19 Apr 2001 23:06:36 GMT
"newbie" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Do not forget that any plaintext is a determinstic sentence of "sense".
> It is a long bit-string with a lot of constraints ( grammar, syntax,
> sense, specific terms, specific patterns, etc...). It is builded
> structure. You could still separate builded structure from random
> sequence even if mathematically it is impossible.
> Equality : random + structured text is not strictly = random.
Um this qualifies as stupid. You didn't even respond to my post that or
you're too disallusioned from reality to acknowledge it. I think this
thread has been dead for a bit now, adios
Tom
>
> Tom St Denis wrote:
> >
> > "newbie" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > You are reaching what I had tried to prouve.
> > > You could distinguish with extra-information which message is valid.
> > > And select the message. Because, the plaintext is deterministic
> > > sequence.
> > > If you could distinguish truly random output and not random, you have
> > > still a way to break it.
> > > I know it is very hard. Very very hard. It is like rebuilding the
> > > plaintext with very few information.
> > > I said OTP could be broken practically.
> > > In theory, I KNOW that is unbreakable, but If you combine the context
> > > factor and other extra-information you can break it.
> >
> > No you keep missing the important (I think you are ignoring my posts)
facts.
> > An OTP is not breakable under ANY circumstances. You can get the info
it's
> > hiding via other methods (i.e torture, just plain assuming the
plaintext,
> > likely to be wrong) but you cannot break an OTP.
> >
> > Just remember that there are lot of english sentences for a given n-char
OTP
> > message, all of which are equal probable.
> >
> > Just like (let's assume the message is zero padded or something)
> >
> > I WALKED MY DOG TODAY 0
> > ME GOOD LIKE CAT 0
> > NOBODY READS MY POSTS 0
> >
> > are all equal probable. There is no way to tell them from each other.
> >
> > Tom
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Thu, 19 Apr 2001 16:06:21 -0700
<[EMAIL PROTECTED]> wrote in message news:BCHD6.4820$[EMAIL PROTECTED]...
> newbie <[EMAIL PROTECTED]> wrote:
> : When you introduce the context factor all the messages are not
> : equiprobable.
> : That is the way to try to find out the input.
>
> : If I analyse any output of 128 bits I will obtain 2^128 messages. I know
> : that.
> : But all the messages are not 100% in the context.
> : And all the output are not 100% random.
> : I have two ways to select : context factor and degree of randomness.
>
>
> Okay, remember that you don't have access to the pad itself. Now, suppose I
> have two different pads and I encrypt the following two messages:
>
> SELL 750 SHARES
> BUY 1000 SHARES
>
> Since I am not reusing the OTP, I encode each message with a different
> pad. By some bizarre coincidence, the pads happen to encrypt their
> messages to exactly the same result: 5e8f128c65a30954371a7e494217ad
>
> Now, given that the two messages are reasonably within the same context here,
> how can you possibly tell which one I actually sent?
>
> You might be able to guess which one I sent by analyzing my business and maybe
> by planting spies in my office, but at that point, you haven't really broken
> the OTP. In fact, you might figure out that I need to send the "BUY 1000 SHARES"
> message, but because I made a mistake, I sent the "SELL 750 SHARES" message.
Artfully done. I don't think I'll play chess with you :-)
I'm gonna clip this one and just post it during the next OTP
controversy.....sigh.... Probably tomorrow.
Paul
> --
> Mark Wutka
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: OTP breaking strategy
Date: Thu, 19 Apr 2001 16:11:09 -0700
Opps! right comment, right newbie, wrong thread.
Sorry about that. Posting to two different but similar threads
can be confusing.
Anyway, it is still to the point.
Paul
------------------------------
Subject: Re: A practical idea to reinforce passwords
From: [EMAIL PROTECTED] (Tony L. Svanstrom)
Date: Thu, 19 Apr 2001 23:16:49 GMT
Harald Korneliussen <[EMAIL PROTECTED]> wrote:
> My idea is that upon selecting a password, X bits of random data is added
> to the password. You are not informed of what these bits are, nor does the
> computer store them. The computer only stores how many bits there are, and
> brute-forces them every time you enter you password.
Scramdisk is doing something like that, but instead of adding random
data to the password it just doesn't store any information about what
algorithm was used. This means that the program has to try all the
"valid" (ie the ones that are an option to use) algorithms and then
check if that was the correct one.
/Tony
--
########################################################################
I'm sorry, I'm sorry; actually, what I said was:
HOW WOULD YOU LIKE TO SUCK MY BALLS?
- South Park -
------------------------------
From: [EMAIL PROTECTED] (Roger Fulton)
Crossposted-To: talk.politics.misc,alt.hacker
Subject: Re: "I do not feel secure using your program any more."
Date: Thu, 19 Apr 01 23:20:30 GMT
In article <[EMAIL PROTECTED]>, James Felling
<[EMAIL PROTECTED]> wrote:
}
}
}Anthony Stephen Szopa wrote:
}
}> "I do not feel secure using your program any more."
}>
}> You sure jumped to a hasty conclusion.
}
}Perhaps, perhaps not. Your program can produce sound output, but you need
}to enter far more data/do much more in the way of babysitting the code to
}get the same level of quality you would get with any modern stream cypher.
}The program you sell is slow vs other methods such a s RC4, memory
}consumptive, has poor key agility, and if not used properly produces bad
}output without warning the user.
Why the bloody christing pig fuck is this in
talk.politics.misc???????????????????????????
Followups set to alt.flame you shithead.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Minimal Perfect Hashing
Date: 19 Apr 2001 16:32:15 -0700
"Francois St-Arnaud" <[EMAIL PROTECTED]> writes:
> I'm looking for a simple C algorithm for a function y = f(x) that would take
> a 48-bit number x and return another 48-bit number y. f should map x to y in
> a one-to-one fashion. f should be one-way, or at least, it should not be
> trivial to calculate x knowing y and the algorithm used.
>
> Any thoughts, code snips, links?
That's called a 48 bit block cipher ;-). Try Schroeppel's HPC (Hasty
Pudding Cipher) which you can find with a search engine. If you don't
mind 64 bits instead of 48, there's a very wide variety of 64-bit block
ciphers to choose from, starting with the venerable DES.
------------------------------
Subject: Re: Can this be done?
From: John Wasser <[EMAIL PROTECTED]>
Date: Thu, 19 Apr 2001 23:36:25 GMT
[[ This message was both posted and mailed. ]]
Alice sends a message containing her public key (or she can add it to
one or more of the messges). Alice hashes each message and encrypts
the hash with her private key.
Bob decrypts the hash with the known public key to find that the
decrypted hash matches the message. This proves that all messages were
sent by someone who knows the private key that matches the public key.
The public key
In article <[EMAIL PROTECTED]>,
Julian Morrison <[EMAIL PROTECTED]> wrote:
> Here's a scenario:
>
> 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?
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Thu, 19 Apr 2001 16:45:03 -0700
newbie <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> So if the probability of non-random is infinitesimal, why to try
> statistical tests to prove truly randomness?
Read the instruction manual that comes with these tests.
They do not prove that an output is random (nothing can) They
detect a probability that an output might not be random.
> Statistical tests (Diehard, Maurer etc...), is it a loss of time?
Not if you use them for their intended purpose. If you are trying
to prove that a particular sequence IS random, then yes, they are
a complete and total waste of time.
> Sincerely I do not understand.
> I choose any bit-string I have 99.9999999 % that is purely random.
> Why wasting time to find if it is random or not.
It is a waste of time to use the test for this purpose. If
it hurts when you do that...don't do that.
Paul
>
>
>
> John Savard wrote:
> >
> > On Thu, 19 Apr 2001 14:38:17 -0300, newbie <[EMAIL PROTECTED]>
> > wrote, in part:
> >
> > >If the message is 100101010
> > >and the ouput 1111111111
> > >you are quite sure to reject the "possible" key.
> >
> > The fraction of possible keys that are statistically nonrandom is
> > nearly infinitesimal, and so this is unlikely to eliminate any
> > possible plaintexts. Furthermore, it is generally considered an error
> > when doing an OTP to reject random keys because they don't look
> > random, although using a pad consisting of 0000000...0000 to encrypt a
> > message would make all but the stoutest hearts quail. (We had an
> > interesting debate on this issue some time ago.)
> >
> > John Savard
> > http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Diffie-Hellman signatures now described
Date: Fri, 20 Apr 2001 00:06:30 GMT
One thing I had not described on my site, it involving somewhat
advanced mathematics, was how Diffie-Hellman, rather than RSA, could
be used as a basis for digital signatures.
At
http://home.ecn.ab.ca/~jsavard/crypto/pk050302.htm
I have now rectified this omission. I hope I have added some
information that will make these signatures easier to understand than
they may have been from the description in AC. I've also added a
description of El Gamal on the preceding page.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Basic AES question
Date: Fri, 20 Apr 2001 00:09:38 GMT
On Thu, 19 Apr 2001 16:17:16 GMT, [EMAIL PROTECTED] (Lou Grinzo) wrote,
in part:
>I'm just starting to learn about AES, and I was wondering:
>Why does the AES standard support only the key sizes of
>(I think) 128, 192, and 256 bits?
These where the key sizes originally requested when an algorithm was
called for. Thus, Rijndael with these key sizes was what was studied
and analyzed during the approval process; with other key sizes, it
might possibly have different properties, which may be insecure.
In my opinion, however, with a 128 bit block size (Rijndael can also
cope with other block sizes), the key size of 224 bits may provide
protection against some weaknesses that may possibly exist with the
regular key sizes, so, while I understand the rationale behind
including only the standard key sizes, I think the decision should be
changed.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Fri, 20 Apr 2001 00:12:24 GMT
On Thu, 19 Apr 2001 18:17:36 -0300, newbie <[EMAIL PROTECTED]>
wrote, in part:
>So if the probability of non-random is infinitesimal, why to try
>statistical tests to prove truly randomness?
>Statistical tests (Diehard, Maurer etc...), is it a loss of time?
>Sincerely I do not understand.
>I choose any bit-string I have 99.9999999 % that is purely random.
>Why wasting time to find if it is random or not.
Well, if I generated numbers by throwing dice, the probability of
something non-random would be infinitesimal, so applying Diehard or
Maurer to those numbers would be a waste of time.
If I generate a string of numbers by some other method, say a linear
congruential generator, then I'm using a technique which doesn't
generate all possible sequences of numbers - and it IS quite likely to
produce numbers that fail statistical tests.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Diffie-Hellman signatures now described
Date: Fri, 20 Apr 2001 00:26:35 GMT
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> One thing I had not described on my site, it involving somewhat
> advanced mathematics, was how Diffie-Hellman, rather than RSA, could
> be used as a basis for digital signatures.
To be precise DH cannot be used for signatures. ElGamal is the
encryption/signature scheme based on the DL problem.
DH key exchange is based on the DLP too...
Tom
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Fri, 20 Apr 2001 00:37:25 GMT
On Wed, 18 Apr 2001 12:04:07 -0300, newbie <[EMAIL PROTECTED]>
wrote, in part:
>What some forget is the context where a word occure.
>Just sample :
>
>What is important for me is to discover the amount of credit transfer.
>
>I look for dollars or $ in my cipher text
>cipher text = 10010001000100101010...
>keystream totally random = 1010101010001010101010...
>suppose that $ or dollars = 0100010010
>I have to slide my bit-string dollars in all the ciphertext bit by bit
>until I find if it match. If it matches, it does not matter for me what
>the fraction of random string is.
>I continue.
Although your technique will not work for a _real_ one-time-pad,
composed of genuinely random digits, and you are not realizing this
because of failing to understand some facts about random numbers, it
is indeed a valid and powerful technique.
What you are describing is pretty much exactly the technique used by
the NSA in its VENONA project to decrypt some messages sent by the
Soviets with one-time pads...because those one-time pads, instead of
being filled with genuinely random numbers, were just made by typists
who were told to type digits at random. This meant that sequences of
the same digit more than twice were extremely rare, digits typed with
the right and left hands often alternated, and so on and so forth.
This constrained the keystream enough so that techniques like what you
propose really could work.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Diffie-Hellman signatures now described
Date: Fri, 20 Apr 2001 00:39:22 GMT
On Fri, 20 Apr 2001 00:26:35 GMT, "Tom St Denis"
<[EMAIL PROTECTED]> wrote, in part:
>"John Savard" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> One thing I had not described on my site, it involving somewhat
>> advanced mathematics, was how Diffie-Hellman, rather than RSA, could
>> be used as a basis for digital signatures.
>To be precise DH cannot be used for signatures. ElGamal is the
>encryption/signature scheme based on the DL problem.
>DH key exchange is based on the DLP too...
Well, I could have said 'how the discrete log problem could be used as
a basis for digital signatures'; DH can't be used, but it was the
basis of the five schemes noted by Bruce in AC, only one of which is
said to correspond to El Gamal...
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Diffie-Hellman signatures now described
Date: Fri, 20 Apr 2001 00:40:13 GMT
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Fri, 20 Apr 2001 00:26:35 GMT, "Tom St Denis"
> <[EMAIL PROTECTED]> wrote, in part:
> >"John Savard" <[EMAIL PROTECTED]> wrote in message
> >news:[EMAIL PROTECTED]...
>
> >> One thing I had not described on my site, it involving somewhat
> >> advanced mathematics, was how Diffie-Hellman, rather than RSA, could
> >> be used as a basis for digital signatures.
>
> >To be precise DH cannot be used for signatures. ElGamal is the
> >encryption/signature scheme based on the DL problem.
>
> >DH key exchange is based on the DLP too...
>
> Well, I could have said 'how the discrete log problem could be used as
> a basis for digital signatures'; DH can't be used, but it was the
> basis of the five schemes noted by Bruce in AC, only one of which is
> said to correspond to El Gamal...
DH afaik describes a key exchange protocol involving the DLP.
Tom
------------------------------
From: [EMAIL PROTECTED] (David Formosa (aka ? the Platypus))
Subject: Re: Minimal Perfect Hashing
Reply-To: [EMAIL PROTECTED]
Date: Fri, 20 Apr 2001 00:37:29 GMT
On Thu, 19 Apr 2001 19:47:46 GMT, Francois St-Arnaud
<[EMAIL PROTECTED]> wrote:
[...]
> I'm looking for a simple C algorithm for a function y = f(x) that would take
> a 48-bit number x and return another 48-bit number y. f should map x to y in
> a one-to-one fashion. f should be one-way, or at least, it should not be
> trivial to calculate x knowing y and the algorithm used.
The Discrete Logarithm Problem can be used for this.
y = a ^ x mod p
--
Please excuse my spelling as I suffer from agraphia. See
http://dformosa.zeta.org.au/~dformosa/Spelling.html to find out more.
Free the Memes.
------------------------------
From: "Andre" <[EMAIL PROTECTED]>
Subject: Re: All One Polynomail
Date: Fri, 20 Apr 2001 09:53:10 +0900
Reply-To: "Andre" <[EMAIL PROTECTED]>
> Joe Silverman wrote a very nice paper for CHES '99 which describes it. He
> found some previous references and lists them there as well. I think you
> can find it under the Springer LNCS series, or maybe floating around the
> net. If not, I've got a paper copy I can mail you.
>
> Patience, persistence, truth,
> Dr. mike
Thank you for your great suggestion.
I have the book of CHES'99.
But, I didn't know that till now on.
Andre
------------------------------
** 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
******************************
