Cryptography-Digest Digest #929, Volume #11 Sat, 3 Jun 00 06:13:01 EDT
Contents:
Re: Is OTP unbreakable?/Station-Station (Greg)
Re: Is OTP unbreakable?/Station-Station (Greg)
Re: Is OTP unbreakable?/Station-Station (Greg)
XTR independent benchmarks (Wei Dai)
Re: PSS and PSSR patent status (was Re: XTR) (David A Molnar)
Re: Self Shrinking LFSR (Scott Nelson)
Re: Cipher design a fading field? (David A Molnar)
Re: TC3 Update (Gregory G Rose)
Re: No-Key Encryption (Mok-Kong Shen)
Re: No-Key Encryption (Mok-Kong Shen)
Re: Pollard's algorithm for computing discrete logs (Mok-Kong Shen)
Re: Good ways to test. (Mok-Kong Shen)
Re: Good ways to test. (Mok-Kong Shen)
Quantum computers (DrArm)
Re: Pollard's algorithm for computing discrete logs (Quisquater)
Re: Anti-Evidence Eliminator messages, have they reached a burn-out po (jungle)
Re: Cipher design a fading field? (Mok-Kong Shen)
Re: Cipher design a fading field? (Mok-Kong Shen)
Re: C implementation of CAST-256? (David Crick)
Re: Anti-Evidence Eliminator messages, have they reached a burn-out po (jungle)
Re: C implementation of CAST-256? (David Crick)
----------------------------------------------------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Is OTP unbreakable?/Station-Station
Date: Sat, 03 Jun 2000 04:34:48 GMT
> I have a question about your method as described. How do you
> handle a missing message (iether random transmission error or
> a man-in-the-middle adding to or removing from your message
> stream?) You have your OTP, and so does your recipient, but
> he is trying to decrypt with a key that you have already
> destroyed. How do you get him to jump ahead and resync to you?
Why is this an issue. Pick one 256 bit value as the resync code
and when the other side sees it they know to begin receiving.
Then the question is, how are you sure it was not noise or a lucky
attack? Well, noise maybe, but not really. Attack- not really either.
If you want, make the resync 1024 bits long and you really can't
have a failure to resync properly because the world will come to
and end before that one value is accidentally or maliciously produced
in which case, who cares?
--
There is only one gun law on the books- the second amendment.
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Is OTP unbreakable?/Station-Station
Date: Sat, 03 Jun 2000 04:36:41 GMT
> Nobody cares about your personal messages, but even so, there is a
> some degree of predictability to them, which means that we can
> *guess a portion* correctly in some cases. For example, you're
> quoting postings to which you respond using a standard format,
> and we therefore have a good chance of guessing the first hundred
> or so characters of your plaintext.
Not if there was a continuous stream of noise to confuse where the
messages began.
--
There is only one gun law on the books- the second amendment.
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Is OTP unbreakable?/Station-Station
Date: Sat, 03 Jun 2000 04:49:43 GMT
> I have a question about your method as described. How do you
> handle a missing message (iether random transmission error or
> a man-in-the-middle adding to or removing from your message
> stream?) You have your OTP, and so does your recipient, but
> he is trying to decrypt with a key that you have already
> destroyed. How do you get him to jump ahead and resync to you?
ooops I did not read the question correctly so ignore my previous
answer. Let me try again.
The receiver reads data from the stream and decrypts the data.
The receiver is looking for one of two things to resync:
- ignore bytes which are all zeroes
- start bit patter which can be as long as you want
(I would advocate 256 or larger to ensure random
events do not appear as a start event.)
Zeroes are interpreted as throw aways and anything other than
a start is interpreted as true noise that can initiate a break,
which would result in an index transmitted in the clear to
resync the two sides again.
The cipher stream would not be able to yield when the message
started, even if a resync took place because a resync could have
any number of zeroes sent before the message. Without knowing
how many zeroes are sent, you have no way of knowing how long the
real message is or where it started.
Does this make sense?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Wei Dai <[EMAIL PROTECTED]>
Subject: XTR independent benchmarks
Date: Fri, 2 Jun 2000 23:53:39 -0700
I decided to do a quick XTR implementation to see how well the claims of low
computational overhead hold up. Here are the results (time in milliseconds,
numbers in parentheses are the claims in the XTR paper):
RSA 1024 Encryption 0.57
RSA 1024 Decryption 19.44 (40)
XTR-DH 171 Key-Pair Generation 8.35 (11)
XTR-DH 171 Agreement 17.20*
XTR-DH 342 Key-Pair Generation 30.97
XTR-DH 342 Agreement 62.63
DH 1024 Key-Pair Generation 10.43
DH 1024 Key-Pair Generation with precomputation 4.19
DH 1024 Agreement 10.53
DH 2048 Key-Pair Generation 46.91
DH 2048 Key-Pair Generation with precomputation 14.10
DH 2048 Agreement 47.82
LUCDIF 512 Key-Pair Generation 5.21
LUCDIF 512 Agreement 6.96
LUCDIF 1024 Key-Pair Generation 22.47
LUCDIF 1024 Agreement 27.16
EC over GF(p) 168 DHC 13.71
EC over GF(p) 168 DHC Key-Pair Generation with precomputation 6.86
EC over GF(p) 168 DHC Agreement 14.18
*Key agreement includes time for either co-factor multiplication or validating
the counterparty's public key to prevent subgroup attacks.
This was done using C++ code compiled with MSVC 6.0, with only two assembly
routines for adding and subtracting multiple precision integers. The benchmark
program ran on a 450MHz Intel Celeron processor with Microsoft Windows 2000.
Notice that my XTR implementation is actually faster than the XTR paper claims,
but it's advantage compared to RSA is smaller. (The paper's numbers are based
on a 450MHz Pentium II which is virtually identical to the 450MHz Celeron.) One
reason may be that my large integer code is optimized for bit lengths that are
powers of 2, so that XTR-DH 171 is actually doing 256-bit arithmetic (this also
applies to EC 168).
If you noticed that the RSA and other numbers are lower than on my benchmarks
web page, it's because additional code optimizations have been made in Crypto++
since the last time the benchmarks page was updated. The optimizations as well
as XTR implementation will be included in the next version of Crypto++. Send me
an email if you wish to examine the XTR code in the mean time.
Other observations:
- XTR suffers if precomputation is possible or prevention of subgroup attacks
is needed, otherwise it compares favorably against ECC over GF(p).
- XTR is actually slower than LUCDIF in this test, but again this may be due to
the optimization choices in Crypto++.
- I stand by my earlier remark that XTR's advantages (where they exist) are
rather marginal.
--
"You want me to speed up your RSA implementation? But if you use PGP a
decryption only takes a few seconds. Isn't that good enough?"
-me during a job interview circa 1995
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: PSS and PSSR patent status (was Re: XTR)
Date: 3 Jun 2000 06:49:46 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
> PSS as standardised in P1363 is royalty-free; PSSR (the message recovery
> variant) is not.
Thanks for pointing that out! The only nitpick I have is over what exactly
constitutes a "conforming implementation", but probably I can find that on
the site.
> FREELY license any conforming implementation of PSS as a technique
> for achieving a digital signature with appendix. No registration fee
> or other administrative procedure will be required.
-David
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Self Shrinking LFSR
Reply-To: [EMAIL PROTECTED]
Date: Sat, 03 Jun 2000 07:34:40 GMT
On Fri, 02 Jun 2000 Mike Rosing <[EMAIL PROTECTED]> wrote:
>Scott Nelson wrote:
>> You may be right.
>> I've been unable to locate a definitive reference for
>> the meanings of primitive and irreducible, so can nether confirm
>> nor deny it. However, it's clear that to be maximal
>> length a polynomial must be both primitive and irreducible.
>
>In another thread Terry Ritter pointed at his glossary that gives
>a consise definition. Irreducible is a prime polynomial - it has no
>factors. Primitive is a maximal order polynomial, it is also
>irreducible.
>The order of a polynomial (P) can be found by taking any other
>polynomial of
>lesser degree (X) times itself until you get 1. That is, X^m mod P = 1
>means P has order m. When m = p^n-1, it is maximal length.
>
>> It may take a /bit/ longer than a couple of weeks to brute
>> force the dense 32 bit ML sequences.
>
>It's not that hard. You can easily find if a polynomial is irreducible.
>To test if it's primitive, you need to see if x^(factors of p^n-1) = 1
>mod P. If so, it's not primitive.
I guess this is another one of those mistaken definition things.
I always thought upper division math courses were considered
"hard", so solving a problem by using finite field mathematics
should also be considered "hard" even though it's pretty easy
to do _once you understand finite field mathematics_.
>For p == 2, you only need 9 billion
>checks for brute force, so I'd think the whole thing can be done in
>a day on a reasonable PC. There are faster ways to do this, a few
>months
>ago someone posted the URL for a paper that showed some efficient
>methods
>for checking if polynomials are primitive.
>
Even ftp://helsbreth.org/pub/helsbret/random/lfsr_s.exe
(my program) which uses a less sophisticated technique,
took less than a day to find all the 32 bit sequences.
However, I wouldn't classify either method as "brute force"
so I think my original claim of more than a couple of weeks
_to brute force_ all the "dense" 32 bit sequences is still correct.
The best link I've found for those who can handle finite
field mathematics is http://ks.fernuni-hagen.de/~rieke/primitiv/
I estimate Andreas Rieke's method would take far less than
an hour to find all 32 bit sequences.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: 3 Jun 2000 07:36:44 GMT
[EMAIL PROTECTED] wrote:
> Why else is a new cipher required? Will AES be the -final- cipher?
Every cipher either creates a new assumption that it is secure or
relies on a previous set of assumptions. This includes the one-time pad,
which makes at least the assumptions that the key involved is
unguessable, as long as the plaintext, and secret. Once you move into the
computationally-bounded setting, the assumptions become hairier -- and
very difficult to compare.
Quick : which is better, the strong RSA assumption or the dependent
RSA assumption? "MARS is secure" or "RC6 is secure" ? factoring or
discrete log or diffie hellman or decisional diffie hellman or hash diffie
hellman? security through long-term analysis or constantly changing cipher
stacks?
People can and do disagree about which assumptions they want to make. I
expect this to continue. By itself, this would drive the development of
new ciphers. Combined with the need for performance pointed out in this
thread by David Wagner (and elsewhere by Bruce Schneier), and the need to
react to new developments in cryptanlysis, I think new ciphers will be
designed for some time.
Terry Ritter referred to the subfield of "provable security." I agree that
the name is misleading, especially if you don't have a semester or two
to spend studying it! A better way to talk about it might be
"clarifying" or "refining" the assumptions we make in cryptography --
trying to work out what exactly it is we need and don't need to do
encryption, signatures, and whatever else. It makes us think about and
state the assumptions we're making when we design a system.
I think that makes it valuable, even if it's not the final answer in
cryptography. Then again, I'm biased because I tend to prefer thinking
about public-key cryptography and protocols to symmetric ciphers. The
method of "provable security" has had some successes there, which don't
seem to be replicated in the symmetric world AFAIK.
You asked about cipher design, but I'll just point out that even if the
perfect cipher suite came to us tomorrow, we'd still have a dozen
different ways to screw up while using it to exchange data. Then we'd have
a hundred other ways to use it for wild and wonderful things like
multiparty computation, online voting, subliminal-free channels, and
anonymous remailers. Probably a thousand ways to use it "correctly" but in
a way contrary to expectations such that people get hurt. Cipher design
gets a lot of press, but it's not the last word in crypto.
-dmolnar
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: TC3 Update
Date: 3 Jun 2000 01:19:46 -0700
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>Clearly, GF(8) is not a field. See, e.g.:
>
> http://www.io.com/~ritter/GLOSSARY.HTM#Field
Not like Terry to make such a mistake. GF(2^3) is
GF(8) and it is indeed a field. The problem is
that the field operators are polynomial addition
(xor) and polynomial modular multiplication with a
primitivemodulus polynomial of degree 3. The operators are
*not* integer modular addition and multiplication,
which operations form a ring not a field. In
otherwords, he's right that what was described is
not a field. Both were wrong in labelling what was
described as "GF(.)".
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Sat, 03 Jun 2000 11:02:26 +0200
Greg wrote:
> Well, first they are keys because they unlock the secret. Second,
> it is not a keyless cryptosystem but a keyless mistake. There is
> no way that one can determine who is reading the message unless
> a receiver's public key or a common secret key is known to the sender.
I suppose there can be situations, though, where authentication is not
an issue and there is no active opponent, i.e. no manipulations.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Sat, 03 Jun 2000 11:02:35 +0200
John Savard wrote:
> But M*A*B = M*B*A for all M,A,B does not necessarily imply that A*B =
> B*A for all A,B.
>
> I gave an example: perhaps M*Q = M*(-Q) for all M,Q, and A*B = -(B*A)
> for all A,B. (For example, A*B might be |A| - |B|, although that
> operator is not associative.)
I am not yet convinced of that. Since '*' is assumed to be associative,
we certainly have M*(A*B)=M*(B*A). If this is true for any M, I
think that by applying the inverse one should have A*B=B*A, which
is the commutativity. What is the flaw here?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Pollard's algorithm for computing discrete logs
Date: Sat, 03 Jun 2000 11:02:42 +0200
Scott Contini wrote:
> See "Speeding up Pollard's Rho Method for Computing Discrete Logarithms"
> by Edlyn Teske.
In which journal is that?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Good ways to test.
Date: Sat, 03 Jun 2000 11:14:51 +0200
tomstd wrote:
>
>
> My point was that while we can't state the strength of a cipher,
> we can point out what it does right. This can lead to
> suggestive levels of strength of the function.
Who is the 'authority' that is going to 'point out what it does right'?
Aren't 'suggestive' matters subjective and fundamentally arguable?
> From a medical point of view it's similar. If 5% of the people
> get sick with brand A, and only 0.01% with brand B, well we
> would pick brand B. But that doesn't mean in the long run brand
> B is any better. Just over that short period of analysis.
There is nothing parallel to the above in crypto. You may continue
to use a cipher without knowing that it has been cracked by some
mighty opponents. What one can often do is to go conservative,
e.g. using superencipherment, in the hope that the risk is somewhat
reduced. But there can be no absolute assurance.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Good ways to test.
Date: Sat, 03 Jun 2000 11:14:39 +0200
tomstd wrote:
> Reality: Pick the best we got, relative to all known attacks.
Pick what you think and 'believe' is the best from what you have
at hand, relative to all what you currently know and 'believe' about
published attacks. Then prey.
M. K. Shen
------------------------------
From: DrArm <[EMAIL PROTECTED]>
Subject: Quantum computers
Date: Sat, 03 Jun 2000 12:10:30 +0300
Is it true that NSA has a quantum computer for codebraking?
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: Pollard's algorithm for computing discrete logs
Date: Sat, 03 Jun 2000 11:43:49 +0200
Mok-Kong Shen wrote:
>
> Scott Contini wrote:
>
> > See "Speeding up Pollard's Rho Method for Computing Discrete Logarithms"
> > by Edlyn Teske.
>
> In which journal is that?
>
> M. K. Shen
Speeding up Pollard's Rho Method for Computing Discrete Logarithms.
Proceedings of ANTS III, LNCS 1423, Springer 1998, pages 541-553.
See
http://cacr.math.uwaterloo.ca/~eteske/
========
Université de Louvain
UCL Crypto Group
see http://www.dice.ucl.ac.be/crypto
tél. 32.10.47.25.41 (connected to my voicebox and cellular phone)
fax: 32.2.358.55.83 (only for me)
SMS: send an email (only the subject will be transmitted) to
[EMAIL PROTECTED]
------------------------------
From: jungle <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy,alt.privacy.anon-server,alt.security.pgp
Subject: Re: Anti-Evidence Eliminator messages, have they reached a burn-out po
Date: Sat, 03 Jun 2000 05:31:12 -0400
please substantiate your claims, when you can ...
EE Support wrote:
>
> On Sat, 27 May 2000 18:45:54 -0400, jungle <[EMAIL PROTECTED]>
> wrote:
>
> >very cool post, thanks ...
> >
> >but the EE spam will be ON again very soon ...
> >
> EE Tech Support here.
>
> You've been using your jungle.net address to post negative posts
> against our software for some time haven't you?
>
> Please substantiate your claims now.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sat, 03 Jun 2000 11:44:41 +0200
[EMAIL PROTECTED] wrote:
> Given the results of the cipher contest, it appears that designing a
> strong block cipher is quite easy. Some 7 or 8 ciphers remain
> unattacked on the contest site. Even assuming that all of the ciphers
> have some weakness, it seems that finding a -practical- weakness is very
> difficult.
I think that, if a cipher is published, then it has a non-zero chance
of being looked at. It does NOT follow that many people will look at
it and have sufficient interest/knowledge/resource/time/energy to do
anything with it. Basically an advertisement in a newspaper isn't any
different. I am pretty sure that plenty of competent analysts are outside
of our group. So the time spam from publication of a cipher till before
observation of any reaction from the public has no implication at all in
my humble view.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sat, 03 Jun 2000 11:44:49 +0200
"David A. Wagner" wrote:
> At this point you might ask whether the performance of today's ciphers,
> e.g. the AES, are adequate. The answer is, apparently not yet: practitioners
> still want much better performance than the best we know how to give them
> today. Maybe when we can give them encryption bandwidth that is higher
> than memory and I/O bandwidths, we'll have this problem licked, but until
> then, we're a long way from being to declare victory.
But isn't performance an unsatiable goal? A year ago I bought a 450 MGZ
PC, but now it is almost an old hat.
M. K. Shen
------------------------------
From: David Crick <[EMAIL PROTECTED]>
Subject: Re: C implementation of CAST-256?
Date: Sat, 03 Jun 2000 10:36:03 +0100
Dido Sevilla wrote:
>
> Does anyone know where I can find a reference implementation in C of the
> CAST-256 algorithm described in RFC 2612? As you people can see from my
> sig I do not live in the United States so it has to be from a source
> that doesn't come from there, lest I and the site I get it from find
> ourselves in violation of EAR. Thank you very much.
Check Dr Brian Gladman's site (in the UK):
http://www.btinternet.com/~brian.gladman/cryptography_technology/aes2/
--
+-------------------------------------------------------------------+
| David Crick [EMAIL PROTECTED] PGP RSA 0x22D5C7A9 DH 0xBE63D7C7 |
| Damon Hill Tribute Site: http://www.geocities.com/MotorCity/4236/ |
| M. Brundle Quotes: http://members.tripod.com/~vidcad/martin_b.htm |
+-------------------------------------------------------------------+
------------------------------
From: jungle <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy,alt.privacy.anon-server,alt.security.pgp
Subject: Re: Anti-Evidence Eliminator messages, have they reached a burn-out po
Date: Sat, 03 Jun 2000 05:41:49 -0400
is this a formal preliminary request to conduct evaluation of your product ?
when yes ...
provide your request with your requirements, I will reply to you back asap ...
EE Support wrote:
> Hi,
> EE Tech Support here.
>
> You've been using your jungle.net address to post negative posts
> against our software for some time haven't you?
>
> Please substantiate your claims now.
------------------------------
From: David Crick <[EMAIL PROTECTED]>
Subject: Re: C implementation of CAST-256?
Date: Sat, 03 Jun 2000 10:47:20 +0100
David Crick wrote:
>
> Check Dr Brian Gladman's site (in the UK):
Sorry, should have been the following for the Round 1 candidates:
http://www.btinternet.com/~brian.gladman/cryptography_technology/aes/
--
+-------------------------------------------------------------------+
| David Crick [EMAIL PROTECTED] PGP RSA 0x22D5C7A9 DH 0xBE63D7C7 |
| Damon Hill Tribute Site: http://www.geocities.com/MotorCity/4236/ |
| M. Brundle Quotes: http://members.tripod.com/~vidcad/martin_b.htm |
+-------------------------------------------------------------------+
------------------------------
** 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
******************************
