Cryptography-Digest Digest #446, Volume #12 Tue, 15 Aug 00 04:13:00 EDT
Contents:
Re: chap authentication scheme? (Thomas Wu)
Re: Key in ASCII ?? ("Trevor L. Jackson, III")
Re: Impossible Differentials of TC5 (Ulrich Kuehn)
Re: The quick brown fox... (Mike Brown)
Re: chap authentication scheme? (Cryptocol)
Re: chap authentication scheme? (Cryptocol)
Re: Playfair-Analyze ? (Mark T. VandeWettering)
Re: 1-time pad is not secure... (Mark T. VandeWettering)
Re: chap authentication scheme? (Cryptocol)
----------------------------------------------------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Subject: Re: chap authentication scheme?
Date: 14 Aug 2000 23:08:04 -0700
[EMAIL PROTECTED] (Cryptocol) writes:
>
> Finally, I would like to show my solution.
>
> AA-CHAP:
>
> Alice has v while Bob stores g^v.
Aaron steals g^v from Bob's database.
> 1. Alice <-- g^x -- Bob
> 2. Alice -- g^y, h(g^xa) --> Bob
>
> a : amplified password such that a = y + v
> Bob verifies h((g^yg^v)^x) == h(g^x(y+v))
1. Aaron <-- g^x <-- Bob
2. Aaron --> g^y/g^v, h(g^xy) --> Bob
Bob verifies h(([g^y/g^v]*g^v)^x == h(g^xy).
> Both parties need two exponentiations.
> AA-CHAP is secure against passive attack and server compromise, not against
> fake Bob.
The server's verifier g^v is a password equivalent, since v is itself
not needed to convince Bob of the client's identity.
This same attack came up while I was designing SRP. I dubbed it the
"inverted verifier attack" and mentioned it in section 3.2.4 of my
paper.
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
Date: Tue, 15 Aug 2000 02:29:00 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Key in ASCII ??
Guy Macon wrote:
> Trevor L. Jackson, III wrote:
>
> > With respect to your dictionary search, single words are not English
> > text. There is insufficient context to limit the information to a
> > single bit per character. After all, there are far more than 256
> > eight-letter words in English. However, a random sequence of
> > eight-letter words is hardly English text.
>
> Let me see if I amm getting this straight. Are you saying that
> in the following text string:
>
> "With respect to your dictionary search, single words are not English
> text. There is insufficient context to limit the information to a
> single bit per character. After all, there are far more than 256
> eight-letter words in English. However, a random ******** of
> eight-letter words is hardly English text.", that there are roughly
> 256 8 character words that can replace "********"? (In the general
> case over many english text strings, of course.) I can see that.
I have no idea. Might be. That part of the discussion was aimed at dissing
your examples not mine. ;-)
For these kinds of tests I think one is supposed to use only trailing
context. So the prediction of the next word would be based upon "... words in
English. However, a random ????????".
The metric of one bit per character is supposed to indicate that if you take a
body of typical English text (I suppose the Brown corpus might suffice) the
ability to predict the next character based on the previous letter frequencies
is 50% accurate. The phrase "The quick brown fox jum" might be followed by a
'p' or something else (like "bled the alphabet.")
You may want to look at the languages you get when generating random text
based upon the statistics of text samples. With a zero-width trailing window
one gets a uniform distribution. With a single character window one gets
syllables, the beginning of suggestive text. With a five character window one
gets a distortion of english. I think at the eight character size you get to
play games with the stylistic aspects of the language such as
British/American, education level, geographic regions, etc. All of these
stats are from memory, so they aren't reliable.
In addition to the window width the size and homogeneity of the sample text
makes a big difference.
It is precisely the redundancies of English that allow this type of
constructive model. Those redundancies are what takes up the other bits of
the characters. All of the parity bits are going to be zero, so that bit is
trivially wasted. Almost all of the text will be lower case characters, so
we're down to 5 bits including the escape codes for the rare characters. When
you take average character frequencies into account the value of a character
drops to just over 3 bits. When you takes those frequencies _in_context_ the
value drops to the single bit range.
Take it the other way around. If there were 7 bits of information in each
character we'd have a uniform distribution. We don't have a uniform
distribution of characters. So the information density (bits of info/bit of
data) is less than unity.
------------------------------
From: Ulrich Kuehn <[EMAIL PROTECTED]>
Subject: Re: Impossible Differentials of TC5
Date: Tue, 15 Aug 2000 08:43:35 +0200
Reply-To: [EMAIL PROTECTED]
tomstd wrote:
> So this means you must send the 128-bit difference
>
> (0,0,0,0,0,0,0,0,0,0,0,0,0,0,d1,d2)
>
> After the first 32-bit feistel we want an output difference of
> (first round of the 64-bit feistel) The probability of this is
> very low about ((2^-6)^5)^3 = 2^-90.
>
Do not get confused about the 32 bit feistel. Just think in generic
terms of a 5 round feistel network. (I am using here a model where
the right half is put through f, before being XORed to the left half).
I am repeating here the arguments of Knudsen's DEAL paper (please look
that one up!). Assume that f is bijective, so an output diff of 0 can
only come from an input diff of zero.
An input difference (a, 0) with nonzero a causes, before the second
round, the diff of (0, a) by 0->0 through f. Then, with a->b for some
nonzero b, thus, before the third round, we have the diff of (b, 0)
where the diff b is to be input to f.
Ok, now lets take a look at the output. Assume we have an output diff
of (a, 0) with the same a as above. Thus, as the input to f has diff 0,
before the last round (after the swap) the diff must have been also (a,
0). The round before the input diff to f must have been a, so f gives
a->b' with some nonzero b'.
But then the round before, at the input to f, we must have had an input
diff of b', and from the above forward argument we had the input diff b,
thus b=b'. The output diff of f in the third round must be 0, but that
is impossible as f is bijective.
That is all. Hope this help to resolve your confusion.
Ulrich
> (0,0,0,0,0,0,0,0,0,0,0,0,d3,d4,d1,d2)
>
> When the 32-bit right half gets xored to the 64 bit block at
> this point we find the 128-bit difference is now
>
> (0,0,0,0,0,0,0,0,d3,d4,d1,d2,d3,d4,d1,d2)
>
> Then in the next round of the 64-bit feistel the left half
> (d3,d4,d1,d2) will go into the 32-bit feistel. This is not the
> required (0,0,d1,d2) as described by M.Wooding.
>
> This is where I get confused....
>
> Tom
>
> -----------------------------------------------------------
>
> Got questions? Get answers over the phone at Keen.com.
> Up to 100 minutes free!
> http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (Mike Brown)
Subject: Re: The quick brown fox...
Date: Mon, 14 Aug 2000 14:30:28 GMT
Reply-To: [EMAIL PROTECTED]
In message <[EMAIL PROTECTED]> Anders Thulin wrote:
> wtshaw wrote:
>
> > Requiring the whole alphabet, does anyone know of other alternatives,
> > perhaps shorter ones and with no increase in nonsense content?
>
> You may want to try comp.fonts. When I was lurking in that newsgroup
> a few years ago, one of the posters had that kind of sentences in
> his signature -- usually a new one every time.
>
Here is my collection, gathered piecemeal over the course of many years,
the original sources long since forgotten. The first 10 are shorter
than the traditional QBF. Also included are some examples resuling from
the so-called 'calligraphy' party game, where the object is to construct
'sensible' pangrams including a specified word.
Bright vixens jump; dozy fowl quack.
How quickly daft jumping zebras vex.
Quick bright vixens jump a dozy wolf.
Jackdaws love my big sphinx of quartz.
Prize fowl vexed him just by quacking.
Waltz, dumb nymph, for quick jigs vex.
The five boxing wizards jumped quickly.
Brazen old wives fight a quick jumpy ox.
Pack my box with five dozen liquor jugs.
Sympathizing would fix Quaker objectives.
The quick brown fox jumps over the lazy dog.
Jail zesty vixen who grabbed pay from quack.
Dumpy kibitzer jingles as exchequer overflows.
Brawny gods just flocked up to quiz and vex him.
Martin J Hixeypozer quickly began his first word.
Jim just quit and packed extra bags for Liz Owen.
A large fawn jumped quickly over white zinc boxes.
Many big jackdaws quickly zipped over the fox pen.
The vixen jumped quickly on her foe barking with zeal.
The fox, jaw bleeding, moved quickly, dazing his prey.
Five or six big planes zoomed quickly by the new tower.
The exodus of jazzy pigeons craved by squeamish walkers.
The very bent, jacknifed forms were quizzically perplexing.
Raquets give a quick buzz to sexy players who find jokes lame.
The kings amazingly poised equerry advanced with javelin fixed.
Alfredo just must bring very exciting news to the plaza quickly.
Anxious Paul waved back his pa from the zinc quarry just sighted.
Dance experts would be amazed by his feverish jerking and quaking.
He jokingly removed porcupine quills from a zebras back with wax.
Picking just six quinces, the new farmhand proved strong but lazy.
Now is the time for all quick brown dogs to jump over the lazy fox.
The judo expert grapples quickly, but with zeal, felling seven men.
Using axes, lumberjacks very quickly felled the wizards pine forest.
The brazen jackal querulously attacked a feral vixen, maiming her paw.
Four or five puzzle-box locks can be opened quickly with just magnets.
Xenophobes know unequivocally that magnetization jeopardizes folklore.
The jovial yokel found six zealots praying and backed qualmishly away.
Karate experts bring down victims with just a few amazingly quick chops.
The fabled Quetzal roosted on a mulberry twig, vexing the peevish
jockey.
Venerable Will played jazz sax til 3 oclock in the morning before
he quit.
The exiled queen, justly moved, celebrated with a dazzling fireworks
display.
Despite being haunted by the wizards jinx, the quartet performed ver
y slickly.
Troubled by the voodoo hex, the jazz men packed their gear and went off
quickly.
The knowledgeable superintendent amazed us by quickly fixing the five
pipe joints.
Our sixth earthquake just split five buildings, leaving hazard in its
stormy wake.
Someone just asking was quite pleased with our gifts of a zebra and a
clever oryx.
As we explored the gulf of Zanzibar, we quickly moved closer to the
jutting rocks.
Travelling beneath the azure sky in our jolly ox-cart, we often hit bumps
quite hard.
Obsequious kowtows with each word are just examples of Ezras unctuous
grovelling ways.
Curious and wily journalists braved the fury of six brazen knaves
picketing the mad queen.
Their kind aunt was subject to frequent dizzy spells, thus causing much
anxiety and worry.
After quizzing her, he justly blamed anorexia nervosa as the cause of all
her known problems.
William said that everything about his jacket was in quite good condition
except for the zipper.
The daredevils quivered, knowing this rube would commit the faux pas of
dozing when they jumped.
The junior office clerks were quite amazed at the extra reward given by
their generous employer.
The jittery killer immobilised his victim with a wax-filled hypodermic
syringe, then drove off quickly.
The vegetarian menu included gazpacho, piquant julien beets, rusk rounds
with yoghourt, and excellent flan.
Calligraphic Pangrams:
Calligraphic wizardry expounds a quiet but rhythmic flow eschewing jerky
movements.
Justly vexed, the Queen exiled the calligrapher who spattered some black
ink on her dog.
Five men, using just penknives, would cut the sixty quills needed by a
dozen calligraphers.
Calligraphy requires just a very few basic needs: pen, ink, dexterity,
and most of all zeal!
Calligraphers see words as exquisitely moving, subtle thicks and thins,
of zigzags and joins.
Im jealous of any calligrapher who writes with zest, exuberance, freedom
and unequivocal skill.
He wrote deftly and quickly, just amazing us with his expertise and his
unabashed love of letters.
Six calligraphers just amazed, watched children busily cutting quills with
their favourite penknives.
Regards to all readers,
Mike.
--
M J D Brown: Newhaven, Peterchurch, Herefordshire HR2 0RT, England
------------------------------
From: [EMAIL PROTECTED] (Cryptocol)
Date: 15 Aug 2000 06:54:19 GMT
Subject: Re: chap authentication scheme?
I would like to summarize AA-CHAP as follows. If anybody has a comment, please
send me an email. ([EMAIL PROTECTED]) Personally I don't think this
two-pass protocol is so useful but I hope it meets the requirements posted
here. I hope we don't waste our time by my poor proposal.
<Thanks Tom, I missed that kind of attack. I also experienced it while I was
designing AMP. Mr. David Jablon kindly pointed it out at that time. Of course,
I modified AA-CHAP as I did in AMP. It's so simple.> huh, I think we need a
good formal proof method some day. :)
[Posted Goal]
Strengthen CHAP in a very restricted environment, like a puzzle; (edited from
the rules requested by Mr. Bill Unruh in sci.crypt NG)
a) No cleartext storage of passwords on the server. --> No text-equivalence for
authentication and verification
b) Two message pass --> 1)Challenge from server where the server does not know
who is calling in. 2)Response from client to deliver the identifier(id) as well
as the verification information.
c) Maximise the security, both against eavesdropping, spoofing and server
comprimise. --> Two pass protocol cannot help allowing fake BOB.
[[ AA-CHAP ]]
- Strengthening CHAP
- Evolved from A-CHAP
- Based on the AMP's idea; the amplified password proof
[Protocol Setup]
A client ALICE and a server BOB agree on the global parameters; a prime modulus
p such as a safe prime or a secure prime, a prime factor q of p-1, and a
generator g of Z_q.
ALICE keeps a password P.
BOB stores its verifier g^v mod p.
Note: v=f(P) for a good one-way function f() that expands and perturbs P to a
secure exponent.
[Protocol Run]
1. ALICE <-- g^x -- BOB (Challenge)
BOB chooses x at random from Z_q - {0,1} and computes g^x mod p
BOB sends g^x to ALICE
2. ALICE -- id, g^y, h(g^xa) --> BOB (Response)
ALICE chooses y at random from Z_q - {0,1} and computes e = h(g^x,g^y).
ALICE computes an Amplified Password "a" such that a = ye + v mod q. (ALICE
must have computed v = f(P) while waiting for message 1 from BOB)
ALICE computes and sends g^y, h((g^x)^a) to BOB.
BOB fetches g^v and computes e = h(g^x,g^y).
BOB computes (g^ye * g^v)^x; this can be done efficiently by the
simultaneous exponentiation method, i.e., ((g^y)^ex * (g^v)^x)
BOB compares h((g^yg^v)^x) to h(g^xa); if h((g^yg^v)^x) == h(g^x(y+v)) then
BOB authenticates ALICE.
[Safety Guards]
g^x == {-1,0,1}, g^y == {-1,0,1}
Note: Of course, BOB is able to send ALICE the global parameters (g,p,q) in
each step 1 but then it may burden ALICE because she has to test them for
security reasons.
[Security]
secure against
- passive dictionary attacks
- server compromise (require dictionary attacks)
vulnerable against
- server impersonation (fake BOB)
[Computation]
ALICE computes; BOB computes;
v = f(P)
# g^y mod p g^x mod p
e = h(g^x,g^y)
a = ye + v mod q
# (g^x)^a mod p
h((g^x)^a) e = h(g^x,g^y)
# (g^y)^ex * (g^v)^x mod p <- simultaneous exponentiation
h((g^yg^v)^x)
h((g^yg^v)^x) == h((g^x)^a)
Note: # implies expensive computations.
[History]
- The first version of A-CHAP had message 2 twice as big as message 1 and was
vulnerable to server compromise because of text-equivalence.
--> message size was solved by hashing g^y, i.e., h(g^y), in message 2.
- The hashed version of A-CHAP was still vulnerable to server compromise
because both party handled v.
--> vulnerability was solved by simple modification; making ALICE handle the
amplified password while BOB handle the verifier, i.e., modified message 2 of
A-CHAP, (g^xg^v)^y,h(g^y) --> g^y,h(g^x(y+v)); transpose (g^xg^v)^y andg^y,
again transpose x and y, for making ALICE handle the amplified password as we
did originally in AMP.
- The modified version was vunerable to the attack that I missed; Tom Wu kindly
pointed out the vulnerability.
--> again, I corrected the protocol as I did in designing AMP. ;)
- That is AA-CHAP!
[Note]
I think Tom Wu's solution is also wonderful and similar though it is came from
a little different idea.
[Reference]
http://www.integritysciences.com/links.html : a plentiful source of password
authentication research.
http://eprint.iacr.org/2000/026 : AMP paper for the amplified password proof
idea.
------------------------------
From: [EMAIL PROTECTED] (Cryptocol)
Date: 15 Aug 2000 07:04:38 GMT
Subject: Re: chap authentication scheme?
sorry, typo ;)
In protocol run step 2,
BOB compares h((g^ye*g^v)^x) to h(g^xa); if h((g^ye*g^v)^x) == h(g^x(ye+v))
then BOB authenticates ALICE.
------------------------------
Subject: Re: Playfair-Analyze ?
Reply-To: [EMAIL PROTECTED]
From: [EMAIL PROTECTED] (Mark T. VandeWettering)
Date: Tue, 15 Aug 2000 07:13:37 GMT
In article <[EMAIL PROTECTED]>,
JPeschel <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] (Ronny Burow) writes, in part:
>
>>Now i need some help with Playfair. Where can i get
>>a simple description how to analyze a playfair-chiffre ?
>
>You can find the Lanaki lessons on my web site on the
>"Crypto lessons" page. You'll also find a Playfair
>cracking tool on the "Historical" page.
If you want to "cheat", I had good luck using both genetic algorithms
and simulated annealing type approaches. Even simpler programs can be
effective. For instance, to solve the Playfair that was part of Singh's
Cipher Challenge, I took my favorite bit of English prose (Bram Stoker's
Dracula, available from Project Gutenberg). I collected counts on all
trigrams for the novel. I then took the log of the raw counts base 2,
and called that the score. My program proceeds by picking a random
encoding square. It scores the square by decrypting the message, totalling
all the scores for each trigram in the decoded message. It then searches
for the pair of letters to swap that increases the score the most, and repeats.
The problem with this method is that it often settles into local maxima, so
when you can't find a better swap, I just pick two random pairs and swap them,
and repeat. With a reasonable amount of cipher text, this was pretty
successful, easy to code, and sufficient to break the Stage 6 code.
For more fun, I went back and redid it with more "proper" SA and genetic
algorithms.
Mark
------------------------------
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
From: [EMAIL PROTECTED] (Mark T. VandeWettering)
Date: Tue, 15 Aug 2000 07:32:50 GMT
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
>Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>We don't agree at all.
>
>Any process that appears random may be the deterministic outcome of events
>at a lower level. The rational scientist can't currently say one way or
>the other about whether there is determinism in physics - he plain doesn't
>know.
Quantum mechanics addresses this issue. It disagrees with you. Please
post your refutation of quantum mechanics, and the Nobel committee will
send you your prize in the return mail.
Mark
------------------------------
From: [EMAIL PROTECTED] (Cryptocol)
Date: 15 Aug 2000 07:33:56 GMT
Subject: Re: chap authentication scheme?
I apologize to whom is busy. So, I would like to add the simplified description
of AA-CHAP for convenience.
AA-CHAP:
1. ALICE <-- g^x -- BOB
2. ALICE -- id, g^y, h(g^xa)
note: "a" is an amplified password such that a = ye + v mod p
p is a safe prime or a secure prime modulus
e = h(g^x, g^y) for a strong one-way hash function h()
v = f(P) for a one-way function f() and a password P
ALICE keeps P and computes v = f(P) for authentication.
BOB stores V = g^v for verification.
BOB gets m1 = g^x.
BOB sends m1 to ALICE.
ALICE gets m2 = g^y
ALICE gets e = h(m1,m2).
ALICE gets a = ye + v
ALICE gets m3 = (m1)^a = g^xa.
ALICE sends m2, h(m3) to BOB.
BOB gets e = h(m1,m2).
BOB gets m4 = ((m2)^ex * (V)^x) = g^(ye+v)x. <-- simultaneous exponentiation is
preferred, but if not, that's okay with serial computation.
If h(m4) == h(m3), BOB authenticates ALICE.
Note: m4 = g^(ye+v)x = g^ax = g^xa = m3.
AA-CHAP is secure against server compromises (needs dictionary attacks) as well
as passive attacks; finally, fake BOB needs dictionary attacks but we cannot
say it is secure against fake BOB. :)
-- The End --
------------------------------
** 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
******************************
