Cryptography-Digest Digest #210, Volume #14 Sun, 22 Apr 01 20:13:01 EDT
Contents:
Re: OTP WAS BROKEN!!! ("Tom St Denis")
Re: OTP WAS BROKEN!!! (newbie)
Re: Delta patching of encrypted data (David Wagner)
Re: OTP WAS BROKEN!!! (newbie)
Re: OTP WAS BROKEN!!! ("Tom St Denis")
Re: OTP WAS BROKEN!!! ("Tom St Denis")
research on polymorphic crypto/Best Possible Privacy? ("Shea J. Hawes")
Re: keys and random (David Hopwood)
Re: PK Algorithm Idea (David Hopwood)
Re: patent this and patent that (David Hopwood)
Re: Clarification - Re: Factoring.... (David Hopwood)
Re: OTP WAS BROKEN!!! (Mathew Hendry)
Re: OTP WAS BROKEN!!! (newbie)
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Sun, 22 Apr 2001 23:16:35 GMT
"newbie" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> It is not an answer F### off.
> It is an insult. I'm not going to insult you, because I'm polite. You
> are simply lying. I never said what you are claiming. I did not talk
> about non-random.
>
> Thank you Sir Smart.
WTF. OTPs are based on random strings of key bits. Anything else and it's
not an OTP. Look at the subject of this thread.
Tom
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Sun, 22 Apr 2001 19:17:03 -0300
Let me just say that :
If you re-use OTP, it is then easy to break it.
I suppose a key k'.
I use this key to encippher a text that I know for sure.
C = P Xor k
C' = P' Xor k'
If k' = k, k' Xor k = 0 that mean that I re-used the key k to encipher
C'. It is like if I reuse OTP twice.
The solution is easy. And P is text that have a sense.
But, If k' is different from k => C' Xor C = (P Xor k) Xor (P' Xor k') =
(k' Xor k) Xor (p Xor P')
I know P' and I do know P and k.
C' Xor C Xor P' = P Xor ( k Xor K')
I know what C' Xor C Xor P'.
I know that k' Xor k is random, It is like If I have new random key "z"
C' Xor C Xor P' = P Xor z
The probability that P Xor z have a sense is infinitesimal.
How I select my messages?
Using a criteria of "sense".
If k'=k I'm sure that the result of C' Xor C Xor P' is a text that have
a sense and that is nothing more than P. OTP is broken.
If k' is different from k, I'm quite sure because of randomness of z =
k' Xor K is a bit-string that does not have a sense. The probability
that any text Xored With random give you as result a bit-string that
have a sense is infinitesimal.
You have now the proof that OTP could be broken.
Alexis Machado wrote:
>
> "newbie" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > OTP was broken!
> > It is not a joke.
> >
> > Let encipher with truly random key a message M.
> > M is a plaintext
> > M =( M1 M2 M3 .... Mn)
> > K is a Keystream
> > K = ( K1 K2 K3......Kn)
> > C is a Ciphertext
> > C = ( C1 C2 C3 .... Cn)
> > ___________________________
> >
> > What I know before breaking is C.
> >
> > What I could know using extra-information is the specific langugage used
> > in my ciphertext
> > Sample : military communication. If I know that I can still assign a
> > high probability to occur to
> > all the words and and sentences used by militaries in their mails.
> > So I'm going to use a specific database to break my ciphertext.
> > I'm going to show you that even I have not extra-information, it makes
> > my breaking more difficult but not impossible.
> [snip]
>
> Hi,
>
> In my previous reply to your post "OTP breaking strategy", I suggested a
> mathematical argument against your claim. Maybe the reasoning was not clear
> (and with some errors). So, I will try for the last time, I promise :-)
>
> As you stated
>
> C = M xor K
>
> Let
> 1) Ai be the bit i of a text A.
> 2) P(Ai) be the probability of "Ai = 1".
> 3) 0 <= P(Ai) <= 1
>
> If the attacker can't guess anything about Ki, P(Ki) = 1/2.
> Let's find the relation between P(Ci) and P(Mi) :
>
> P(Mi) = P(Ci xor Ki)
> = P(Ci or Ki) - P(Ci and Ki)
> = P(Ci) + P(Ki) - P(Ci and Ki) - P(Ci and Ki)
> = P(Ci) + P(Ki) - 2 * P(Ci) * P(Ki)
> = P(Ci) + 1/2 - 2 * P(Ci) * 1/2
> = P(Ci) + 1/2 - P(Ci)
> = 1/2
>
> Note: Starting from P(Ki) = P(Ci xor Mi) we get the same result.
>
> Hence, P(Mi) and P(Ci) are unrelated and you can't say nothing about one
> based on the other.
>
> If K is reused, the attacker may guess something about Ki by analyzing the
> plaintexts xor. In this case, P(Ki) is not 1/2 and we have a relation
> between P(Mi) and P(Ci).
>
> Alexis
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Delta patching of encrypted data
Date: 22 Apr 2001 23:22:31 GMT
Benjamin Goldberg wrote:
>Let's call the encryption operations PFB() and CBC() (just cause cbc is
>more well known than iapm).
>
>file = CBC(k2, IV, PFB(k1, pt)) == what is stored on disk.
>x = CBC^-1(k2, file)
>x' = applypatch(x, patch)
>IV' = new unique random string.
>file' = CBC(k2, IV', x') == what is stored on disk.
But once again, this requires re-writing the entire ciphertext.
The original poster asked for a way to avoid this.
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Sun, 22 Apr 2001 19:20:43 -0300
I knew it.
Do not be skeptical please.
Just try to understand my idea.
Please.
It is based on the simulated re-use of OTP.
If I reuse twice OTP you can break it for sure.
That is the trick that I used.
It is very simple.
Mark G Wolf wrote:
>
> > Did you read what I wrote?
>
> To be honest, no not all of it; simply because I'm sure you can't break a
> random cipher stream if used "properly". But there are instructive ideas in
> your arguments. I myself do have some questions about cracking OTP's
> assuming less than perfect randomness. One question is what is the
> relationship between message density and the randomness of the cipher
> stream? Can you make up for "lack" of randomness with greater diffusion,
> and what is the mathematical relationship? Then there is the question of
> time value of information. You might be able to break a cipher, but will it
> be worth anything by the time you do? Closely related to that question is
> relative computational power; specifically, what is the relationship between
> less than "perfect" randomness and difference in relative computational
> strength between the sender/receiver and adversary.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Sun, 22 Apr 2001 23:33:26 GMT
"newbie" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Let me just say that :
>
> If you re-use OTP, it is then easy to break it.
If you reuse the pad it's not an OTP. Thus your subject line is misleading.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Sun, 22 Apr 2001 23:33:52 GMT
"newbie" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I knew it.
> Do not be skeptical please.
> Just try to understand my idea.
> Please.
>
> It is based on the simulated re-use of OTP.
> If I reuse twice OTP you can break it for sure.
> That is the trick that I used.
> It is very simple.
if you use the pad more than once it's not an OTP. Check your subject line
it's misleading.
Tom
------------------------------
From: "Shea J. Hawes" <[EMAIL PROTECTED]>
Subject: research on polymorphic crypto/Best Possible Privacy?
Date: Sun, 22 Apr 2001 16:36:59 -0700
Reply-To: [EMAIL PROTECTED]
I'm looking for research that anyone may have done regarding the product
Best Possible Privacy. The underlying technology is described as a
polymorphic encryption scheme. There is a description of the algorithm
at www.identification.de/crypto/descript.html with a related site
selling the product at www.ciphers.de/bpp. I have searched for other
references to either of these pages and found nothing so far. I have
read the snake oil faq and this seems to fall into that category but I
am not an expert so I turn to those of you who are.
Shea Hawes
------------------------------
Date: Mon, 23 Apr 2001 00:16:07 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Re: keys and random
=====BEGIN PGP SIGNED MESSAGE=====
David Wagner wrote:
> Mark Wooding wrote:
> >There are some sly active attacks against Diffie-Hellman exchanges and
> >similar which force values into different subgroups. You resist these
> >attacks by (a) noticing when something is in the trivial subgroup (1,
> >-1) and (b) making sure that it doesn't matter when this happens because
> >all the other subgroups are at least as difficult as your main one
> >anyway.
>
> I agree with your first statement, but I'd like to see some
> further evidence for the second one. What if I replace g^x
> (in the subgroup) by - g^x? This won't be detected by your
> measures, but I can easily imagine using it to attack a protocol.
> (For instance, suppose the receiver computes (g^x)^y, where y
> is a long-term secret. Then the resulting key exchange will
> succeed iff y is even, potentially revealing one bit of
> information on y per key exchange.)
However, it is always the lowest bit of y, not one distinct bit of
information per key exchange.
There are at least three ways of preventing any information at all
from being leaked:
1. Include a representation of the ephemeral public key (g^x) in
the input to the key derivation function, so that the key
exchange will fail whenever the sender and receiver disagree
on what this key is. DHAES uses this method, for example.
2. Sign and verify the transmitted ephemeral public keys. (However,
note that this is not always sufficient, since the attacker may
be the authenticated sender. Whether it is sufficient depends on
the specific protocol, and which keys are reused.)
3. Use cofactor exponentiation with a cofactor of 2 (i.e. double
the private exponents, and if it is required to maintain
compatibility with standard DH, also square the public keys).
Interestingly, some editing of the P1363a draft standard has
managed to break DL/ECIES (which is based on DHAES) by removing
the ephemeral public key from the KDF input, *and* making the
subgroup check optional (even the partial check that 2 <= g^x <= p-2
is optional, and note that P1363a does not require either Lim-Lee
or Germain primes). I'm currently trying to convince the working
group to fix this.
> It seems to me that it would be prudent to check that all
> received values that are supposed to be in the subgroup are
> indeed in the subgroup. This can be done by checking that
> X = g^x is not 1, and that X^q = 1 mod p, if q is prime.
The disadvantage of this is that it requires an extra exponentiation
(it is possible to combine the two exponentiations done by the
receiver, but that is more complicated, and still has an overhead
of about 30%). Using a Lim-Lee prime means that no additional
exponentiations are required, for most DH-based protocols.
(There are exceptions, though - for example SRP-3 does require a
Germain prime.)
- --
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
iQEVAwUBOtsaTzkCAxeYt5gVAQF/BQf/dPLFZFN8Pds85R8UFogGyVkI/rGXSfar
BuYhRrMDeQiZF8nP84QdcZrJjToMZ3a8BrQIENSxvj5fm388dTdEjv9GCii0/oPo
moV84RrakusMAqbDPBx40W+XWJapYK8XNeBmoFVXHvoFu+Lida4MPjf3OgHkhzcM
61L6bEv13TQSIHU0Q1L5JQjAAcqjj2/RN1ZDeop7eOfD79h04H4GWt6SU+XBC8oz
efiNyzgdHrL+lr4qjLCl9judNM+ESlYQL2iKq4VfQ0U9Qnr8K6YE0WnIrE6llhUX
VUOea0zHS8FvcIADvkAFaXoTDz/miSUE5lQHkcecfIrZroiP74LCYg==
=eHY9
=====END PGP SIGNATURE=====
------------------------------
Date: Mon, 23 Apr 2001 00:16:15 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Re: PK Algorithm Idea
=====BEGIN PGP SIGNED MESSAGE=====
Tom St Denis wrote:
> Has anyone considered a hybrid DH-RSA system?
Yes, a system similar to the one you described (with some additional
constraints) was proposed in:
K. S. McCurley,
"A key distribution system equivalent to factoring,"
Journal of Cryptology, 1 (1988), pp. 95-105.
and proven as secure as the harder of finding discrete logs in GF(p)
and GF(q), and factoring pq. Also see section 3.8 of HAC, and the
following paper if you can find it:
Z. Schmuely,
"Composite Diffie-Hellman public key generating systems are hard
to break,"
Technical Report #356, TECHNION - Israel Institute of Technology,
Computer Science Department, 1985.
I suspect that one reason why composite DH isn't commonly used, is that
for taking discrete logs in p and q to be hard, p and q have to each be
about as long as an RSA or DH modulus would be. So, in order for this
to actually result in a cryptosystem that is at least as hard as
factoring and taking discrete logs, the key length has to be doubled
(and hence the encryption/decryption times are multiplied by 8, assuming
full length exponents), relative to DH over GF(p).
In other posts, you wrote:
> Why not use the set of rationals (i.e a/b where a and b are int Z
> and b != 0) in say DH? Basically you pick g = a/b and perform DH
> like normal but all your numbers are in a/b (except the exponent).
and
> You find a prime p (preferable a s.g prime) Then you make up a RxR
> matrix which is a generator in Zp^R space (somehow). Then you perform
> DH like normal using matrices.
Both of these are no harder (up to a constant factor) than standard DH.
- --
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
iQEVAwUBOts3ozkCAxeYt5gVAQFxKgf/d0FYG77RnEqgsR1hVQkcydw6oO66RJfH
T5XFdywF2igGOvAlpMZ1g/qwtE7MqSdxddp5uOg/gudkGgKG37I5Q7OKRf/VHyqh
LKDiXzhQG7TM65OWfNN/PNBXNwy3yZZoSUhAAuFKaNPWsj870PAw5EY6PAwBwP1u
CXL95ryCRhu00eVmACI71A1EQrOpQqwN1gAsWKxZMyy/IARQFgr6TB+HddGwWNUm
CTmvY8wtq3hOx3C569ZbfOsf4yi0DNa9uIWPrSFA6XPhY5OWcl6gPELXYP8tT/Tm
lrrIWwhsnKS+Snmd44/41ATBS4tMJd2N+Yuv2AHtX9vyo6Cv3ZrGCQ==
=Cyqf
=====END PGP SIGNATURE=====
------------------------------
Date: Mon, 23 Apr 2001 00:16:21 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Re: patent this and patent that
=====BEGIN PGP SIGNED MESSAGE=====
Ben Hamilton wrote:
> "Tom St Denis" <[EMAIL PROTECTED]> wrote:
> > When it boils down to it I am penalized because I am younger... I could
> > have thought of those ideas given the time and need. [...]
>
> Your younger. So what.
>
> They were once yonger too.
>
> They had to deal with prior art as well.
>
> Expand on the knowledge that is there. Read the patents, understand them,
Have you actually ever tried to do that? Patents are not written to be
understandable. There is no comparison between the intelligibility of
a paper describing an idea (even a badly written paper!) and a
corresponding patent. Also, the search facilities available for patents
are totally inadequate; despite the severe limitations of web search
engines, a web search will typically give more useful information than a
patent search, at least in the field of computer science.
> figure out how to get around them, make them invalid, find a method
> that is better. Isn't that the inventor/invovator method? (one of).
No. Innovation in computer science proceeds despite patents, not by
reading and improving on them (and the more I look at the effect of
patents in other fields, the more I am convinced that this is true more
generally).
- --
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
iQEVAwUBOttLLTkCAxeYt5gVAQFx7wgAlMhBGbBKZVcWPL+aG77yDMEx9CJAfJWo
K6URoj7vNv4qQv/GYqDl/F3uNDMp7K6vcC59KM0yjjx6n4GTSOzHzNZbuaOeCbd8
Fouai+i4QF2L4D9IwfTBu4o/LusCm7DwrGUgSvQqyP/g44gxgoKndkQwWnT8TPDg
7Z0U+hIcxkolVGml49u2Rh7UJ2Fe+CyJPhXTudr41v1gKwZ06SSnmPxfPsvp+5EF
Z2CwHEAUTd+wqSEZyoS448szSknqncTNXHrDwy/33JGj3I6B/Vm1UI5YKDV/jyxG
97ehd65kYwLDOkgT4VCqrKpwJ1eDEvYODsWNHSaX7XDmiUrfDB6BBg==
=aU7K
=====END PGP SIGNATURE=====
------------------------------
Date: Mon, 23 Apr 2001 00:16:48 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Re: Clarification - Re: Factoring....
=====BEGIN PGP SIGNED MESSAGE=====
Jeffrey Walton wrote:
> Sorry, I received a personal response to using 'modulo p'. Please allow
> me repost:
>
> After I posted, I saw the error. n = p*q. Finding the quadratic
> residue would occur in modulo n.
>
> If I recall, there are basically n/2 quadratic residues, and n/2 non
> quadratic residues.
(n-1)/2 of each, actually.
> Also, in n = p*q, I don't want trivial quadratic residues. For example:
> p = 3*5.
> 1^2 = 1 mod 15 and 14^2 = 1 mod 15. These are trivial. However, 4^2 = 1
> mod 15 is not trivial. (Of course, understand = to be congruence).
>
> So, what is the complexity of an algorithm that finds the square root of
> a quadratic residue, after finding a non trivial quadratic residue.
If p and q are unknown, first factor n. Then apply Algorithm 3.44 of [HAC],
which has time complexity O((lg n)^3).
[HAC says "O((lg p)^3)", without any further qualification. That seems
to be an error, since q could be much larger than p.]
> My "gut instinct" tells me I will find a non trivial quadratic residue
> quickly. I'm trying to define the hueristic "quickly".
Assume p and q are distinct odd primes. Then an element a of Z*_n is a
quadratic residue iff J(a, n) = 1 and J(a, p) = 1 (see [HAC] Algorithm
2.149 and Section 3.4). Since a random element has probability 1/2 of being
a quadratic residue, and computing a Jacobi symbol is O((lg n)^2), then the
expected time complexity of finding a Q.R. by random search (when p and q
are known) is also O((lg n)^2).
If p and q are unknown, there is no known method to feasibly determine
whether a random element is a Q.R. with probability greater than chance
(this is the Quadratic Residuosity Problem). It has not been proven that
there can be no such method, though.
[HAC] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone,
Handbook of Applied Cryptography,
CRC Press series on discrete mathematics and its applications, 1997.
ISBN 0-8493-8523-7.
Chapter 2: http://www.cacr.math.uwaterloo.ca/hac/about/chap2.pdf or .ps
Chapter 3: http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf or .ps
- --
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
iQEVAwUBOtuutzkCAxeYt5gVAQF88wgApTD6T7X/PcXNgSBFNgFI5aaYOCIlGiR/
qzLNQZ2fNparCR7ajq+qzwQOokmzevfpAjxlBgKzjVOC7/KCCXQ6BBuy1T2Wpb0f
1pasqvHBw2qSocC/fv8yb7ijiSh6HtSD050YY25fjGR6cJXPOVS3L8FMyN4CqCfS
iZahfL4oSucKWcaFVBfrZ0SIfR1GFUizxsAuiYZWXiaoyOwn3Ym02XZTLz/04nCW
zLjm9klaG3HCPiFi1a5fX4Y5MBKMmS6gPmb6OXvCcRM8M5fWuH2hr+hMWAAr3ueG
PpOC9DXE6Ze5T5kH+J67nDTDZ9qvf6XBO9zB93HisyMowcEDOI8fnQ==
=Pyj7
=====END PGP SIGNATURE=====
------------------------------
From: Mathew Hendry <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Mon, 23 Apr 2001 00:49:31 +0100
On Sun, 22 Apr 2001 18:46:45 -0300, newbie <[EMAIL PROTECTED]> wrote:
>> You say "well it looks non-random so it must be the solution".
>> You fail to recognize that the number of non-random plaintexts is
>> astronomical....
>
>THE NUMBER OF MESSAGES WHICH HAVE A SENSE IS INFINITESIMAL COMPARING TO
>THOSE WHICH DOES NOT HAVE A SENSE!!!!!!!!!!!!!!!!!!!
But it is still enormous. And you have no way of choosing among that huge
number.
To take a tiny example, here is a three character OTP ciphertext
akh
a few possible plaintexts would be
oui
non
yes
no!
yay
nay
aye
not
Choose between them.
-- Mat.
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Sun, 22 Apr 2001 19:54:09 -0300
xxx
xyz
:a?
izx
ixz
oqx
etc...
They are still enormous.
Mathew Hendry wrote:
>
> On Sun, 22 Apr 2001 18:46:45 -0300, newbie <[EMAIL PROTECTED]> wrote:
>
> >> You say "well it looks non-random so it must be the solution".
> >> You fail to recognize that the number of non-random plaintexts is
> >> astronomical....
> >
> >THE NUMBER OF MESSAGES WHICH HAVE A SENSE IS INFINITESIMAL COMPARING TO
> >THOSE WHICH DOES NOT HAVE A SENSE!!!!!!!!!!!!!!!!!!!
>
> But it is still enormous. And you have no way of choosing among that huge
> number.
>
> To take a tiny example, here is a three character OTP ciphertext
>
> akh
>
> a few possible plaintexts would be
>
> oui
> non
> yes
> no!
> yay
> nay
> aye
> not
>
> Choose between them.
>
> -- Mat.
------------------------------
** 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
******************************
