Cryptography-Digest Digest #473, Volume #13 Mon, 15 Jan 01 16:13:01 EST
Contents:
Key fingerprint algorithms ? (Jarno Huuskonen)
Re: fun with solitaire ("r.e.s.")
How do I fix? (was Re: Security proof) (Benjamin Goldberg)
Re: fun with solitaire (Rex Stewart)
Re: fun with solitaire (John Savard)
Re: fun with solitaire (John Savard)
A Special Deck of Encryption Cards (John Savard)
Re: Challenge/response with MD5 (Bryan Olson)
Re: NSA and Linux Security (Mok-Kong Shen)
Re: Cavell challenge #2 (Tom St Denis)
Re: future trends in asymmetric cryptography (Tom St Denis)
Re: multiple anagramming? (Benjamin Goldberg)
Re: A security proof for ECDSA (DJohn37050)
Re: fun with solitaire ([EMAIL PROTECTED])
Re: multiple anagramming? ("Brian Wong")
Re: fun with solitaire ("r.e.s.")
Re: A Special Deck of Encryption Cards (Benjamin Goldberg)
----------------------------------------------------------------------------
From: Jarno Huuskonen <[EMAIL PROTECTED]>
Subject: Key fingerprint algorithms ?
Date: 15 Jan 2001 21:07:54 +0200
Hi,
Does anyone have any pointers to the algorithm used in ssh 2.3.0/2.4.0 to
print out the sha1 fingerprint of ssh-keys ?
The ssh manuals say the algorithm is 'bubble babble' (it converts the
sha1 hash to 'words' like xyzzy-fuzzy- etc).
I guess I could reverse engineer the algorithm from ssh sources, but if the
algorithm is publicly available I'd rather get the algorithm from there.
Thanks,
-Jarno
PS. Could also mail the reply to [EMAIL PROTECTED]
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: fun with solitaire
Date: Mon, 15 Jan 2001 11:39:28 -0800
"John Myre" <[EMAIL PROTECTED]> wrote ...
| "r.e.s." wrote:
| <skip>
| > Is it possible to find a starting sequence that
| > will cause the Solitaire letter stream to begin
| > with "HELLOEARTHLINGS...", or perhaps
| > "THISISTHENSA..."? ;o)
|
| It seems unlikely to be able to match a non-trivial length
| sequence. This seems a lot like trying to find a (the) key
| for a known keystream, which is the same as breaking the
| cipher. Of course, you could regard this as a challenge...
The starting sequence for the deck is the key, so, yes,
this is trying to construct a key that will produce the
longest possible initial segment of a desired keystream.
Unlike decryption, though, there seems to be no assurance
that a key exists that will generate the desired stream.
It seems to me that for any given stream cipher, there
will be some maximum, say Lmax, to the length of initial
output segment such that, no matter what one requires
this initial segment to be, a key is guaranteed to exist
that will generate it. I'm not sure what this Lmax might
signify in terms of the cipher's performance. (?)
(Just for fun, I've tried working out a Solitaire key that
will produce "HELLOEARTHLINGS...", but, so far, I've only
succeeded to "HELLOEAR..." ;o)
--r.e.s.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: How do I fix? (was Re: Security proof)
Date: Mon, 15 Jan 2001 19:49:40 GMT
In my proposed scheme, I discovered a differential bias which causes the
construct to fail to be an SPRP if only one round of it is used.
If words are N bits, and one input word is changed, then in an SPRP,
each of the output words should have a nonzero output difference with
probability ((2**N-1)/(2**N)), and those changes should appear to be
independent.
With this construct, if one input word is changed, the probability of a
nonzero difference is ((2**N-1)/(2**N))**L (where L is the number of FFT
layers, and the log2 of the number of input words), and furthermore,
output differences of 0 are correlated in an easily detectible way.
Example:
Let us consider the 3 layer FFT, and one bit words. A one bit input
difference will result in each of the outputs changing with probability
1/8 -- MUCH below SAC.
Possible fix:
Use two+ rounds.
Problem:
Going into layer 1, each word has an input difference 1 with probability
1/8, and a difference of 0 with probability 7/8. Each mixer sees a 0
difference in both with probability 49/64, and a 1 difference in at
least one with probability 15/64. The probability of an output
difference of 1 is 15/128.
Urk. 15/128 is less than 1/8. Obviously I'm doing my math wrong, since
it seems as if the odds of a nonzero output difference seem to decrease
each round. At this rate, applying many rounds will result in all
ciphertexts being equal! Will someone tell me what I'm doing wrong?
Guessed reason for problem:
I *think* it has to do with the fact that, if there is a nonzero
difference to one or both of the inputs to a mixer, and if one of the
outputs has a zero difference, then the other output will, 100% of the
time, have a nonzero output difference.
When looked at *independently*, the probability of one of a 2x2 mixer's
output bits being nonzero is (1 - (1 - p)**2) * 1/2, where p is the
probability of a nonzero input bit difference.
Generalizing, when looked at *independently*, the probability of one of
an 2Nx2N mixer's output word differences being nonzero is (1-(1-p)**2) *
(2**N-1/2**N), where p is the probability of a nonzero input word
difference.
The problem is that input differences aren't independent. If one of the
two input words has a zero input difference, the other word is much more
likely to have a nonzero input difference.
Guessed solution:
Calculate the input difference probabilities based on the fact that
zeros are correlated.
Problem:
I have no clue how to do this.
Some thoughts:
Although I'm fairly certain that two rounds are enough to get SAC with 8
bit words, I don't know how to prove it, nor do I know how many rounds
are needed with 1 (or arbitrary N) bit words. Two? Three? How do I
calculate this?
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Rex Stewart <[EMAIL PROTECTED]>
Subject: Re: fun with solitaire
Date: Mon, 15 Jan 2001 19:37:33 GMT
Depends on what you mean by trivial here.
For one or two characters output it is pretty trivial.
It does get much more difficult as the string gets longer.
I have done it for four charactors, as part of an attempt
to get the cipher to "short cycle." I think I could do
it for a few more by hand. A computer should be able to
do it for a dozen characters.
This is not the same as breaking the cipher - as
there are many internal states that would produce
a particular 6 or even 12 char sequence.
--
Rex Stewart
PGP Print 9526288F3D0C292D 783D3AB640C2416A
In article John Myre <[EMAIL PROTECTED]> wrote:
> "r.e.s." wrote:
> <skip>
> > Is it possible to find a starting sequence that
> > will cause the Solitaire letter stream to begin
> > with "HELLOEARTHLINGS...", or perhaps
> > "THISISTHENSA..."? ;o)
>
> It seems unlikely to be able to match a non-trivial length
> sequence. This seems a lot like trying to find a (the) key
> for a known keystream, which is the same as breaking the
> cipher. Of course, you could regard this as a challenge...
>
> JM
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: fun with solitaire
Date: Mon, 15 Jan 2001 19:24:22 GMT
On Mon, 15 Jan 2001 16:17:19 GMT, Rex Stewart <[EMAIL PROTECTED]>
wrote, in part:
>(Yes, I know it is supposedly not truely reversable,
>but it is close enough to make it workable.)
As I recall, Solitare is reversible in one sense; while it is designed
so that you shouldn't be able to go from the sequence of outputs to
any state, it is possible to work from a state to previous states.
This was intentional, because if it had steps that worked like a hash
function, then information from the initial state would be lost as
outputs were generated.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: fun with solitaire
Date: Mon, 15 Jan 2001 19:43:30 GMT
On Mon, 15 Jan 2001 19:24:22 GMT, [EMAIL PROTECTED]
(John Savard) wrote, in part:
>As I recall, Solitare is reversible in one sense;
This stimulated me to look again at my own playing card cipher on my
web page, and I found an error in the example I gave; after the first
time, I forgot to apply the rule that red is lower than black. I've
corrected the example now.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: A Special Deck of Encryption Cards
Date: Mon, 15 Jan 2001 19:57:06 GMT
Thinking in terms of playing card ciphers, an idea occurred to me.
If one uses an elaborate Solitare-like scheme of scrambling the order
of a deck of cards, it would be convenient if it were possible to
encipher more than one letter of a message for each scramble.
If one were to give up the advantage of using an ordinary deck of
cards, obtainable anywhere, for this purpose, but were instead using a
special deck specifically designed for performing encryption, I
thought of an easy way to do this.
Let us suppose that each of the cards involved have, on one of their
long edges, a different scrambled alphabet, spaced evenly, repeated
twice.
Then, each re-ordering of the deck would produce a different key for a
*strip cipher*; that is, the edges of the cards could be used like a
Bazieres cylinder/Jefferson wheel cipher/M-94 to encipher a segment of
plaintext. One might use only, say, the first 25 or 36 cards.
And, just to make the nature of the deck less obvious - to make it
plausible that a deck of cards with such an unusual thing as scrambled
alphabets on the sides of it could serve a purpose other than
encryption - one could increase the size of the deck by 50%, which
would also have the effect of increasing the security of the cipher.
(The resulting deck, 50% larger than a normal deck without jokers,
would contain 78 cards, the number of cards in many quite bizarre
decks.)
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Challenge/response with MD5
Date: Mon, 15 Jan 2001 20:16:07 GMT
Ivan Skytte wrote:
> I am developing a challenge/response authentication
> which authenticates both ends.
>
> Each end generates a random 32-byte challenge. The
> first 4 bytes are not random - they are the current
> unix time (seconds since 1970). Otherwise
> it is as random as you can get on a determistic machine.
> Each end calculates the response by doing a MD5 over a
> shared secret and the challenge, and then sends the
> response to the other end.
If there's only one shared secret, I could wait for your
challenge, echo it, then wait for your response and echo it.
You could defeat that several ways: more explicit ordering, a
specific check, including an ID under the hash, or using a
different shared-secret for each direction.
> The stuff with the first 4 bytes was included to
> protect against replay attacks
A nonce (one-time value) makes a fine challenge. I don't see
any advantage to the long random string.
[...]
> I am considering changing response into two
> parts: yet another random block and the MD5 of
> the shared secret, the random challenge and the
> random block. Would this by more secure?
Arguably, but does this protocol really do what you want? It
ends with each side knowing he has interacted with the other.
There were no application-level messages. It's good for
secure ping, but that's about it. Most applications need to
tie the challenges to meaningful requests and responses.
For example suppose we have a different shared secret for each
direction, and we use a nonce as a challenge. With the
challenge I'm saying "I'll accept messages as authentic only
if they are MAC'ed using the key SHA1(shared_secret + nonce)."
Incidentally, RSA labs, birthplace of MD5, now recommends
against using MD5 in new applications, and suggests replacing
it with SHA-1.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Mon, 15 Jan 2001 21:38:33 +0100
digiboy | marcus wrote:
>
> > > I suppose that the truth of your sentence, when applied
> > > to any country, is conditioned on its status of democracy,
> > > which, BTW, might vary with time, as history shows.
>
> Quite. I was applying it to the current structures in UKUSA
> countries.
I am foreign and hence lack knowledge. But at least in
a couple of (anyway proclaimed democratic) countries of
which I know something, it is my impression that there
are 'networks' behind the official political scene and it
is very hard to tell who has what connections with whom
and how. Sometimes certain 'scandals' surface, revealing
a bit of the collaborations, and the journalists are joyous,
being able to show their talents, but that's evidently
only the tip of the iceberg. If such does not apply to
where you are living, then be happy and praise the
Allmighty that it is so.
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Cavell challenge #2
Date: Mon, 15 Jan 2001 20:26:16 GMT
In article
<[EMAIL PROTECTED]>,
Richard John Cavell <[EMAIL PROTECTED]> wrote:
> My second challenge is in rec.puzzles.
Stop posting puzzles to sci.crypt, or puzzle related news.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: future trends in asymmetric cryptography
Date: Mon, 15 Jan 2001 20:25:24 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jan Fedak) wrote:
>
> Hi guys.
>
> Do you have any good ideas? I should write a conclusion for my thesis
> till tomorrow and after some hard hours at work I feel empty...
>
> Thanks for any promotions.
You want to know where asymmetric crypto is going? So do I.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: multiple anagramming?
Date: Mon, 15 Jan 2001 20:46:04 GMT
<flame type=impersonal>
It's utterly astounding how often requests for online references result
in people responding with book references!
Call me an idiot, or cheap and impatient, but I don't see how something
which will cost quite a bit of money, and take a week or more to get,
and which has only one or two things I want, out of an entire book, is
supposed to help me on something I want help with now, in the next day
or so (and preferably without spending money).
When I ask for an online reference, there's a reason for it.
</flame>
However, I do appreciate very much, and thank you for, the description
of multiple anagramming you gave in your post. Perhaps someone (you or
Terry Ritter) could put this description on a web page?
For instance, you could add the description of multiple anagraming inder
the "Methods of Transposition" page (you mention it there, but don't
describe how to do it anywhere on your site), and Ritter could add a
"Multiple Anagraming" entry in his glossary (and also an entry for
"Transposition Cipher," which is a very odd thing to omit!)
--
Technology which is distinguishable from magic is insufficently
advanced. (Corrolary with Clark's Law).
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 15 Jan 2001 20:52:18 GMT
Subject: Re: A security proof for ECDSA
This is the one I was referring to before in sci.crypt. I did not realize it
was on the web, having seen a preprint.
Don Johnson
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: fun with solitaire
Date: Mon, 15 Jan 2001 20:49:18 GMT
In article <93vjkd$nb$[EMAIL PROTECTED]>,
"r.e.s." <[EMAIL PROTECTED]> wrote:
> "John Myre" <[EMAIL PROTECTED]> wrote ...
> | "r.e.s." wrote:
> | <skip>
> | > Is it possible to find a starting sequence that
> | > will cause the Solitaire letter stream to begin
> | > with "HELLOEARTHLINGS...", or perhaps
> | > "THISISTHENSA..."? ;o)
> |
> (Just for fun, I've tried working out a Solitaire key that
> will produce "HELLOEARTHLINGS...", but, so far, I've only
> succeeded to "HELLOEAR..." ;o)
>
> --r.e.s.
I've got code for doing the same thing with RC4 at
http://burtleburtle.net/bob/c/brute.c
Someday I ought to modify it to attack Solitaire.
One trick that should help is to start in the middle of the sequence and
work both forward and backward, rather than at the beginning and just
moving forward.
- Bob Jenkins
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Brian Wong" <[EMAIL PROTECTED]>
Subject: Re: multiple anagramming?
Date: Mon, 15 Jan 2001 15:55:43 -0500
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> <flame type=impersonal>
> It's utterly astounding how often requests for online references result
> in people responding with book references!
>
> Call me an idiot, or cheap and impatient, but I don't see how something
> which will cost quite a bit of money, and take a week or more to get,
> and which has only one or two things I want, out of an entire book, is
> supposed to help me on something I want help with now, in the next day
> or so (and preferably without spending money).
>
One word: library
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: fun with solitaire
Date: Mon, 15 Jan 2001 13:04:18 -0800
"John Savard" <[EMAIL PROTECTED]> wrote ...
| As I recall, Solitare is reversible in one sense; while
| it is designed so that you shouldn't be able to go from
| the sequence of outputs to any state, it is possible to
| work from a state to previous states.
| This was intentional, because if it had steps that worked
| like a hash function, then information from the initial
| state would be lost as outputs were generated.
In fact it isn't. As I recall, it was Paul Crowley who
pointed out that if the A-joker is second from the top,
then one can't tell whether its previous position was
the top card or the bottom card.
That's why I've have occassionaly complained that the
Counterpane site contains rather misleading information
in suggesting that it *is* reversible in the above sense.
--r.e.s.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: A Special Deck of Encryption Cards
Date: Mon, 15 Jan 2001 21:09:35 GMT
John Savard wrote:
[snip]
> And, just to make the nature of the deck less obvious - to make it
> plausible that a deck of cards with such an unusual thing as scrambled
> alphabets on the sides of it could serve a purpose other than
> encryption - one could increase the size of the deck by 50%, which
> would also have the effect of increasing the security of the cipher.
> (The resulting deck, 50% larger than a normal deck without jokers,
> would contain 78 cards, the number of cards in many quite bizarre
> decks.)
How many cards are in a Tarot Deck?
Another consideration, especially for the Tarot, is that right side up,
and inverted, mean two different things; Why not put a different
scrambled alphabet on each of the two long edges? Also, to make the
presence of the alphabet even less obvious, you might use the Latin
alphabet, rather than the English alphabet.
--
Technology which is distinguishable from magic is insufficiently
advanced. (Corollary with Clark's Law).
------------------------------
** 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
******************************
