Cryptography-Digest Digest #339, Volume #11 Wed, 15 Mar 00 12:13:02 EST
Contents:
Re: Q: Coding of music notes ("Tony T. Warnock")
Re: new/old encryption technique (John Myre)
Re: Question about Blowfish source code in "Applied Cryptography" (John Myre)
Special One way function ([EMAIL PROTECTED])
Re: Universal Language (Boris Kazak)
Looking for a special one way function ([EMAIL PROTECTED])
Re: pedagogical provably stupid protocols (John Myre)
Re: My 2 pennies (How to introduce...) (Boris Kazak)
Re: Special One way function (Volker Hetzer)
Re: sci.crypt Cipher Contest (Boris Kazak)
Re: Cheating in co-operative open-source games, how can we protect from it? ("Kasper
Pedersen")
Re: Cheating in co-operative open-source games, how can we protect from it? ("Kasper
Pedersen")
----------------------------------------------------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Q: Coding of music notes
Date: Wed, 15 Mar 2000 08:11:57 -0700
Reply-To: [EMAIL PROTECTED]
There was an industry wide attempt called NIFF. The problem was that the
vendors still preferred their propriatary representations.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: new/old encryption technique
Date: Wed, 15 Mar 2000 08:46:18 -0700
> perform ROT-16, ROT-1, ROT-14, ROT-20, ROT-4, ROT 6.
Equivalent to performing ROT-9 by itself.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Question about Blowfish source code in "Applied Cryptography"
Date: Wed, 15 Mar 2000 09:00:22 -0700
Night Heir wrote:
<snip>
> blf_enc(&c,data,5)
> blf_dec(&c,data,1)
> blf_dec(&c,data+2,4)
<snip>
> I understand that blf_key performs initialization for the encryption and that
> blf_enc encrypts 5 bytes of data.
No. It encrypts 5 *blocks* of data, which is 10 words, which is
40 bytes - that is, all of data[].
> What I do not understand is why the
> decryption in blf_dec has been performed in two parts one consisting of 1 byte
> and the second consisting of 4 bytes.
Decrypts the first block and then the other 4 blocks. Just a little
test that you can do it in pieces; perhaps certain coding bugs are
caught this way. It isn't important. (Well - it's important that the
code work; I mean that there isn't anything subtle or mysterious here).
He could just as well have decrypted the last 2 blocks and then the
first 3, for example; or decrypted various parts in 3 steps. Certainly
it would work to decrypt all 5 words at once, too.
<snip>
John M.
------------------------------
From: [EMAIL PROTECTED]
Subject: Special One way function
Date: Wed, 15 Mar 2000 16:01:35 GMT
I am looking for a one way function f that has the
following properties:
f f f f f f
A1 ---> A2 --->A3 ---> A4 ---> A5 --->... ---> An
where Ai=f(Ai-1).
Assume the computation cost of f is C, then
generally caculating An from A1 needs a cost of
O(n). Is there any special kind of one way
function that can reduce this cost to O(1) or
O(log(n)).
Thanks,
Shine
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Universal Language
Date: Wed, 15 Mar 2000 16:12:55 GMT
Richard Herring wrote:
>
> In article <8am56f$u$[EMAIL PROTECTED]>, Mike McCarty
>([EMAIL PROTECTED]) wrote:
> > In article <8alge4$g6d$[EMAIL PROTECTED]>,
> > Richard Herring <[EMAIL PROTECTED]> wrote:
> > )In article <[EMAIL PROTECTED]>, Mok-Kong Shen
>([EMAIL PROTECTED]) wrote:
>
> > )> and Russian is even more complicated in my view.
> > )
> > )Arguable. Six cases, but only two aspects and two tenses.
>
> > [snip]
>
> > Err, seven cases. Though they are not fully represented.
***(?!?)*** BNK
>
> Nominative, accusative, genitive, dative, instrumental, prepositional.
> Which one did I miss?
>
> --
> Richard Herring | <[EMAIL PROTECTED]>
***********************
Absolutely correct, I confirm it as a native Russian speaker,
although the conventional order in Russian grammar textbooks
is a bit different:
Nominative
Genitive
Dative
Accusative
Instrumental
Prepositional
Best wishes BNK
------------------------------
From: [EMAIL PROTECTED]
Subject: Looking for a special one way function
Date: Wed, 15 Mar 2000 16:14:05 GMT
I am looking for a special one way function that has the following
properties:
Assume f is the one way function, the computation cost of f is C.
Xi+1 = f(Xi)
Generally, compute Xn from X1 needs computation cost (n-1)C, which is in
the order of O(n). Here is my question: Is there any one way function
that can computer Xn from X1 at a cost of O(1) or O(lgn)?
Thanks,
Shine
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: pedagogical provably stupid protocols
Date: Wed, 15 Mar 2000 09:27:22 -0700
David A Molnar wrote:
>
> Does anyone know of any simple examples of protocols which can be
> "proved" or otherwise convincingly and *correctly* argued as "good" --
> but according to a fatally flawed definition of goodness?
Here's one that I like, although it probably isn't simple enough.
Recall Biham and Anderson's BEAR and LION? They actually proved
them secure, under certain assumptions. The notion of security
was that you couldn't figure out the key. However, the LION
definition allowed a usage[1] where the key did not affect the result
at all; the proof holds (you still can't find the key!) but you
don't have much secrecy.
As you say, the problem is in the definitions.
John M.
[1] The trick is to try to use LION on a very short message; where
the size of the right part is zero. This, of course, has nothing
to do with the intended use of LION, where the right part is very
large. A similar weakness exists for BEAR, and even "very short"
(non-zero, but only a few bits) right sides are a problem.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: My 2 pennies (How to introduce...)
Date: Wed, 15 Mar 2000 16:34:05 GMT
[EMAIL PROTECTED] wrote:
>
> I want to design one or two lessons for 12th grade students majoring in
> computer science, that will introduce them to the basic concepts,
> problems, and ideas of cryptography. The activity can include anything
> from a computer lab session to group activity or perhaps even a
> cryptosystem competition of some sort.
> If you have any creative, engaging, interesting ideas please share them
> with me. Where would you start? what do you think is most important?
> what should my goals be?
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
*****************************
(My 2-pennies-worth, this can be a topic in your lesson.)
Among various transposition systems one certainly worth noting
is
the rectangular grille cipher. Its origin is largely unknown to me, but
it
was very popular in the 19-th century among Italian and Russian
revolutionaries.
The principle of this cipher is best understood with an example.
A revolutionary emissary wants to send a message:
MEETING IN PALERMO ARRESTED CHELENTANO TRAITOR CLOSE ANTONIO HOUSE
SILVAN
obviously without any spaces, commas, dots etc. Here is the method he
uses.
The following sketch represents an 8x8 square, where 16 of 64
small squares are punched out, and the remaining are in place, holding
the
system together. In practice such a grille would be cut of a paper sheet
with the help of a knife or small scissors.
-----------------------
|WW| |WW|WW|WW|WW| |WW|
|--|--|--|--|--|--|--|--|
|WW| |WW| |WW| |WW|WW|
|--|--|--|--|--|--|--|--|
|WW|WW|WW| |WW|WW|WW| |
|--|--|--|--|--|--|--|--|
| |WW|WW|WW| |WW|WW|WW|
|--|--|--|--o--|--|--|--|
|WW|WW|WW|WW|WW| |WW|WW|
|--|--|--|--|--|--|--|--|
|WW| |WW|WW|WW| |WW| |
|--|--|--|--|--|--|--|--|
|WW|WW|WW| |WW|WW|WW|WW|
|--|--|--|--|--|--|--|--|
|WW|WW|WW|WW| |WW|WW| |
-----------------------
Our emissary starts writing. He places the grille on a blank
page
and pins the middle of it to the paper (the small "o" in the center). He
writes the letters in the openings, one letter per square. The message
reads now:
M E
E T I
N G
I N
P
A L E
R
M O
Not much of a ciphertext yet, the words are clearly visible. But
wait, the emissary turns his grille 90 degrees clockwise. All the
letters
already written are now hidden under the grille, and punched holes open
new places for writing. The message continues:
M A E
E R T I R E
N G
I S N T E
D C P
A H E L L E
R E
N T M A O
That's already much better, but this is only half of the story.
The
emissary turns the grille another 90 degrees clockwise and keeps
writing:
N M O A E
E R T T I R E
R A N I G
I S T N T E
D O C P R
C A H E L L L E
O R S E N
T A A M N N O
And here the grille turns another 90 degrees:
N M T O A O E N
I E R T T I R E
R O A N H O I G
I S T U N T E S
D E S O C P I R
C A H E L L L E
L V O R S A E N
T A A N M N N O
Obviously, deciphering is the same as enciphering, the recepient
just
reads the scrambled message through the grille, rotating it 90 degrees
in
order to read the next section.
Now let us look at the grille in more detail. In particular let
us
figure out how the grille spacings are positioned and how many different
grilles of a given size can be constructed.
In order to do this, let us draw the square grille as if it
consists
of 4 quadrants, each one comprising 16 small squares numbered from 1 to
16.
Quadrant 1 Quadrant 2
-----------------------
| 1| 2| 3| 4|13| 9| 5| 1|
|--|--|--|--|--|--|--|--|
| 5| 6| 7| 8|14|10| 6| 2|
|--|--|--|--|--|--|--|--|
| 9|10|11|12|15|11| 7| 3|
|--|--|--|--|--|--|--|--|
|13|14|15|16|16|12| 8| 4|
|--|--|--|--o--|--|--|--|
| 4| 8|12|16|16|15|14|13|
|--|--|--|--|--|--|--|--|
| 3| 7|11|15|12|11|10| 9|
|--|--|--|--|--|--|--|--|
| 2| 6|10|14| 8| 7| 6| 5|
|--|--|--|--|--|--|--|--|
| 1| 5| 9|13| 4| 3| 2| 1|
-----------------------
Quadrant 4 Quadrant 3
The actual design is very simple. One of four squares #1 is
punched
out, then one of four squares #2, and so on until there will be 16 holes
comprising all the numbers. It should be obvious that in 4 rotations all
64 places will be covered, 16 at a time.
This procedure immediately answers the question about the total
number of possible grilles. Since there are 4 different possible
positions
for each hole, the total number of combinations is equal to 4^16 or
2^32,
in other words about 4 billion different grilles size 8x8 are possible.
Bigger grilles will provide better security due to larger number
of possible combinations, for example a 10x10 grille has 2^50 variants,
or about 10^15 - 250,000 times more than 8x8 grille.
Grilles need not be square, rectangular grilles can be made
which
can be better suited to the paper sheet size. An example of a 4x6 grille
template shows that the numbering system is slightly changed - adjacent
quadrants are now numbered as a mirror image of one another.
-----------------
| 1| 2| 3| 3| 2| 1|
|--|--|--|--|--|--|
| 4| 5| 6| 6| 5| 4|
|--|--|--|--|--|--|
| 4| 5| 6| 6| 5| 4|
|--|--|--|--|--|--|
| 1| 2| 3| 3| 2| 1|
-----------------
The design is basically the same, one of four squares #1 is
punched
out, then one of four squares #2, and so on until there will be 6 holes
comprising all the numbers. The usage, however, is a little different -
after the first section is written, the grille must be turned 180
degrees,
after the second section it must be flipped over, after the third
section it
must be again rotated 180 degrees. Readers are welcome to experiment and
to find out the proper usage of the grilles of different kinds.
Now the last (but not least important) subject. How can the
grille
be memorized, so that our amateur cryptographer would not carry around
the
actual grille or a picture of it in the pocket? A method exists which
makes
use of the binary numbering system.
Taking as an example the 8x8 grille used by Mr. Silvan, one can
write down the position of its holes as 8 binary numbers, where 1 stands
for the hole and 0 stands for the solid paper:
01000010 = 42 hex = 66 decimal
01010100 = 54 hex = 84 decimal
00010001 = 11 hex = 17 decimal
10001000 = 88 hex = 136 decimal
00000100 = 04 hex = 4 decimal
01000101 = 45 hex = 69 decimal
00010000 = 10 hex = 16 decimal
00001001 = 09 hex = 9 decimal
Hex numbers or decimal numbers are easy to memorize, to pass to
a
partner, and what is most important, the 8 numbers allow to easily
reconstruct the original grille whenever it is needed.
An alternative way is to write down the numbers of the quadrants
where successive holes have been punched. In case of Mr. Silvan's grille
the
sequence will be:
3 1 2 3 2 1 4 1 3 2 3 1 1 4 3 2
just like a long telephone number, and can be disguised as such in a
notebook:
(31)-232-1-413-321-1432
In the expert opinion of contemporary cryptanalysts, grilles
alone
do not provide adequate security, which is due to the fact that
transposition
ciphers do not change the alphabet codes relative frequencies. However,
in
my humble opinion, short delay is sometimes all that is needed. Imagine
that
it would take carabineros 2 days to break Mr. Silvan's code and to read
the
message. By this time unlucky Chelentano with his throat slashed would
be
already feeding the octopuses at the bottom of the Bay of Naples,
marshals
raiding the Antonio House would find it abandoned, and Silvan would
already
be known as Pietro and would use another grille out of 4 billion
possible.
Finally, the combination of Vigenere polyalphabetic substitution
with
a subsequent grille permutation is to be taken VERY seriously...
Presented by Boris N. Kazak
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Special One way function
Date: Wed, 15 Mar 2000 16:45:59 +0000
[EMAIL PROTECTED] wrote:
>
> I am looking for a one way function f that has the
> following properties:
>
> f f f f f f
> A1 ---> A2 --->A3 ---> A4 ---> A5 --->... ---> An
>
> where Ai=f(Ai-1).
>
> Assume the computation cost of f is C, then
> generally caculating An from A1 needs a cost of
> O(n). Is there any special kind of one way
> function that can reduce this cost to O(1) or
> O(log(n)).
I don't know, but I think I saw a paper by Bruce Schneier where
he showed that every cryptographically secure hash can not
be short-circuited in the way you want.
He used it for a password generating scheme that required
less password bits while still beeing reasonably secure
(but weaker than a longer password).
Have a look at http://www.counterpane.com/low-entropy.pdf .
Greetings!
Volker
--
Hi! I'm a signature virus! Copy me into your signature file to help me spread!
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: sci.crypt Cipher Contest
Date: Wed, 15 Mar 2000 16:55:15 GMT
"Trevor L. Jackson, III" wrote:
>
> Boris Kazak wrote:
>
> > I would like to submit there something that can be called a
> > "Proposed Universal Key Scheduler" based on a 64-byte shift register
> > and multiplication (mod 2^32+1). This procedure can accept any key
> > lengths up to 512 bit and can produce an arbitrarily long sequence of
> > randomized subkey bytes (full avalanche, change of 1 bit in key changes
> > all subkeys).
>
> If you use 66 bytes the function is trivial, needs no multiplication, and runs
> at almost maximum bus speed. The 521/32 LFSR with simple sampling meets all
> of your criteria.
>
**********************
Excellent, this makes already an assortment of possible key schedulers.
Notice how frequently attacks against various ciphers boil down to
attacks
against their key schedules - the whole term "Related key attack" comes
from there...
On the other hand, my proposal is very handy for ciphers based on
modular multiplication - the MODMULT routine is already there, a little
slowdown is not important (it can be even thought of as an advantage -
slow key scheduling discourages trial-and-error attacks).
Best wishes BNK
***************************
> >
> > I am eager to look at other submissions.
------------------------------
From: "Kasper Pedersen" <[EMAIL PROTECTED]>
Subject: Re: Cheating in co-operative open-source games, how can we protect from it?
Date: Wed, 15 Mar 2000 17:06:19 GMT
<[EMAIL PROTECTED]> wrote in message
news:8ahmct$e9e$[EMAIL PROTECTED]...
> In article <A9Py4.1453$[EMAIL PROTECTED]>,
> Kasper Pedersen <[EMAIL PROTECTED]> wrote:
> >When clientA receives status about clientB (what? He had 200 hp before, I
> >hit him 500, but he's still 200!?), he can vote that player as cheater.
If
> >enough clients vote him as cheater, that character gets banned.
>
> Wonderful! Then I'll get together with N of my friends and we'll all hack
> our clients - NOT to submit false character data, we'll submit honest
> character data, but we'll submit false "cheater" votes against people we
> don't like. Then you have to have a vote on cheating in the anti-cheating
> protocol, and we can cheat in that vote too, so you need another layer of
> voting, and so on.
As you might have noticed, I noticed that too!
So in the last part of the description the supposed cheater is just
INVESTIGATED, not kicked outright (as I thought of first).
What you are talking about is a game too - and a mighty fun one. (For a game
of MudHackWar to work, the server must be very very robust.)
------------------------------
From: "Kasper Pedersen" <[EMAIL PROTECTED]>
Subject: Re: Cheating in co-operative open-source games, how can we protect from it?
Date: Wed, 15 Mar 2000 17:06:20 GMT
"NFN NMI L." <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> <<Only MD5 required>>
>
> Why do people have this MD5 fetish?
>
> S. "HA-1" L.
Hehe. No, I thought wether I should propose SHA or MD5. I thought MD5 would
suffice, as it will be far from the weakest point.
/Kasper
------------------------------
** 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
******************************
