Cryptography-Digest Digest #659, Volume #12 Tue, 12 Sep 00 01:13:01 EDT
Contents:
Re: Scottu19 Broken (Tom St Denis)
Re: Weaknesses in this algorithm? (Patrick Schultz)
Re: RSA Patent -- Were they entitled to it? (Joaquim Southby)
nice simple function (Tom St Denis)
Re: RSA public exponent (Bob Silverman)
Re: RSA public exponent (Ed Pugh)
Re: Getting Started, advice needed (FAQs , yes I read them) ("Douglas A. Gwyn")
Re: Getting Started, advice needed (FAQs , yes I read them) ("Douglas A. Gwyn")
Re: RSA?? ("Douglas A. Gwyn")
Re: RSA public exponent (Ed Pugh)
Re: MIRACL ("Douglas A. Gwyn")
Re: Intel's 1.13 MHZ chip ("Douglas A. Gwyn")
Re: Problem with Tiger hash algorithm and binary files ("Douglas A. Gwyn")
S.I. unit names, off-topic (was re Intel's 1.13 MHZ chip) (David Hopwood)
Re: Camellia, a competitor of AES ? (David Hopwood)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Scottu19 Broken
Date: Tue, 12 Sep 2000 01:06:53 GMT
In article <OZbv5.68998$[EMAIL PROTECTED]>,
"Paul Pires" <[EMAIL PROTECTED]> wrote:
>
> Tim Tyler <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> > Hmm. It's not common to anonymously spread FUD about someone else's
> > technology - and then to subsequently confess (without any sign of
> > duress being applied) that you're actually someone with a known
> > distaste for the author.
> >
> > Oh well, full marks for revealing phreakerboyz' identity, anyway.
>
> He got me too. I could kick myself. Look at the following snip
> out of PB's post.
>
> (
> Oh now I have to give reasons? Nah. NSA likes breaking all crypto
> espescially from fanatics.
>
> P/b
>
> Tom
> )
>
> Not only did he use his signature phrase "Nah", He signed it.
>
> Paul
I really didn't want to offend anyone. I was trying to show how
hurtful DS was behaving. I am sorry if I was rude.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Patrick Schultz <[EMAIL PROTECTED]>
Subject: Re: Weaknesses in this algorithm?
Date: Mon, 11 Sep 2000 18:18:45 -0700
Mark Wooding wrote:
>So, we have a message M, a passphrase P, a random RC4 key K, and a
>one-time pad R. We send
>
> P \xor K, R \xor RC4(K), M \xor R
>
>We immediately calculate
>
> R \xor RC4(K) \xor M \xor R = M \xor RC4(K)
>
>which eliminates the one-time pad. This then is no more secure than
>either RC4 or the passphrase. I consider that the worth of (memorized)
>passphrases as key material is long gone.
Ok, I see the weakness is in the fact that RC4 is just \xoring a
psuedo-random string with the one-time pad. So because the one-time pad is
\xored with two separate things, it is able to be eliminated. But what if
you replaced RC4 with a block cipher? Would this not fix the weakness you
mentioned?
>What was it you were actually trying to acheive?
My main thought was simply that, because every step of the encryption uses
random data, that the cipher text should be statistically random, making it
immune to any attacks based on the statistics of the plaintext.
-Patrick Schultz
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: RSA Patent -- Were they entitled to it?
Date: 12 Sep 2000 01:23:17 GMT
In article <yAAu5.17316$[EMAIL PROTECTED]> Aztech,
[EMAIL PROTECTED] writes:
> it's the same reasons I see the US Navy capturing enigma
>codes 1940's Nazi uboats at the movies rather than the true story of the
>British Navy doing the work way before the US entered the war, I guess we
>all know not to rely on Hollywood for historical accuracies.
>
And we�ve just learned not to rely on your posts for historical accuracy,
either. If your true story starts with the British Navy was "doing the
work" (whatever that means) way before the US entered the war, what do
you say about the Poles during the 1930's?
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: nice simple function
Date: Tue, 12 Sep 2000 01:21:42 GMT
Take the simple function f(x) = a.x + b in GF(2)^8, assuming a, b in GF
(2)^8 and a != 0.
Now if I have a single pair of input/output (i.e one input and one
output) then the function is still impossible to solve since it's
impossible to distinguish from random.
Suppose I have two pairs... uh oh, it's broken. Now let's consider the
extension
f'(x) = c.x + d
to get
f''(x) = f'(f(x)) = f'(a.x + b) = c.(a.x + b) + d = a.c.x + c.b + d
Since c.b and d are constants we can fold them into 'e'. Since a.c is
the same as g = a.c, we get f''(x) = g.x + e. Obviously no more secure
then before. I can't find (a,b,c,d) from random, but I won't need to.
Let's consider the variant
f''(x) = f'(x + f(x)) = f'(x + a.x + b) = c.(x + a.x + b) + d = c.x +
a.c.x + c.b + d
Where again 'c.b' and 'd' can be folded into 'e', but we now have
f''(x) = c.x + a.c.x + e, or simply f''(x) = x.(c + a.c) + e
If I understand my math you cannot chain the function in anyway to make
it more secure. Which makes me ask about a substitution network that
uses it.
Let's consider a parallel substitution network (like safer) where the
entire block is passed thru the function f(x) = a.x + b. Is there no
way to chain the function for multiple rounds such that it's not
algebraically the same?
What about using non-isomorphic operators in the expression? Such as
mixing integer addition with galois field math? Such as
f''(x) = f'(x ++ f(x)) where '++' represents modular integer addition.
We now get f''(x) = f'(x ++ (a.x + b)) = c.(x ++ (a.x + b)) + d = c.x
++ c.(a.x + b) + d = c.x ++ (c.a.x + c.b) + d
>From what I can tell c.x cannot be grouped with c.a.x, which means we
have an output that is a function of 'c' and 'a'. Also that c.b cannot
be grouped with 'd', but since they are not a function of the input can
we let 'b' be zero and just have f''(x) = (c.x ++ c.a.x) + d
Which leads me to f''(x) = (a.x ++ b.x) + c as a new decorrelated
function. (Assuming a, b != 0).
Am I nuts or what? Please comment :-)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: RSA public exponent
Date: Tue, 12 Sep 2000 01:55:25 GMT
In article <[EMAIL PROTECTED]>,
lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote:
<snip>
> Keep in mind that phi(n) and lambda(n) are equivalent for this
purpose,
> because phi(n) and lambda(n) factor into the same primes (albeit
possibly
> with different exponents). Hence to be relatively prime to one is to
> be relatively prime to the other.
Not quite. We have (2, lambda(N)) = 1, whereas (2, phi(N)) = 2.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Ed Pugh)
Subject: Re: RSA public exponent
Date: 12 Sep 2000 02:56:34 GMT
Reply-To: [EMAIL PROTECTED] (Ed Pugh)
Since there are a number of sub-threads following up to my post of last
night, I will follow up directly to that post, instead of any one of
the several individual follow-ups.
I should have mentioned that I did know about and understand the attack to
break A SINGLE SAME "MESSAGE" encrypted to several recipients with the
same small public exponent (but different modulii). I should have also
mentioned this in my first posting in this thread yesterday. (And I
apologise for not making this clear.) I also knew that PGP is not
vulnerable to this attack because a "message" (actually the symmetric
session key) encrypted to several different recipients is changed for
each recipient (by changing the random "salt" that is padded to the
session key), and therefore is not vulnerable to the attack.
However, Bill's statement seemed different. I understood (misunderstood?)
Bill to have said that if one encrypts a number of specially chosen
messages using a single small-exponent public key (i.e. one RSA key
with a known "small" public exponent, e, and normally large modulus,
N), then a secret exponent can be found (which is entirely different
than recovering a single message plaintext).
Again, if I understand what Bill wrote, then this means that any
RSA key with a "small" public exponent can be broken (i.e. the
secret exponent can be found?)
If such an attack were available, then it does not matter whether
PGP or Honest_Ed's_Snake_Oil (tm ;-) was used to generate the key.
An attacker could write her own software to break the RSA key, given
the "small" e and the modulus, N.
So, again, did I understand Bill's statement correctly, or did I
miss something? And if I did undertand correctly, then is 17 a
"small enough" exponent to be vulnerable to this attack?
I ask for forgiveness in advance, if I have misunderstood or
misconstrued anything.
Thanks and regards,
--
Ed Pugh, <[EMAIL PROTECTED]>
Richmond, Ontario, Canada (near Ottawa)
"Bum gall unwaith-hynny oedd, llefain pan ym ganed."
(I was wise once, when I was born I cried - Welsh proverb)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Getting Started, advice needed (FAQs , yes I read them)
Date: Mon, 11 Sep 2000 23:03:18 -0400
Andy C wrote:
> This begs the question - how does one go about
> guessing a "known" plaintext in any reasonable amount of time?
Try a handful of likely things that you could reasonably
expect to be present in the plaintext. For this particular
system you could try "crib dragging", which means trying
each likely piece of plaintext at various offsets within the
ciphertext. You should make these trials in parallel if
possible. As soon as one works (indicated by uncovering
additional plaintext adjacent to the guessed piece), you
can recover the rest of the plaintext by using the effective
key as explained in a previous posting.
As to what to guess, that depends on what you think you
know about the underlying traffic. If it is probably an
order for hospital supplies, try "penicillin". Etc.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Getting Started, advice needed (FAQs , yes I read them)
Date: Mon, 11 Sep 2000 23:08:52 -0400
Andy C wrote:
> Hmm - I did the 2's complement and it worked out rather odd.
> FFFF9A19, ...
Yeah, in 32 bits it does pick up those extra 1 bits.
(I just posted the lowest 16 bits). My guess is that
the algorithm started out in a 16-bit word context and
was later extended to 32 bits without changing the
additive constant. The thing is, addition introduces
some nonlinearity at the GF(2) level, so probably that
was the motivation for doing it in the first place.
However, the system is so easily reversed (as shown in
other posts) that trying to exploit the properties of
the addition of FFFF9A19 is not the easiest way to proceed.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: RSA??
Date: Mon, 11 Sep 2000 23:18:51 -0400
Runu Knips wrote:
> ... Mathematicans believe that RSA is as hard as factoring, ...
Last I heard, it was known that certain classes of keys
enabled cracking of RSA with dramatically less reources
than general factoring algorithms would require, but no
such short-cuts were known for other keys. So the worst
case seems to be "as hard as factoring", and it is up to
the key selector to ensure that "weak keys" are avoided.
------------------------------
From: [EMAIL PROTECTED] (Ed Pugh)
Subject: Re: RSA public exponent
Date: 12 Sep 2000 03:13:46 GMT
Reply-To: [EMAIL PROTECTED] (Ed Pugh)
Mark, thanks for your corrections and keeping me honest.
I want to clarify something, though.
Mark Wooding ([EMAIL PROTECTED]) wrote:
> Ed Pugh <[EMAIL PROTECTED]> wrote:
>> It is (AFAIK) currently believed that factoring N is the easiest way
>> to find the secret exponent of a RSA key. I often wonder, however, if
>> there may be an easier attack available, given the fact that there are
>> infinitely many possible secret exponents.
>
> There is no such attack. Knowing both exponents allows efficient
> factoring of the modulus (you discover a nontrivial square-root of -1).
> Hence, finding a private exponent is as hard as factoring.
Okay. I think I understand this. So let me rephrase the question.
AFAIK, current thought is that the easiest way to break an RSA key
is to factor the modulus to recover the prime factors, p and q, and
then use these with the public exponent, e, to find "the" secret
exponent, d.
However, given that there are Aleph-Null possible values of d available,
I wonder if there might be some, as yet unthought of, method of finding
a value of d WITHOUT first factoring N (i.e. NOT givn the prime factors,
p and q) ?
If ANY such value could be found (not necessarily one of the two or
more values less than N), then can N still be factored given e and
the found value of d? If so, then it would be a simple matter to
continue from there to recover p and q, and then "THE" value of d
(i.e. the one less than lambda(N)) and have the further advantage
(to the attacker) to be able to use CRT to decrypt the target's
messages.
If not, then the attacker could still decrypt the target's messages,
abeit less efficiently, with the found (larger) value of d and the
modulus N, even without knowing p and q.
Does this make sense or am I "smokin' somp'n strange" ?
Thanks and regards,
--
Ed Pugh, <[EMAIL PROTECTED]>
Richmond, Ontario, Canada (near Ottawa)
"Bum gall unwaith-hynny oedd, llefain pan ym ganed."
(I was wise once, when I was born I cried - Welsh proverb)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: MIRACL
Date: Mon, 11 Sep 2000 23:20:15 -0400
Soeren Gammelmark wrote:
> When I try to run the BC32DOIT.BAT to create the
> library I get tons of error messages.
The content of the error messages, especially the first few,
should provide a clue as to what is wrong.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Intel's 1.13 MHZ chip
Date: Mon, 11 Sep 2000 23:26:52 -0400
John Savard wrote:
> Note, though, that ECL has much higher power consumption than CMOS,
> and supports much lower chip densities. (It's worse than bipolar,
> because it gains its speed by not driving its transistors to
> saturation.)
Right. I think there are also fan-out limitations.
> Also, the 1 GHz speed of a microprocessor is for a machine cycle,
> which involves many elementary logic operations. The figure you quote
> may be the speed of individual NAND gates.
The so-called "1GHz" of today's processor specs refers to clock
rate, not operation execution rate. Many modern processors
perform 2 elementary phases of operation per clock cycle; some
older ones took 2 clock cycles per elementary phase of operation.
And of course with instruction pipelines, memory caches, and
multiple processing units operating in parallel, true speed of
executing a real program can be hard to predict.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Problem with Tiger hash algorithm and binary files
Date: Mon, 11 Sep 2000 23:29:29 -0400
He should also open the file in binary mode instead of as a text stream.
------------------------------
Date: Tue, 12 Sep 2000 04:00:57 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: S.I. unit names, off-topic (was re Intel's 1.13 MHZ chip)
=====BEGIN PGP SIGNED MESSAGE=====
John Savard wrote:
> [...] It does point out correct usage of unit abbreviations within the
> Systeme Internationale:
>
> the multiplier symbols, which include case as significant
>
> multiply divide
> T - tera p - pico 1 000 000 000 000
> G - giga n - nano 1 000 000 000
> M - mega (mu) - micro 1 000 000
> K - kilo m - milli 1 000
Not quite; the correct symbol for *1000 is, somewhat inconsistently,
lowercase k (e.g. kg, km, kHz).
> H - hecto c - centi 100
> D - deca d - deci 10
>
> precede the unit abbreviation, which, in the case of Hertz (formerly,
> in English, c.p.s. or cycles per second), is Hz.
To be even more horribly pedantic, the name of the unit is hertz
(lowercase h), which is indeed abbreviated Hz. Despite common usage,
this is the correct rule for all S.I. units named after people, e.g.
newton -> N, siemens -> S, henry -> H, pascal -> Pa, etc.
- --
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
iQEVAwUBObvrWTkCAxeYt5gVAQEYcAf/VZm0NW3aOaQLwKc+i5cwh9W7Ehbtt5eH
hehnJh60Ap69BAIb2c80Enmj+lQabM6JrJKkr1aSd8CyCLPiQZfzB+crAA62iFao
hkrw7qOh12Hpox0Dc8+G1L70jHomxBcm6w2TkK5a4WF4o6K+c8uRAHS1Kn6zS2r3
IF56sBPJwb5QbqtX6PsJIaBJGBdUEQ1VXdW9LfEYsdEtbYFLekVOYkZMbu/eGEss
o4qfeaFlRUaOb2fuifEx5lJiSl9w9dQkvp0801JY51hSSqPDLqV69GSMghTuglgM
JTdv5LSxWzg5FU8DhVZUdB6eePhksOf4qCXrv9F4Kz1CLtFvjGAmPg==
=AV+j
=====END PGP SIGNATURE=====
------------------------------
Date: Tue, 12 Sep 2000 04:36:38 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Camellia, a competitor of AES ?
=====BEGIN PGP SIGNED MESSAGE=====
David A Molnar wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > NTT and Mitsubishi will propose Camellia in response to
> > calls for contributions from ISO/IEC JTC 1/SC27 and are
> > aiming at adoption as a international standard.
>
> This is nice, but does it tell us whether Camellia will be released to the
> public domain ? i.e. does the ISO require standardized algorithms to be
> unpatented? (it seems not, since previous ISO standards included RSA, but
> I'm not familiar with this process).
I notice that a specification of Camellia has been published as an Internet
Draft (http://www.ietf.org/internet-drafts/draft-nakajima-camellia-00.txt),
but with the following rider:
This document is an Internet-Draft and is NOT offered in accordance
with Section 10 of RFC2026, and the author does not provide the IETF
with any rights other than to publish as an Internet-Draft.
Section 10 of RFC 2026 is not optional! (It requires all documents that
are part of the Internet Standards Process, including drafts, to describe
any intellectual property claims known to the authors, and guarantees that
the document will be freely available.) I'm surprised it was allowed to
be published with this condition. If it was published as an RFC in that
form, I would certainly consider lodging a formal objection.
In any case, there are patent applications relating to Camellia:
Mitsubishi Electric Corporation (Mitsubishi Electric) and Nippon
Telegraph and Telephone Corporation (NTT) have filed patent
applications on the techniques used in Camellia. For more
information, please contact at [EMAIL PROTECTED] and/or
[EMAIL PROTECTED]
- --
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
iQEVAwUBOb2kmzkCAxeYt5gVAQFhzgf+OFhmC3TTyFStPdF5c5YoQW66jssavHgw
V5yBH0TMMjUbnKMoDUk0CcjwAKVK9S0abphxnnRwModk+kFE9XOPQOJQ6uGqK/os
QjXDn9GLi2QHGUKQLCIBjjKjl+z82yE2Ffxp+W1gSwNxWKWh9+2nyeYsBS4/9VmO
2LdxrH+eVQ5RCw7eqHQuq9RqcK66/c28lqMgOnvi7ghl7pXdftuLVJcMQZ7Ywhbx
VbmJsLrI+v059h86EfssN0IAc4QUd2Zy3bkkUEeCeKYuY0GuBVXDQMJmMIMn6dyq
pPTQW6F8jUIQN8J9Vp5EF9C4jAz+mMJoVjYJxO+Z/ebF3ELAerWSvQ==
=a6+E
=====END PGP SIGNATURE=====
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
