Cryptography-Digest Digest #239, Volume #10 Wed, 15 Sep 99 03:13:03 EDT
Contents:
Re: Ritter's paper (Sundial Services)
Re: Can you believe this?? (Eric Lee Green)
OBJECT IDENTIFIER for HMAC-SHA1-96 and HMAC-MD5-96???? ("Douglas Clowes")
ANNOUNCE: Interception & Decryption, Scrambling for Safety 3.5 (UK), 23/9/99 ("No
Spam")
Re: Make a point on KRYPTOS (Jim Gillogly)
Re: First draft of Ocotillo now online (Eric Lee Green)
Re: Mystery inc. (Beale cyphers) (Curt Welch)
Re: Mystery inc. (Beale cyphers) (Curt Welch)
----------------------------------------------------------------------------
Date: Tue, 14 Sep 1999 21:55:14 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Ritter's paper
Terry Ritter wrote:
> > I check it out nice article. But what I did not get was the comment about
> >if you use a patented system and someone breaks it you can recover damages.
> >What did you mean by that Mr. Ritter. Are you saying it is against the law to
> >decode something this is encrypted with a patented method?
>
> Against the law? Well, yes, sort of: using a patented cipher without
> an explicit license is grounds for a suit to recover damages in
> federal court.
It may be so, Mr. Ritter, but personally I felt that the article was a
bit too self-defensive about the issue of a cipher being patentable or
not, and patented or not. An algorithm's patent status is neither a
crown nor a scarlet-letter and should not interfere with objective
judgement of it. You have some original ideas and should be justifiably
pleased to have a patent and you should continue to exploit it.
But I debate in my mind how successful one would be, asking a jury to
reward one spook for stealing secrets from another spook. I debate how
successful software patents really are, anyway. You just can't
touchy-feely computer software like you can a physical invention...
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Can you believe this??
Date: Tue, 14 Sep 1999 21:39:09 -0700
jerome wrote:
> but /dev/random is blocking when the entropy isnt there...
> important to know :)
Hmm... I haven't tried it under Linux. Under FreeBSD I type "cat
/dev/random >/tmp/foobar" and it puts out however many bits of entropy
are in /dev/random to /tmp/foobar. Ah. Just ssh'ed into a machine at the
office running Linux 2.0.37, and indeed it blocked when I tried "cat
/dev/random >/tmp/foobar". Same thing with Linux 2.2.12. Sigh. There has
to be some way around that :-(. Except I can't think of a way except for
doing 1-byte reads with an alarm() to interrupt me swiftly if I block
:-(. Hmm, I wonder what happens if I do a select() on /dev/random to see
if there is any input waiting? I would still need to get it one byte at
a time that way, but at least I wouldn't block. But I don't remember if
select() will work on a device node under Linux (mumble mumble mumble
I'll wait until I have to port this beast to Linux...).
> and you can still use /dev/urandom for challenge, because as
> far as i know they don't need to be cryptographically random
Well, maybe. The problem is that if not enough state has been mixed into
/dev/urandom. Challenge strings are generally created initially at
network service boot time in order to prevent replay attacks and don't
change after that (the sequence numbers increment after that to prevent
replay attacks), but they prevent replay attacks only if they are not
reused. Still, I suspect only around 2^24 bits of real randomness would
suffice to make reuse very unlikely, making /dev/urandom quite
sufficient in practice. That also helps with hiding any weaknesses of
the PRNG used to generate session keys and such, since no outputs of the
PRNG will be sent "in the clear" this way where somebody could somehow
figure out an attack against the PRNG based on known outputs. Hmm, David
Wagner has a paper at http://www.cs.berkeley.edu/~daw/papers/ detailing
some attacks on PRNG's based on known outputs.
There has to be some reason why I'm fiddling with this stuff at 9:30pm,
at home on my own time. General fascination with the subject, I guess...
--
Eric Lee Green http://members.tripod.com/e_l_green
mail: [EMAIL PROTECTED]
^^^^^^^ Burdening Microsoft with SPAM!
------------------------------
From: "Douglas Clowes" <[EMAIL PROTECTED]>
Subject: OBJECT IDENTIFIER for HMAC-SHA1-96 and HMAC-MD5-96????
Date: Wed, 15 Sep 1999 15:51:09 +1000
Anybody know where to find these things?
Where does IANA keep their registered OIDs?
Thanks,
Douglas
------------------------------
From: "No Spam" <[EMAIL PROTECTED]>
Subject: ANNOUNCE: Interception & Decryption, Scrambling for Safety 3.5 (UK), 23/9/99
Date: Wed, 15 Sep 1999 06:24:03 +0100
PLEASE CIRCULATE TO THOSE THAT MIGHT BE INTERESTED
(APOLOGIES FOR ANY DUPLICATION)
(Timing and speakers likely to change : please check
http://www.fipr.org/sfs35.html frequently for updates)
Scrambling for Safety 3.5 - Thursday September 23 1999
======================================================
The Foundation for Information Policy Research, Privacy International and
the LSE Computer Security Research Centre are jointly sponsoring the fourth
in the series of public conferences on cryptography policy, e-commerce and
Internet surveillance. This will be the second conference of 1999, and has
been called in response to the exceptional circumstance of two official DTI
consultations in the same year, and the Home Office's recent consultation on
revising the Interception of Communications Act to cover the Internet.
Admission is free of charge.
09:15 - 13:30, Thursday 23 September 1999
Old Theatre, Main Building,
London School of Economics,
Houghton St., London WC2
(for directions, check links on the Website)
Registration: Send e-mail to
[EMAIL PROTECTED]
with "name, organisation" in body. Telephone enquiries: 0171 354 2333
The connections between Home Office policy on interception and powers
proposed in Part.III of the DTI's draft Electronic Communications Bill
(closing date for responses 8th October) will be explored, and well as
the legal framework for establishing voluntary licensing of cryptography
services, and recognition of digital signatures.
Provisional Programme :
=======================
09.25 Welcome - Caspar Bowden, FIPR
09:30 Internet Service Providers Association (invited)
Alliance for Electronic Business: Progress towards self-regulation
10:00 "Cryptography, privacy and information warfare"
- Whitfield Diffie
10:30 "Why we needed further consultation"
- Alan Duncan MP, Shadow spokesman on Trade and Industry
11:00 "Cryptography's central role in e-commerce policy"
- Chris Sundt, CBI
11:30 "Law enforcement access to keys - legal and human rights issues"
- Nicholas Bohm (Law Society)
12:00 Keynote: Patricia Hewitt MP
- Minister of State for E-Commerce at the DTI
12:45 Panel discussion
- Jim Norton (Cabinet Office PIU)
- Stephen Pride (DTI)
- Peter Sommer (Special Adviser to T&I Sel Ctee)
- Clare Wardle (Post Office)
- LIBERTY
- Jack Beatson QC (Essex Court Chambers)
13:30 close
============
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Make a point on KRYPTOS
Date: Wed, 15 Sep 1999 05:31:57 +0000
"Douglas A. Gwyn" wrote:
> However, the cryptographer seems to have intentionally
> chosen systems and ciphertext quantities that can be
> broken with pencil-and-paper (and perserverance, and luck).
> So it seems that it was intended to be a "fair" challenge.
That's certainly true of the first three (broken) systems. However,
Sanborn has said that the remaining part is a "whole new ball game",
and has said in the past that he never expects it to be broken.
While it's seductively tempting to think that the fourth part is as
easy as the first three and just awaits somebody trying the right
kind of cipher with the right key(s), it's also quite possible that
it is indeed much harder, as suggested by Sanborn in print.
--
Jim Gillogly
Sterday, 24 Halimath S.R. 1999, 05:29
12.19.6.9.12, 5 Eb 20 Mol, Third Lord of Night
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: First draft of Ocotillo now online
Date: Tue, 14 Sep 1999 22:07:51 -0700
jerome wrote:
> On Mon, 13 Sep 1999 14:24:33 -0700, Eric Lee Green wrote:
> >
> >1) Finding sources of adequate initial entropy. I don't think I've done
> >a good job there, there's just not many sources on raw Unix :-(.
> >However: There is provisions for adding more values to the input pool.
> >One suggestion was to use the "jitter" between the times that keystrokes
> >came in, etc.
>
> which one do you use ?
Millisecond timestamp, a counter, millisecond timestamp when packets
come in. My particular application is not interactive and many of the
targets don't even have keyboards, so interactive things like using the
difference between millisecond timestamps when keystrokes are pressed,
a'la the old PGP method, won't work.
For initial entropy, I also do things like: md5 the contents of
various system log files (these are not random but do change with every
reboot, so they should at least be unpredictable unless the attacker has
root access -- and if they have root access, Game Over for my
application, the whole point of the cryptographic component is to keep
people from gaining root access), toss in the output of netstat -i (the
count of packets that have gone in and out is the particular bit of
entropy that I'm interested in there), etc. These files change very
slowly over time so they cannot be used as an ongoing source of
unpredictability, but I have to find something somewhere to generate my
initial seed... trying to do this in userspace without an interactive
operator available to noodle the keyboard is a pain in the @#%$!@.
> >2) How random is the output when asked to give huge numbers of values?
> i dont see any if you keep feeding your prng with random bits.
David Wagner generously shipped me a couple of references to papers he's
done. See his archives at
http://www.cs.berkeley.edu/~daw/papers/
One problem is that, when asked to give huge numbers of values, we are
essentially in counter mode -- i.e., essentially the data input to the
block cipher at the heart of the beast is counting up 1..2..3..4..5..
etc. Or worse yet, 1000..2000...3000..4000.. which would cycle even
faster and allow the attacker to predict future values after the first
cycle is over. The MD5 on the input is supposed to prevent this to a
certain extent, the same with the MD5 on the output, but it still may
cycle.
> >4) Is the MD5 hash on the output necessary? I've tried it both ways,
> >with and without the hash. In both cases the output appears to be
> >statistically random. The thought is that the MD5 hash on the output
> >prevents backtracking attacks, is that reasonable?
>
> yes, md5 has no publicly known examples of 'plain text' found from
> the message digest. But md5 just diffuses the original random, it
> don't add any.
Okay. So the MD5 *is* good for preventing attacks against the block
cipher itself.
> as far as i know you are in 'user space', you can hardly have
> control of the data you read. your timer reads may be synchronized
> and/or manipulate by another processus (obviously ran by an attacker).
> you have to use data unknown from the attackers.
Most of the attacks that I can think of for my particular application
would require 'root' access on the system that the program is running
on. Given that the whole point of the cryptographic component of the
application is to prevent attackers from gaining 'root' access on the
system that the program is running on, well, (shrug) if they have
'root', game is already over.
On the other hand, I'm not under the delusion that I somehow evaded the
laws of physics. The problem you mention is real. It most probably will
not be a problem for my particular application, because the only really
important keys are generated immediately after installation hopefully
prior to the time that the network is under attack (though that's an
unwarranted assumption on some networks, I've seen networks that were
like swiss cheese, with password sniffers, root kits, and Back Orifice
all happily working away), but I'd definitely prefer a real /dev/random
where I could get my bits.
> to sum up if you succeed to do a good random generator in user space,
> i would be really interrested to know how.
The question is not whether I can do a really good random generator in
user space (there just isn't any way to do that, given the limited
sources of entropy available). The question is whether I can do a "good
enough" PRNG in user space. I will definitely prefer a source of true
randomness like /dev/random if I have access to it. Unfortunately, Sun,
HP, etc., in their wisdom, do not seem to have seen fit to to outfit
their operating systems with kernel-level random number generators :-(.
It's sad that "freeware" operating systems like Linux and FreeBSD
outstrip their commercial counterparts so badly in this area. (And
unfortunately I cannot expect customers to retrofit their HP, Sun, etc.
with equivalent kernel-mode drivers, even if I somehow got my boss to
hire enough manpower to do the device drivers for all the architectures
we support).
--
Eric Lee Green http://members.tripod.com/e_l_green
mail: [EMAIL PROTECTED]
^^^^^^^ Burdening Microsoft with SPAM!
------------------------------
Subject: Re: Mystery inc. (Beale cyphers)
From: [EMAIL PROTECTED] (Curt Welch)
Date: 15 Sep 1999 05:38:47 GMT
"Colin Barker" <[EMAIL PROTECTED]> wrote:
> Is there any particular reason why you left an underscore for all
> occurrences of the letter x (represented by the number 994 which is the
> word "seXes"), but explicitly put the letter y (represented by the number
> 822 which is the word "fundamentallY")?
I don't know for sure. But I think I understand what's going on.
First, that was output from a program written by Ed Rupp (not me) using his
numbering of the DOI, and his copy of the Beal #2 cipher. The program
worked that way because the DOI it used as input was Ed's "corrected"
version which stopped at the word "fundamentally". Any number larger than
the last word in the input key was printed as an _. His DOI used as input
for that program has the word spelt as "yfundamentally" so it prints the y
correctly. So that's why you see the y and the _.
Second, you are using a copy of Beal #2 that is different than the one I
have (which I got from Ed). In my copy, the x is represented by the number
1005 (not 994), and the y is 811 (not 822). 1005 is the largest number in
the cipher. 811 is the second largest number. I'm pretty sure you have a
bogus copy of the cipher.
As Jeff already wrote in another article:
[EMAIL PROTECTED] wrote:
> I believe the Roanoke transcript you mention is the one written by
> George Hart. Hart rewrote the original ciphers to conform to his own
> numbering of the Declaration of Independence, so it is not a good
> starting point for the Beale ciphers. For many years the Hart
> manuscript was the only source available, but a copy of the original
> 1885 pamphlet, The Beale Papers, by James Ward, was finally discovered
> in the late 1970's. This has been reprinted in, The Beale Treasure, A
> History of a Mystery, by Peter Viemeister.
>
> More information can be found at the Crypto Drop Box:
>
> http://www.und.nodak.edu/org/crypto/crypto/resources.html
Hart changed the #2 cypher so it matched a correct numbering of the DOI
and didn't bother to point this fact out (hey, it was already broken so who
cared if he changed it to make it look better?). I think you have a copy
of the bogus Hart #2 instead of the real Beale #2 (as published by Ward
in the 1800s).
Ed has a photocopy of the original Ward publication so I'm sure he has the
correct numbers.
And, now that I'm thinking about this issue, I go back and check the other
article in this thread:
[EMAIL PROTECTED] wrote:
> Look at the size of the maximum number in each coded piece:
> #1 => 2906
> #2 => 994
> #3 => 975
The max number in #2 is 1005, not 994. #1 and #3 is correct.
sha99y000000, you too have a bogus copy of #2 as well.
So, because of the fact that the DOI key used for #2 now clearly has
something to do with #1 (because of the Gillogly strings), it becomes
imporant to get the _correct_ numbering of the DOI. i.e., the numbering
used to encode #2. And to figure that out, you need the "real" #2, not
the doctored version published by Hart.
If you look at the errors in #2, you find that numbers are "shifted"
in different sections. i.e. 310-350 are all off by +1, 351-412 are +2,
etc. (these are just examples not real numbers). This indicates the
errors happened becuse the DOI was numbered incorrectly. For example,
to do this, imagin getting a copy of the DOI, and then counting the
words. You could then do something like write the word number for only
the first word at the beginning of each line. Line 1 starts with word
1, line 2 starts with word 12, line 3 starts with word 22 etc.
If you do it like this, and make an error, then that error is likely
to carry on though the rest of the document. And if you encode your
clear text using that, you would find a word to use, then, using the
number at the beginning of the line, count over to your word to figure
out the cipher text number to use. So if the first word is labeled
wrong, then every word encoded from that line will be "off" by the
same amount.
It looks like this is what happened when #2 was encoded.
So, to get the "real" key for #2, you need to try and reproduce all
these counting errors. Ed did this in his copy of the DOI which he
used as input for his decoding program. He did it by inserting
bogus words (x x x) where needed, or combining two words into one (I think
there's one case in the DOI were it's unclear whether something was
actually one word or two) - and at least in one place I think about 10
words had to be removed.
This is the same type of "fix" Jim talked about John King doing in another
messages in this thread.
When you adjust the DOI numbering to match the "real" #2, you find that
it also corrects some of the errors in the Gillogly strings which show up
in #1. So this is both an indication that the encoding errors were made
in the DOI numbering (instead of in the process of encoding), and that
this same (bogus) numbering of the DOI was somehow used in the process of
encoding the #1 cipher.
So, back to the y/_ question.
Since y is encoded with 811, and x is 1005, and there are no numbers
between 811 and 1005 in the #2 cipher, you end up with a gap of
(1005-811) 194 words in the DOI between these that were not used in the
the #2 cipher. But if you count the words, you find in
the real DOI, there are something like 172 words between "fundamentallY"
and "sexes". So, if there are numbering errors adding up to 22 words,
where are they? How do you even know for sure that "sexes" is right?
(though it is a very good guess as to what the original encoder was trying
to hit seing there are no words beging with x and sexes is the closest
to 1005).
Anyway, I think Ed felt the numbering of the DOI beyond "fundamentallY" was
really undefined. And since he was using that DOI for other tests (like
looking at the Gillogly strings), he didn't want the words beyond that
being used and confusing the results he saw). So I think that's why he
stopped at funaamentally and that's why y shows up but x shows up as _.
Is that simple enough for you :)?
BTW, Ed sent me this "corrected" DOI in 1985 (I still have the e-mail).
And I see from Jim's article in this thread that John King published his "A
Reconstruction of the Key to Beale Cipher Number Two" in 1993 (8 years
later). I think Ed published his work as well, but I don't know the date.
I suspect however that it was before 1993.
I should ask Ed if he knows of King's work and if he knows how his DOI
compares to King's. (Ed - consider yourself asked...) (and if he has done
any more work on this in the past 15 years....)
Here's my copy (from Ed) of the Beal #2 cipher:
115 73 24 807 37 52 49 17 31 62 647 22 7 15 140 47 29 107 79 84 56
239 10 26 811 5 196 308 85 52 160 136 59 211 36 9 46 316 554 122
106 95 53 58 2 42 7 35 122 53 31 82 77 250 196 56 96 118 71 140
287 28 353 37 1005 65 147 807 24 3 8 12 47 43 59 807 45 316 101 41
78 154 1005 122 138 191 16 77 49 102 57 72 34 73 85 35 371 59 196
81 92 191 106 273 60 394 620 270 220 106 388 287 63 3 6 191 122 43
234 400 106 290 314 47 48 81 96 26 115 92 158 191 110 77 85 197 46
10 113 140 353 48 120 106 2 607 61 420 811 29 125 14 20 37 105 28
248 16 159 7 35 19 301 125 110 486 287 98 117 511 62 51 220 37 113
140 807 138 540 8 44 287 388 117 18 79 344 34 20 59 511 548 107
603 220 7 66 154 41 20 50 6 575 122 154 248 110 61 52 33 30 5 38
8 14 84 57 540 217 115 71 29 84 63 43 131 29 138 47 73 239 540 52
53 79 118 51 44 63 196 12 239 112 3 49 79 353 105 56 371 557 211
505 125 360 133 143 101 15 284 540 252 14 205 140 344 26 811 138
115 48 73 34 205 316 607 63 220 7 52 150 44 52 16 40 37 158 807 37
121 12 95 10 15 35 12 131 62 115 102 807 49 53 135 138 30 31 62 67
41 85 63 10 106 807 138 8 113 20 32 33 37 353 287 140 47 85 50 37
49 47 64 6 7 71 33 4 43 47 63 1 27 600 208 230 15 191 246 85 94
511 2 270 20 39 7 33 44 22 40 7 10 3 811 106 44 486 230 353 211
200 31 10 38 140 297 61 603 320 302 666 287 2 44 33 32 511 548 10
6 250 557 246 53 37 52 83 47 320 38 33 807 7 44 30 31 250 10 15 35
106 160 113 31 102 406 230 540 320 29 66 33 101 807 138 301 316
353 320 220 37 52 28 540 320 33 8 48 107 50 811 7 2 113 73 16 125
11 110 67 102 807 33 59 81 158 38 43 581 138 19 85 400 38 43 77 14
27 8 47 138 63 140 44 35 22 177 106 250 314 217 2 10 7 1005 4 20
25 44 48 7 26 46 110 230 807 191 34 112 147 44 110 121 125 96 41
51 50 140 56 47 152 540 63 807 28 42 250 138 582 98 643 32 107 140
112 26 85 138 540 53 20 125 371 38 36 10 52 118 136 102 420 150
112 71 14 20 7 24 18 12 807 37 67 110 62 33 21 95 220 511 102 811
30 83 84 305 620 15 2 10 8 220 106 353 105 106 60 275 72 8 50 205
185 112 125 540 65 106 807 138 96 110 16 73 33 807 150 409 400 50
154 285 96 106 316 270 205 101 811 400 8 44 37 52 40 241 34 205 38
16 46 47 85 24 44 15 64 73 138 807 85 78 110 33 420 505 53 37 38
22 31 10 110 106 101 140 15 38 3 5 44 7 98 287 135 150 96 33 84
125 807 191 96 511 118 40 370 643 466 106 41 107 603 220 275 30
150 105 49 53 287 250 208 134 7 53 12 47 85 63 138 110 21 112 140
485 486 505 14 73 84 575 1005 150 200 16 42 5 4 25 42 8 16 811 125
160 32 205 603 807 81 96 405 41 600 136 14 20 28 26 353 302 246 8
131 160 140 84 440 42 16 811 40 67 101 102 194 138 205 51 63 241
540 122 8 10 63 140 47 48 140 288
I put it in this form by hand editing so there could be errors.
To double check things, there should be 763 numbers in the
cipher. The largest is 1005, the second largest is 811.
There are 180 unique numbers. If you sum all 763 numbers, you
get the value 122738. If any of this doesn't match the above
numbers, I made an error somewhere. Also, I'm guessing this is
somewhat close to the Hart version so if you compare the two
the differences should make sense. (I've never done that however).
--
Curt Welch http://CurtWelch.Com/
[EMAIL PROTECTED] Webmaster for http://NewsReader.Com/
------------------------------
Subject: Re: Mystery inc. (Beale cyphers)
From: [EMAIL PROTECTED] (Curt Welch)
Date: 15 Sep 1999 06:12:53 GMT
[EMAIL PROTECTED] (Curt Welch) wrote:
> [EMAIL PROTECTED] wrote:
> > More information can be found at the Crypto Drop Box:
> >
> > http://www.und.nodak.edu/org/crypto/crypto/resources.html
http://www.und.nodak.edu/org/crypto/crypto/general.crypt.info/beale/
I just checked this site out and found it has lots of good info
about all this, including most of Ed's work that I have under the
more.beale directory. And in the DOI file is a nice description
of somebodies adjustments to the DOI _and to B2!_. Didn't know
there were B2 adjustments people felt were needed!
> I put it in this form by hand editing so there could be errors.
> To double check things, there should be 763 numbers in the
> cipher. The largest is 1005, the second largest is 811.
> There are 180 unique numbers.
I also noted that under that same site there's a "corrected" version
of B2 which says there are (I think) 182 variants - so that version
may well be the best to work from. It's a must-see site if you want
more info on this...
--
Curt Welch http://CurtWelch.Com/
[EMAIL PROTECTED] Webmaster for http://NewsReader.Com/
------------------------------
** 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
******************************
