Cryptography-Digest Digest #228, Volume #14 Tue, 24 Apr 01 23:13:00 EDT
Contents:
Re: Security proof for Steak ("Henrick Hellstr�m")
Re: Security proof for Steak ("Tom St Denis")
Re: OTP WAS BROKEN!!! (Lou Grinzo)
Re: Generating primes by incremental search (Terry Boon)
Question on p and q (Brett)
Re: Delta patching of encrypted data (David Wagner)
Re: Question on p and q ("Tom St Denis")
Re: Can this be done? (David Hopwood)
impossible differentials ("Tom St Denis")
Re: impossible differentials ("Tom St Denis")
Re: Can this be done? (SCOTT19U.ZIP_GUY)
effects of mistaken *partial* reuse of a OTP? ([EMAIL PROTECTED])
Re: Censorship Threat at Information Hiding Workshop ("Paul Pires")
Re: effects of mistaken *partial* reuse of a OTP? ("Tom St Denis")
Re: effects of mistaken *partial* reuse of a OTP? ("Joseph Ashwood")
----------------------------------------------------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: Security proof for Steak
Date: Wed, 25 Apr 2001 01:11:45 +0200
"Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
news:hUmF6.49738$[EMAIL PROTECTED]...
> Ahh but it depends on how far the distinguisher can go. Often it's only a
> few rounds and after that the output differences are indistinguishable
from
> random. For example, if you took fixed sboxes and plugged them into a 4x4
> MDS and used that as your round function, if you used say 20 rounds (i.e
> 8-byte block cipher) it should be secure.
That's only an academic proposal, I hope. Somehow I don't see the point in
making a cipher less secure and less efficient at the same time. ;-)
Furthermore, your design would not really be an 8-byte block cipher, unless
you discarded the PCFB-mode-ish feedback too.
Lastly, you are right about the behavior of iterated MDS matrix transforms.
Actually, I think I just found an MDS matrix such that eight iterations of
it would be equal to four iterations of the Steak MT matrix with fixed
S-boxes. But that just seems to add to the perception of the robustness of
the present design.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Security proof for Steak
Date: Tue, 24 Apr 2001 23:20:34 GMT
"Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote in message
news:9c518o$kon$[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
> news:hUmF6.49738$[EMAIL PROTECTED]...
> > Ahh but it depends on how far the distinguisher can go. Often it's only
a
> > few rounds and after that the output differences are indistinguishable
> from
> > random. For example, if you took fixed sboxes and plugged them into a
4x4
> > MDS and used that as your round function, if you used say 20 rounds (i.e
> > 8-byte block cipher) it should be secure.
>
> That's only an academic proposal, I hope. Somehow I don't see the point in
> making a cipher less secure and less efficient at the same time. ;-)
What? If it's more secure it's more secure....
> Furthermore, your design would not really be an 8-byte block cipher,
unless
> you discarded the PCFB-mode-ish feedback too.
It is. You make a feistel with a 4-byte round function. Hm.. that's
8-bytes if my math is sharp enough.
> Lastly, you are right about the behavior of iterated MDS matrix
transforms.
> Actually, I think I just found an MDS matrix such that eight iterations of
> it would be equal to four iterations of the Steak MT matrix with fixed
> S-boxes. But that just seems to add to the perception of the robustness of
> the present design.
Right ok.
Tom
------------------------------
From: [EMAIL PROTECTED] (Lou Grinzo)
Subject: Re: OTP WAS BROKEN!!!
Date: Tue, 24 Apr 2001 23:31:06 GMT
I've been reading this thread all along and staying out of the
crypto part of the conversation, but I wanted to jump in here.
I think that what we have here is an instance of someone using
common experience and an ability to reason to try to solve a
problem that pure math says can't be solved. For example, I'm
sure we've all seen the explanations of how critical this kind
of process was in breaking messages encoded with Enigma machines
in WW II--the British often knew things like the fact that a
weather report was sent every from a given location at the
same time every day, so they would look for certain words in
the beginning of an intercepted message. We can cite all sorts
of examples from brain teasers to much more serious things, where
similar reasoning pays off with the right answer.
The disconnect comes, I think, when you try to apply that approach
to a OTP, as that term is strictly defined. Someone gave an
example earlier in this thread of a message that might be an
order to attack on the enemy's "rear" or "left", and I think
that nicely illustrates the problem: You can guess what most
of the message is, but when you get to those four characters
that correspond to "left" or "rear" in the plaintext, there's
no way to use logic or intelligent guessing or whatever you
care to call it to narrow it down, because those two possibilities
are equally likely, and having cracked other parts of the
cyphertext and key (assuming you got it right) doesn't help you
at all with those critical four letters. For all you know they
could be "frnt" (for "front") or "slow" or something else entirely.
[I'd say something here about how if I'm wrong please correct me,
but having read the thread this far, I suspect that's not
necessary. <g>]
Lou
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> I'm just trying to present ideas.
> Do not forget that I'm newbie.
> I'm just to exploit extra-information and other tricks to try to reduce
> the number of possibilities.
> I tried selecting by degree of randomness.
> I tried by introducing the "context" factor to select.
> I tried by simulating re-susing the key.
> All did not work.
> Only guessing what the sender wrote, using extra-information, could
> work.
> This option has no sense.
> My objective is to find a way to give to some messages more weight than
> others.
> I'm still thinking even if I KNOW THAT ALL MESSAGES ARE VALID.
> C= P Xor k = P' Xor k' = P" Xor k" etc.....
> I know that.
> I'm trying to find some trick to isolate a defined group of P's or K's
> to solve the problem.
> I'm looking if some specific properties of k or P could help me.
>
> I have a text and random sequence.
> How to distinguish between the two.
> That is the core of the problem.
>
>
>
>
>
>
>
> Volker Hetzer wrote:
> >
> > newbie wrote:
> > > THE NUMBER OF MESSAGES WHICH HAVE A SENSE IS INFINITESIMAL COMPARING TO
> > > THOSE WHICH DOES NOT HAVE A SENSE!!!!!!!!!!!!!!!!!!!
> > One can be more specific. The number of messages that makes sense, given
> > a certain context and OTP encrypted message is *exactly* the number of messages
> > that make sense given a certain context and the size of the OTP encrypted
> > message.
> > There's no way to narrow it down further.
> > Might I remind you that you've been given three simple chaellenges and
> > have not taken up even one? Not even stated what's wrong with the challenges?
> >
> > Greetings!
> > Volker
> > --
> > They laughed at Galileo. They laughed at Copernicus. They laughed at
> > Columbus. But remember, they also laughed at Bozo the Clown.
>
------------------------------
From: [EMAIL PROTECTED] (Terry Boon)
Subject: Re: Generating primes by incremental search
Date: Tue, 24 Apr 2001 23:02:01 GMT
Reply-To: [EMAIL PROTECTED]
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
On Mon, 23 Apr 2001 04:48:36 +0100, David Hopwood
<[EMAIL PROTECTED]> wrote:
>Terry Boon wrote:
[bias from generating primes with add-two method - snip]
>> (And, furthermore, is this effect significant? ...)
>
>Almost certainly not. See
>
> J�rgen Brandt, Ivan Damg�rd,
> "On generation of probable primes by incremental search."
> Advances in Cryptology - Crypto '92,
> Lecture Notes in Computer Science Vol. 740, pp. 358-370.
> Springer-Verlag, 1993.
>
>This doesn't appear to be on the web. A brief summary is that they look
>at the entropy of the primes output by the incremental search algorithm,
>and show that it is not too much less than that of randomly chosen
>primes, under a assumption called the 'prime r-tuple conjecture' (which
>is well-supported experimentally).
Thanks for the reference and summary.
This makes a little less pressing my curiosity to experimentally check
the entropy of such a random prime generator (although I'll still try
when I have time)...
...and now I shall instead have to find out what the
interesting-sounding "prime r-tuple conjecture" states.
- --
Terry Boon, Hertfordshire, UK
[EMAIL PROTECTED]
=====BEGIN PGP SIGNATURE=====
Version: GnuPG v1.0.4 (GNU/Linux)
Comment: Processed by Mailcrypt 3.5.5
iD8DBQE65gbWB+GG7A6DEUARAiBYAJ4j8ybSedjHP/Kgx1+9u8aSguMZsACgn/Ky
5PJSozRcqLPXQEgVl/Fxnbg=
=tCxM
=====END PGP SIGNATURE=====
------------------------------
From: Brett <[EMAIL PROTECTED]>
Subject: Question on p and q
Date: Tue, 24 Apr 2001 19:44:30 -0400
Reply-To: [EMAIL PROTECTED]
Hi,
Pardon if this is rediculously easy, but I consulted the FAQ
before posting and do not find it in there.
Public key cryptography relies on two very large primes p and
q to be multiplied together to form a larger number N that makes
up the public key. My question is: How does one find such
large primes in the first place and verify that they are primes
in a reasonable time. If you have a 4096-bit key, N is approx.
10 ^ 1233 in size. p and q must be somewhere in the 10 ^ 600
range ... How does one go about creating a prime that big, and
making sure it is in fact prime?
Brett
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Delta patching of encrypted data
Date: 24 Apr 2001 23:57:43 GMT
Anon wrote:
>But how much will that expose my key, given that the attacker will now have
>a larger set of plaintexts and matching ciphertexts to work with?
It won't. Revealing lots of known (or even chosen) plaintext/ciphertext
pairs is no problem for any halfway decent modern block cipher. Disclosing
known plaintext is the least of your worries. My main concern would be the
information leakage, but if you can take care of that somehow, I think
you're probably set.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Question on p and q
Date: Wed, 25 Apr 2001 00:04:56 GMT
"Brett" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Hi,
>
> Pardon if this is rediculously easy, but I consulted the FAQ
> before posting and do not find it in there.
>
> Public key cryptography relies on two very large primes p and
> q to be multiplied together to form a larger number N that makes
> up the public key. My question is: How does one find such
> large primes in the first place and verify that they are primes
> in a reasonable time. If you have a 4096-bit key, N is approx.
> 10 ^ 1233 in size. p and q must be somewhere in the 10 ^ 600
> range ... How does one go about creating a prime that big, and
> making sure it is in fact prime?
First off RSA and BBS (Blum Blum Shub) depend on a large composite for
security. Not all PK algorithms require that (see Diffie-Hellman, Elliptic
Curve Crypto, ElGamal).
Second the product typically isn't all there is to the public key. In RSA
for example a public exponent is required as well.
To make large primes you take advantage of FLT (Fermats Little Theorem) that
if P is prime and G /|\ P then G^(P-1) mod P = 1, (/|\ is my clever ascii
art for "does not divide").
Of course certain numbers will pass this (i.e some composite P). Which is
why the test was revamped (see Miller-Rabin) to make the algorithm more
constrainted.
Tom
------------------------------
Date: Wed, 25 Apr 2001 02:22:48 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Re: Can this be done?
=====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.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOuYm1jkCAxeYt5gVAQFncgf/cTYwygY8RMifvlB6ndD178CK4lfMqa12
1xFMqv34PK1SxDiu8HAgpLgD1gFW9XCihRQDoDtD+eB7/G8Musl7BVH41EpX3UQF
G+k4915oUoB2OPOEnf4KlIBu2bZBiBazjFeGWDKSdeOFjn5TnPM64r6bp8hNVkto
wpt0y+lvCluhz4BjLJFvEsmqOHh7PkxSUyzfXJ4AjBa+WdxK56SjDuPU+aIShznS
ZZasD+V/cgesF6xOkObyn6o2kivs+swyr+jjd3XseCRTxwkqjO9T7DlYqoyOZbcn
+E9uCbaRp5j8e8wELNRCdRUN5I5tIEm6fXay4tInso7d3zUOWcu4qg==
=vSIQ
=====END PGP SIGNATURE=====
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: impossible differentials
Date: Wed, 25 Apr 2001 01:27:07 GMT
How do they work? I get the key extraction concept. I.e if the subkey lets
the the difference occur it can't be the right key, but if the difference is
impossible how can it occur at all?
Let's take the example of a 2x2 MDS as a round function. An impossible
differential would be (0,x) -/-> (y, 0) and (0, y). How can that be used if
that can never occur.
Ok in this example cipher let's say it's a four-word feistel where the round
function is just the 2x2 MDS (ignore the fact it's linear, etc...) How can
we use that imp.diff in an attack?
All I see..
1. Input a difference of (0,0,0,X)
2. First round (0,0) is the input so it outputs (0,0) (differences not
values)
3. Second round (0,X) must output (X,X) (who cares what X is)
4. Third round (X,X) must goto (X,X),(X,0) or (0,X)
How can we attack this using the impossible differential?
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: impossible differentials
Date: Wed, 25 Apr 2001 01:49:21 GMT
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:LJpF6.50961$[EMAIL PROTECTED]...
> How do they work? I get the key extraction concept. I.e if the subkey
lets
> the the difference occur it can't be the right key, but if the difference
is
> impossible how can it occur at all?
Is it because an invalid key guess will cause a new difference in the round?
I.e
out = F(x) xor F(x xor in)
becomes
out = F(x xor key_wrong) xor F(x xor in xor key_wrong)
Where key_wrong will lead to a condition that lets the impossible diff
occur?
AS in the original 2x2 mds where (x,0) -/-> (0, y) or (y, 0) a wrong key
will have the input diff of (x, x') where x' would be the difference caused
by the wrong key guess?
Tom
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Can this be done?
Date: 25 Apr 2001 01:40:32 GMT
[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.
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: [EMAIL PROTECTED]
Subject: effects of mistaken *partial* reuse of a OTP?
Date: Wed, 25 Apr 2001 02:36:27 GMT
What is the impact on cryptanalysis where two different messages are
enciphered with a portion of a OTP being mistakenly reused? Eg with
two OTPs which due to a flaw in production perhaps, have a section in
common (eg end of one repeated in beginning of next)?
Is the effect simply that the attacker is able to recover those bits
of the two messages which were encoded with the common section, but
that the remainder of the two messages are impenetrable, because for
these bits, the not-in-common bits of each OTP are genuinely one-time?
If so then, in practical terms it is possible that mistaken reuse of a
only a small number of bits (as a proportion of the total message/pad
length) may be tolerable provided the message material recovered is
insufficient for the attacker to understand the critical content of
the meassages?
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: Tue, 24 Apr 2001 19:38:08 -0700
David Wagner <[EMAIL PROTECTED]> wrote in message
news:9c4rag$6n5$[EMAIL PROTECTED]...
> Paul Pires wrote:
> >As Donald Nash pointed out,
> >copyright theft is the stealing of ones labors or services that one has secured
> >their rights to.
>
> Once again, this is a misleading metaphor. Theft of physical property
> deprives the owner of the property. "Theft" of intellectual property
> may deprive the owner of the chance to get paid for another copy of the
> IP, but doesn't deprive the owner of the original good. Using the word
> "theft" to refer to uncompensated copying of IP may be effective rhetoric
> when trying to sway the public with soundbites, but to the better-informed
> it is likely to simply come off as deceptive or disingenuous. As always,
> whoever establishes their metaphor in the public eyes is in a good position
> to get their favorite laws passed, but such metaphors can be deceiving.
We truly disagree here. I see it as theft and not in a rhetorical sense either.
I wish to sway no-one. It is just my position. I don't particularly like the inference
that I am a tool of the money mongering new world order. Deceptive? You think
I am lying rather than just plain wrong? Ask yourself, what would happen if copyright
was not enforced for music or literary works or software for that matter. Do you think
a big publisher would think twice about printing and selling books or music without
paying the author?? Uncompensated copying?? who's being nieve here. Are you
working for the dot com plunder-go public for a huge bump and then fold the tent crowd?
Do you think this has anything to do with freedom of information? No-one is getting
sued
for un-authorized copying. That is just the overt act. They are being sued because
they are
PROFITING from anothers labor without recompense. If you steal my chicken, hold it
until
it lays an egg and then return the chicken this meets your description of "not theft
because
the original good is still there. You stole my chicken. Don't matter what the clever
rational is.
Disingenuous? quit pussy footing around with the weasel words.
You're sounding like a microprocessor aristocrat who get's ticked off if some-one say's
No, you cannot have that.
Now, what was that favorite law I wanted passed?
Paul
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: effects of mistaken *partial* reuse of a OTP?
Date: Wed, 25 Apr 2001 02:57:56 GMT
<[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> What is the impact on cryptanalysis where two different messages are
> enciphered with a portion of a OTP being mistakenly reused? Eg with
> two OTPs which due to a flaw in production perhaps, have a section in
> common (eg end of one repeated in beginning of next)?
>
> Is the effect simply that the attacker is able to recover those bits
> of the two messages which were encoded with the common section, but
> that the remainder of the two messages are impenetrable, because for
> these bits, the not-in-common bits of each OTP are genuinely one-time?
>
>
> If so then, in practical terms it is possible that mistaken reuse of a
> only a small number of bits (as a proportion of the total message/pad
> length) may be tolerable provided the message material recovered is
> insufficient for the attacker to understand the critical content of
> the meassages?
>
And if you replace 16 xors in DES (by mistake of course) it's completely
broken.
So what?
Tom
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: effects of mistaken *partial* reuse of a OTP?
Date: Tue, 24 Apr 2001 20:01:53 -0700
Assuming that the attacker knows that those 2 portions of the pads were
identical, it will only reveal the information in those areas (and whatever
can be deduced from them). Well that's true when it's an XOR-based OTP,
other forms may reveal more but require more work to do it. The rest of the
information will be as provably secure as before (provided, as you noted,
that it cannot be derived form what leaks).
Joe
<[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> What is the impact on cryptanalysis where two different messages are
> enciphered with a portion of a OTP being mistakenly reused? Eg with
> two OTPs which due to a flaw in production perhaps, have a section in
> common (eg end of one repeated in beginning of next)?
>
> Is the effect simply that the attacker is able to recover those bits
> of the two messages which were encoded with the common section, but
> that the remainder of the two messages are impenetrable, because for
> these bits, the not-in-common bits of each OTP are genuinely one-time?
>
>
> If so then, in practical terms it is possible that mistaken reuse of a
> only a small number of bits (as a proportion of the total message/pad
> length) may be tolerable provided the message material recovered is
> insufficient for the attacker to understand the critical content of
> the meassages?
>
------------------------------
** 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
******************************
