Cryptography-Digest Digest #858, Volume #11 Thu, 25 May 00 10:13:01 EDT
Contents:
Short Secure Serial Numbers ("Rick Heylen")
Matrix key distribution? ("Michael Brown")
Re: Short Secure Serial Numbers ("Michael Brown")
Re: Observation of Matsui's Sboxes (tomstd)
Re: pentium timings and RC5 code (tomstd)
Re: yet another broken cipher (please read) (tomstd)
Re: Crypto patentability ("Lyalc")
Re: Crypto patentability ("Lyalc")
Help on factoring large numbers (100+ digits) (Daniel)
Re: Matrix key distribution? (Mark Wooding)
Re: Is OTP unbreakable?/Station-Station (Frank Gifford)
Re: Short Secure Serial Numbers (Mark Wooding)
Re: More on Pi and randomness ("Tony T. Warnock")
Re: Is OTP unbreakable?/Station-Station ("Tony T. Warnock")
Re: Help on factoring large numbers (100+ digits) (David A Molnar)
Re: Retail distributors of DES chips? (Mark Wooding)
----------------------------------------------------------------------------
From: "Rick Heylen" <[EMAIL PROTECTED]>
Subject: Short Secure Serial Numbers
Date: 25 May 2000 10:31:14 GMT
I am trying to find a solution to the following problem.
We have a serial number which the user types in (so it can't be too long).
The serial number contains some information like a product ID, user number
etc with a total information content of about 96 bits and 40 bits of
"checksum" with the idea being that for all possible information contents,
there is only one valid checksum and that in order to find a valid serial
number, an attacker would have to test on average 2^39 possibilities.
The code that verifies the serial number is public but we'd still like it
to be time-consuming to generate different valid serial numbers.
Normal public key cryptography would be suitable except that the message
size for the system to be secure would be longer than what a user would be
happy to type in.
Has anybody got any ideas?
Richard
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Matrix key distribution?
Date: Thu, 25 May 2000 10:47:30 GMT
Hi there,
I was thinking about using singular matricies for key exchange. After a few
attempts I got to the following. I can almost prove it's false, but I can't
break through the last barrier.
Would someone who has a bit of spare time mind looking at it?
Here's how it works:
<- START ->
Computer (1) thinks of two matricies, A and C. A must be invertable and C
must not be. Computer (2) thinks up a matrix B. It, too must be invertable.
These are the matricies in letter form:
A = | a b | B = | f g | C = | k l |
| c d | | h j | | km lm |
Computer (1) sends the matrix AC to computer (2).
AC = | k(a + bm) l(a + bm) |
| k(c + dm) l(c + dm) |
Computer (2) multiplies it by B and sends it back.
ACB = | (kf + hl)(a + bm) (kg + jl)(a + bm) |
| (kf + hl)(c + dm) (kg + jl)(c + dm) |
Computer (1) multiplies the returned matrix by the inverse of A and returns
it.
inv(A)*ACB = CB = | kf + lh kg + lj |
| m(kf + lh) m(kj + lj) |
Computer (2) then multiples this by the inverse of B to get C.
CB*inv(B) = C = | k l |
| km lm |
Both computers now know C without having directly passed it from (1) to (2)
<- END ->
Undoubtably, you spotted the flaw in this system :)
What we have to do is find the value of C from AC, ACB, and CB. By using
the (kf + lh) values in CB it can determine (a + bm) values by using ACB.
It can use this (a + bm) value to get the value for k and l out of the AC
matrix. All relatively easy, and quite quick to do. If this was all you had
to do. There is still the value of m that you have to calculate, and this
is where I get stuck.
With some fiddling you can get a couple of simultanous equations, but these
contain the variables a and b, which you don't know. Am I on the totally
wrong track or is it impossible to get m (wouldn't that be great!)?
Any help greatly appreciated.
Michael Brown
([EMAIL PROTECTED])
Remove the .nospam before replying - I'm paranoid
PS: Has anyone else tried this matrix idea beforehand? Anything come out of
it? I would really like to know if I am trying to do something impossible!
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: Short Secure Serial Numbers
Date: Thu, 25 May 2000 10:52:13 GMT
What I do in my programs is MD5 the following text:
<program name>:<version>:<user name>:<any other data seperated by
:>:<random number>
for example
"MYPROG:1.0:MICHAEL BROWN:my@email:1234
This generated a 32 (I think) charactes hash. You can whack out every third
or second charracter. Then, get the user to fill in the info nd check the
hash. If it doesn;t work, then don't let them install (or whatever). Don't
know if this helps.
Michael Brown
Rick Heylen <[EMAIL PROTECTED]> wrote in article
<01bfc633$ac206860$[EMAIL PROTECTED]>...
> I am trying to find a solution to the following problem.
> We have a serial number which the user types in (so it can't be too
long).
> The serial number contains some information like a product ID, user
number
> etc with a total information content of about 96 bits and 40 bits of
> "checksum" with the idea being that for all possible information
contents,
> there is only one valid checksum and that in order to find a valid serial
> number, an attacker would have to test on average 2^39 possibilities.
> The code that verifies the serial number is public but we'd still like it
> to be time-consuming to generate different valid serial numbers.
> Normal public key cryptography would be suitable except that the message
> size for the system to be secure would be longer than what a user would
be
> happy to type in.
> Has anybody got any ideas?
>
> Richard
>
>
------------------------------
Subject: Re: Observation of Matsui's Sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 25 May 2000 04:12:28 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>
>> No I get what you are saying, I am just pointing out neither
A or I
>> follow SAC. My question is does S follow sac? I will test
it later
>> tonight.
>
>Good-oh. <phew> I think we finally achieved a point where we
>understood each other. It was touch and go for a bit... ;-)
Yeah I did the smart thing and read the rijndael paper.
Sorry for being a bit slow there.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: pentium timings and RC5 code
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 25 May 2000 04:13:34 -0700
In article <8gift3$km7$[EMAIL PROTECTED]>, Greg <ciphermax@my-
deja.com> wrote:
>
>> Well since my code sucks, could someone with a K6-2 or PII
time
>> my code (http://www.tomstdenis.com/rc5asm.zip) and tell me the
>> clocks per block they get?
>
>I think what people have been trying to say is that you cannot
>do this.
>
>Go to the intel web site and download the cpu
>docs to understand the features of the PII to see
>how to maximize cache hits, how to keep the dual pipeline
>filled to capacity as often as possible, etc., then don't
>worry about how the OS interferes with the cache or pipeline.
>You did the best you could in the design and today that is all
>one can expect.
>
>Publish what you designed and the numbers from Intel to back it
up
>and we will give you Kudos for that.
No they are saying it's possible to time it, just that my code
sucks. Well Guys go ahead.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: yet another broken cipher (please read)
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 25 May 2000 04:38:04 -0700
In article <[EMAIL PROTECTED]>, tomstd
<[EMAIL PROTECTED]> wrote:
>I designed yet another cipher, but broke it with a 16R
>differntial and *at least* 2^49 plaintexts. The postscript
>paper is at
>
>www.tomstdenis.com/tc1_draft.ps
>
>If anyone wants pdf copies I will make one...
>
>I would really like comments and confirmations of my results. I
>have some questions about doing the selective-sbox attack (i.e
>where only some of the sboxes are active). If anyone wants to
>help please email me or reply here.
>
>Tom
I made a mistake counting active sboxes, I have a word97
document copy of the paper at
http://www.tomstdenis.com/tc1.doc
But I can't contact this site
http://wheel.compose.cs.cmu.edu:8001/cgi-bin/browse/objweb
To make the pdf and ps files.
If someone could just do this for me and email the output to
[EMAIL PROTECTED] I would really appreciate it.
(BTW you don't need to download my word97 document since the
other website will accept urls).
Thanks,
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Lyalc" <[EMAIL PROTECTED]>
Subject: Re: Crypto patentability
Date: Thu, 25 May 2000 21:54:17 +1000
snip>> 2. An idea can't be patented. A patent describes an implementation of
an
>> idea. e.g. Rotations are an obvious idea - but a specific use of them
can
>> be patented.
>
>Are you saying that, for example, rotation by 5 bits is patentable but
>rotation by n bits, with n dynamically determined, is not patentable?
>Or do you mean that rotation CAN be one element in a specific sequence
>of operations that is a patentable?
The latter
lyal
------------------------------
From: "Lyalc" <[EMAIL PROTECTED]>
Subject: Re: Crypto patentability
Date: Thu, 25 May 2000 22:03:02 +1000
snip
>> _Precisely_ the opposite is actually true: patents are one of the few
>> ways for a small company, or even one smart person, to level the
>> playing field and be competitive against a big company.
>
>So you have the 60.000 deutschmarks to buy an european patent ?
>Even if I'll find something nifty tomorrow I'll hardly be able
>to patent it. Its just too expensive for me. Its also too
>expensive for small companies.
Mostly people laodge the intial application, which starts the 'lock-ip" - it
sets a priority date. This is cheaper - often about $2000-5000, I
understnad.
Once you have the application lodged, then try to sell the IP. With funds
from the sale, then complete the patent process over the next 12-36 months,
costing up the $50k or so, including patent attorney fees. (Australian
prices quoted). If you can't sell the IP, then either a) it was not a good
idea, b) you are not a good IP sales person, c) someone is wating until you
are 'starving', then licences/buys the IP for a song, or d) no one wants the
IP at this stage, so you scrape up the money, finalise the patent, and hope
someone licences/buys the IP before the patent expires.
Getting off topic but:
A patent is a simple commercial investment in property under laws that many
countries have, and observe.
lyal
------------------------------
From: [EMAIL PROTECTED] (Daniel)
Subject: Help on factoring large numbers (100+ digits)
Date: Thu, 25 May 2000 12:46:08 GMT
1) Is there a general method which allows calculating (large) prime
numbers (except Erastothenes'Sieve which is rather slow)
2) Is there a general method for factoring large numbers which contain
over 100 digits?
All help greatly appreciated. Thanks
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Matrix key distribution?
Date: 25 May 2000 13:06:14 GMT
Michael Brown <[EMAIL PROTECTED]> wrote:
> inv(A)*ACB = CB = | kf + lh kg + lj |
> | m(kf + lh) m(kj + lj) |
>
> What we have to do is find the value of C from AC, ACB, and CB. By using
> the (kf + lh) values in CB it can determine (a + bm) values by using ACB.
> It can use this (a + bm) value to get the value for k and l out of the AC
> matrix. All relatively easy, and quite quick to do. If this was all you had
> to do. There is still the value of m that you have to calculate, and this
> is where I get stuck.
Am I missing something? Can you not just use the fact that you know kf
+ lh and m(kf + lh), both in CB above, to find m?
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Frank Gifford)
Subject: Re: Is OTP unbreakable?/Station-Station
Date: 25 May 2000 09:12:04 -0400
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] wrote:
>> One of the major limitations of OTP is its a Station to Station
>> Protocol...if there are more then two users having the random
>> keypad...sending OTP messages to different users at different times
>> is a major headache...you have to sync the random keys..
>
>Usually, a OTP is not shared among more than one link (sender-
>receiver pair), precisely in order to avoid having to synchronize
>multiple pads. The message originator uses a pad appropriate for
>each of the recipients.
1) There is still a problem if HQ wants to send a message to a particular
unit which is unreadable to all others.
2) The usage that OTPs have had (i.e. with spies) is that after a message
was encrypted with a page from an OTP, that page was destroyed. This way
even if the spy was discovered, previous communications could not be
decrypted.
But if everyone has a copy of the pad - or if the pad is on a CDROM, then
destroying the parts of pad which have been used become difficult to
implement. Now you have to tell all your receivers, "destroy page 25",
and you have to trust that they will do so.
This brings a question to mind. If using a CD-RW (rewriteable) to hold
OTP data between two people, and the sectors used for the OTP communication
are then overwritten, how easy/difficult could it be to recover the
original bits? If too easy, then a OTP on a CDROM could allow recovery
of past communications.
-Giff
--
Too busy for a .sig
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Short Secure Serial Numbers
Date: 25 May 2000 13:25:42 GMT
Rick Heylen <[EMAIL PROTECTED]> wrote:
> The code that verifies the serial number is public but we'd still like
> it to be time-consuming to generate different valid serial numbers.
> Normal public key cryptography would be suitable except that the
> message size for the system to be secure would be longer than what a
> user would be happy to type in.
If you were going to use a digital signature, how would you prevent
adversaries from changing the public verification key? If the answer is
that, although the actual code is public, the key is kept somewhere
(relatively) difficult to find and alter, then you can probably make do
with a secret key, and use something like HMAC-SHA to produce your
checking information.
-- [mdw]
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: More on Pi and randomness
Date: Thu, 25 May 2000 07:26:54 -0600
Reply-To: [EMAIL PROTECTED]
"Douglas A. Gwyn" wrote:
> Mok-Kong Shen wrote:
> > I am a complete outsider. But I conjecture that interval arithmetics
> > might be useful in the present issue.
>
> The trouble with interval arithmetic as it is usually applied
> is that the intervals rapidly grow as operations are combined.
> A better (not perfect) approach is to perform arithmetic with
> distributions replacing values. (The simplest useful method
> would be to approximate every distribution as a Gaussian.)
> This still tends to degenerate into total noise after a while,
> but retains significance longer than does worst-case interval
> arithmetic.
Intervals do not necessarily grow in most interval algorithms. For example
in Newton's method, one in puts an interval guaranteed to contain the
solution; then one comutes the x1-f(x0)/f'(x0) in interval arithmetic;
then the original x0 is intersected with x1. The intersection often
narrows the result considerably. Also, dividing an interval by a constant
narrows the resulting interval.
Nick Metropolis had a article about 30 years ago on the idea of carrying
uncertanties as Gaussians. It's not too bad as the width of the error
estimates increases as the square root of the number of computations.
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Is OTP unbreakable?/Station-Station
Date: Thu, 25 May 2000 07:27:50 -0600
Reply-To: [EMAIL PROTECTED]
"Douglas A. Gwyn" wrote:
> [EMAIL PROTECTED] wrote:
> > One of the major limitations of OTP is its a Station to Station
> > Protocol...if there are more then two users having the random
> > keypad...sending OTP messages to different users at different times
> > is a major headache...you have to sync the random keys..
>
> Usually, a OTP is not shared among more than one link (sender-
> receiver pair), precisely in order to avoid having to synchronize
> multiple pads. The message originator uses a pad appropriate for
> each of the recipients.
If more than one pair of people have a one time pad, then oneness is
violated.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Help on factoring large numbers (100+ digits)
Date: 25 May 2000 13:09:25 GMT
Daniel <[EMAIL PROTECTED]> wrote:
> 1) Is there a general method which allows calculating (large) prime
> numbers (except Erastothenes'Sieve which is rather slow)
Yes. Several. Best overview I know of is the chapter in the Handbook of
Applied Cryptography on generating primes for public-key cryptosystems.
You can download it for free from
http://www.cacr.math.uwaterloo.ca/hac/
You should probably look at the Miller-Rabin primality test, and then
consider applying it to large random numbers.
> 2) Is there a general method for factoring large numbers which contain
> over 100 digits?
Yes. The General Number Field Sieve, most recently used to factor a
512-bit number. There are several factoring experts in this group who
may provide specific references. In the meantime, I'm told that
the book by Riesel on Prime Numbers and Methods of Factorization is
good. There is also an introduction to factoring as part of Neal
Koblitz's book; it doesn't get to the GNFS, but it introduces some of
the ideas behind modern factoring algorithms in a nice way.
Thanks,
-David
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Retail distributors of DES chips?
Date: 25 May 2000 13:58:15 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> That's not true. This cipher could simply be
>
> Ek(P) = P xor K
>
> unless you test it.
Yes, but the point is that, in theory, DES is completely deterministic.
If you have a DES chip, you can feed known keys and plaintexts in it,
and verify that you get the right answers against some other known and
trusted implementation. You can even give it `trick questions' every
now and then while it's in production use, checking its results, to make
sure it's not randomly deciding to emit leaked key material instead of
giving the right answers every now and then. I'd hope that most serious
users of black-box cryptography hardware or software did something like
this.
With DSA, if you don't trust the hardware, you're stuffed. You can
verify that what it's given you is a valid DSA signature, but because
DSA is randomized there is no `right' answer such that, if you don't get
it, you can be suspicious. And there are documented ways of leaking
information in valid DSA signatures, such as arranging that r = g^k (mod
p) mod q is a quadratic (non)residue modulo various secret primes -- see
Schneier's book for more information -- and there's no way you can tell
this is happening unless you know the secrets.
-- [mdw]
------------------------------
** 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
******************************
