Cryptography-Digest Digest #311, Volume #12 Sat, 29 Jul 00 06:13:00 EDT
Contents:
Re: substring reversal (Boris Kazak)
Re: Elliptic Curves encryption (Greg)
Re: Elliptic Curves encryption (Greg)
Re: Elliptic Curves encryption (Greg)
Re: counter as IV? (Mok-Kong Shen)
Re: substring reversal (Mok-Kong Shen)
Re: substring reversal (Mok-Kong Shen)
Re: What is DES3mCBCMACi64pPKCS5? (Daniel James)
Re: JavaCard vs Multos security (Daniel James)
Re: How secure is the "Square Block Cipher" in Pegwit? (David Crick)
Re: what is the symmetric algorithm for protection of classified info by (David
Crick)
----------------------------------------------------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: substring reversal
Date: Sat, 29 Jul 2000 07:49:13 GMT
[EMAIL PROTECTED] wrote:
>
> How secure is a bitwise substring reversal-based cipher? The plaintext
> is divided into substrings of length k, where k is a number between 2
> and 17 (the next 4 bits of the key), and each substring is reversed,
> but the order of the substrings themselves is kept intact. Example:
>
> k=3
> plaintext= "The dog jumped over the fence."
> ciphertext="ehTod j gpmu deevot r ehnef.ec"
>
> If the length of the plaintext is not divisible by k, white space is
> simply added:
>
> k=7
> plaintext= "The dog jumped over the fence. "
> ciphertext="god ehTdepmuj t revo nef eh .ec"
>
> This substring reversal operation is done a hundred times or so, and to
> decrypt, the same thing is done, except the key is reversed. This is
> not vulnerable to the a simple character frequency attack, because the
> characters themselves are kept intact, only they are shuffled around.
> Are there any attacks that can be used to crack this?
>
> -- Vlad
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
=============================
(My 2-pennies-worth, this can be a little fun.)
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: Greg <[EMAIL PROTECTED]>
Subject: Re: Elliptic Curves encryption
Date: Sat, 29 Jul 2000 07:43:46 GMT
> In my experience with ECC over GF(p) or GF(2^n), it has slower
> verfication performance vs. RSA by an order of magnitude. ECC has
shown
> faster signing performance and appears to scale to larger key lengths
> much better.
What may be worth pointing out is that there are some performance
improvements that have been patented and once those patents run
out or if you do not intend to sale your product, you can use them
to realize a huge improvement in overall performance with ECC.
--
Craig: Well what will you do?
William: I will invade England and defeat the English on their own
ground.
Craig: Invade? That's impossible.
William: Why? Why is that impossible? You're so concerned with
squabbling for the scraps from Longshank's table that
you've missed your God-given right to something better.
There is a difference between us.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Elliptic Curves encryption
Date: Sat, 29 Jul 2000 07:41:09 GMT
> ECC uses fewer resources than RSA, so it's cheaper to implement in
> hardware. The keys are also much smaller for the same strength, so
> it uses less bandwidth. For many commercial applications this is
> important. For many other applications, it isn't important at all.
But at the same time, my crypto library is very small and simple
compared to any RSA implementation, is far easier to grasp and debug
intuitively, and thus leads to a much higher level of confidence that
it was implemented correctly with far less effort in programming.
That level of confidence is proportional to code size and complexity.
--
Craig: Well what will you do?
William: I will invade England and defeat the English on their own
ground.
Craig: Invade? That's impossible.
William: Why? Why is that impossible? You're so concerned with
squabbling for the scraps from Longshank's table that
you've missed your God-given right to something better.
There is a difference between us.
--
Craig: Well what will you do?
William: I will invade England and defeat the English on their own
ground.
Craig: Invade? That's impossible.
William: Why? Why is that impossible? You're so concerned with
squabbling for the scraps from Longshank's table that
you've missed your God-given right to something better.
There is a difference between us.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Elliptic Curves encryption
Date: Sat, 29 Jul 2000 07:36:13 GMT
> So, basically, you are willing to *believe* that one form of
> cryptography -- and only that form -- is capable of strength.
> Interesting. What possible basis can one possibly have for imagining
> that the field is bicameral in this way? Shall we imagine that number
> theory is "better" than field theory, or mappings?
Terry-
Allow me to share a story with you. I personally know this man - this
man of God - who was working at the time - this real man of God - as
a computer administrator. He was working late one Saturday (and he
makes BIG $$$ too) and he got to the point where he needed to logon
using someone's logon and password. [Note this story is absolutely
true and I know the man personally - very well in fact.]
He could not get ahold of the guy. So he prayed and instantly God
revealed to his mind what the password was. He entered it, completed
his work, and left for home early.
You see, Terry, math ain't enough to secure your data. Be certain you
are on the right side. Then, even weak crypto could be adequate with
the same help from the same friend.
Or did you think those stories about the US military and CIA doing
work in the field of spiritual this or that was a hoax? They know.
Unfortunately, they are making alliances with the devil and not God.
--
I cannot possibly believe that after sitting in the most powerful
seat of the world for more than seven years now, with the weight
of responsibity of the most powerful nation on earth upon his
shoulders, that the Honorable William Jefferson Clinton has not
yet come to the full revelation that indeed God exists and cares
deeply for this and any other nation on earth.
A story is told of a governor from one of the states had retired and
decided to go to the Soviet Union to talk with Nikita Kruchev about
the old days, particularly the cuban missile ordeal. He returned
early, frustrated, and upset that he wasted a long trip for not.
When asked what he and Kruchev talked about, he said that Krucheve
would talk of nothing else other than how wonderful Jesus was.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: counter as IV?
Date: Sat, 29 Jul 2000 10:08:02 +0200
"Douglas A. Gwyn" wrote:
> Mok-Kong Shen wrote:
> > ... If the opponent ever gets
> > the key for one block, he can decrypt the whole message.
>
> That's the case for practically any block cipher used in any
> chaining mode.
I have unfortunately some difficulty with the term chaining mode in
the context of your original article. (Do you mean that the algorithm
E uses chaining (not explicitly stated) or that the keys are 'chained'?)
Anyway, using different keys in different blocks could involve cost
in setup time, as others have commented. If one doesn't mind that,
then one can better employ pseudo-random variable keys in my
humble view. (BTW, concerning chaining modes, I am certainly
highly subjective and biased in my opinion but I would personally
prefer employing a nonlinear chaining mode that I recently
proposed.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: substring reversal
Date: Sat, 29 Jul 2000 10:42:12 +0200
Boris Kazak wrote:
[snip]
> 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.
Wouldn't it be sufficient to represent the holes in the first quadrant
as binary numbers?
> 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
I don't understand this. Could you please explain the first three digits
above as example? (The order of punching the holes is immaterial,
isn't it?)
> Finally, the combination of Vigenere polyalphabetic substitution
> with
> a subsequent grille permutation is to be taken VERY seriously...
Multiple encryption with algorithms of fairly different nature
(similarly for employing different operations in one algorithm) is in
principle always a good idea, I believe, whether that be in classical
or in modern cryptography. Some people seem to be of the
opinion though that there should be one universal algorithm for all
purposes.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: substring reversal
Date: Sat, 29 Jul 2000 10:59:04 +0200
Mok-Kong Shen wrote:
> Wouldn't it be sufficient to represent the holes in the first quadrant
> as binary numbers?
Please forget this silly question.
M. K. Shen
------------------------------
From: Daniel James <[EMAIL PROTECTED]>
Subject: Re: What is DES3mCBCMACi64pPKCS5?
Date: Sat, 29 Jul 2000 10:22:43 +0100
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Mark Wooding wrote:
> If I'm stuck with DES3 CBC-MAC then I'd do the MAC first and
> encryption afterwards, with *different* keys, but sharing the same IV.
It's always better to use different keys for encryption and for MACing.
> Err... If you're talking about the IV used to do the initial
> encryption, rather than the MAC computation, then it's probably a bad
> idea to fix the IV unless you're only going to be using the key for a
> single message, or the redundancy of the first plaintext block is low.
> Otherwise, an eavesdropper can identify common prefixes in plaintexts,
> which may be undesirable. There's no particular point in keeping the IV
> for a CBC encryption secret, unless the first plaintext block is *much*
> more sensitive than the rest.
In DESCBC the IV is simply XORed with the first plaintext block as the first
step in the chaining. If you know the IV you can XOR it with any suspected
common plaitext block for the price of a single (64-bit) XOR operation. I
repeat my statement that using a known IV buys you *nothing* with the proviso
that I regard the cost of a 64-bit XOR as being essentially nothing. If
you're going to use an IV you should encrypt it, or agree it with D-H, or
something. Prepending a plaintext IV to a message is pointless.
Except ... if you're using a message format that requires that you use an IV
and prepend it to the message in clear it obviously makes sense to use a
random value rather than something known (like 0).
> I agree that the IV for the MAC doesn't need to be chosen at random,
> which is, I suspect, why Paul decided to fix it at zero.
Standard ANSI X9.9 (ISO whatever) MAC always uses 0 for IV.
> > > I'd like to be able to get an
> > > encrypted and authenticated ciphertext from a plaintext in a single
> > > module operation.
>
> I'm afraid that you can't do this. I'm not sure that it would be of
> particularly great benefit anyway, since you have to do the same number
> of DES encryptions anyway. You'd reduce the amount of data transferred
> between the host and the module by a third, though. Is that really a
> major issue?
Not knowning the module in use (I'm aware of, but not familiar with,
nCipher's kit, so I didn't recognize it from the details in the posting) I
couldn't say what was possible and what not. Comms overhead and data transfer
time are obviously factors (some security modules use a serial connection
which can impose big overheads).
Cheers,
Daniel.
------------------------------
From: Daniel James <[EMAIL PROTECTED]>
Subject: Re: JavaCard vs Multos security
Date: Sat, 29 Jul 2000 10:22:43 +0100
Reply-To: [EMAIL PROTECTED]
In article <8ls68p$hr2$[EMAIL PROTECTED]>, wrote:
> I am somehwat surprised that Multos has so much to offer with only an 8
> bit cpu...the new javacard cpu's are 32 bit risc, and that has
> considerable more power to run all the Java bytecode...
Some MULTOS platforms are now 32-bit as well. I don't know how the different
VMs compare on performance.
MULTOS used to suffer from relatively poor development tools, but there are
some good tools becoming available (even some that use Java, if you must) and
MULTOS is now looking like a better bet than JavaCard from just about all
angles (unless you happen to be VISA, because MULTOS is partly owned by their
competitors at Mastercard).
Cheers,
Daniel.
------------------------------
From: David Crick <[EMAIL PROTECTED]>
Subject: Re: How secure is the "Square Block Cipher" in Pegwit?
Date: Sat, 29 Jul 2000 10:34:00 +0100
The Square home page is at:
http://www.esat.kuleuven.ac.be/~rijmen/square/index.html
Square is based on earlier work by some of the authors, but
most famously has evolved further into the AES finalist
Rijndael:
http://www.esat.kuleuven.ac.be/~rijmen/rijndael/index.html
(AES information is at http://csrc.nist.gov/encryption/aes/)
This cipher has received far more analysis. Square originally
had four rounds, but the authors discovered attacks and
increased this number to eight. Rijndael's number of rounds
varies with keysize - 10 for 128-bit, 12 for 192, and 14 for 256.
It should be noted that attacks for 8 and 9-round Rijndael have
been found that are faster than exhaustive key search, although
we are still talking over 2^200 work here. Eight rounds for Sqaure
therefore may not be adequate.
Both ciphers allow you to increase the number of rounds without
much difficulty.
--
+-------------------------------------------------------------------+
| David Crick [EMAIL PROTECTED] RSA 22D5C7A9 DH BE63D7C7 87C46DE1 |
| Damon Hill Tribute Site: http://www.geocities.com/MotorCity/4236/ |
| M. Brundle Quotes: http://members.tripod.com/~vidcad/martin_b.htm |
+-------------------------------------------------------------------+
------------------------------
From: David Crick <[EMAIL PROTECTED]>
Subject: Re: what is the symmetric algorithm for protection of classified info by
Date: Sat, 29 Jul 2000 10:56:08 +0100
John Savard wrote:
>
> I've bumped into the names of a lot of Type 1 algorithms in my web
> searches for more information about cryptography. However, I would
> tend to assume that someone asking 'what is the algorithm' would not
> be satisfied with the *name* of the algorithm (and is anyways under
> the misinformation that there is only one).
>
> As for Skipjack, a book on INTELINK which seemed to have had as its
> main purpose advocating the benefits of SGML says that SKIPJACK was
> qualified for use on SECRET but not TOP SECRET information, despite
> being primarily aimed at 'sensitive but unclassified' use and
> infliction on the great unwashed in the company of key escrow.
>
> Noting that 2^10 = 1024, the old 40-bit exportable keys had just over
> a trillion possible values. 80-bit SKIPJACK had a trillion trillion
> keys.
>
> Some web sites advertising military encryption products mention that
> they have 120-bit keys, and are suitable for controlling the launch of
> nuclear missiles. I suppose that at least tells us how *strong* the
> algorithms used for classified information must be.
>
> Since the exportability threshold has moved from 40 bits to 64, I
> suppose we might multiply by three again; but that still means that if
> the AES really is as secure as hoped - no attacks better than brute
> force - it would be as good as anything the NSA thinks worth bothering
> with. I suppose that's reasurring news.
Interesting comments appear[1] in an AES Round 2 Comment by the U.S.
DoJ Immigration and Naturalization Service. They recommend Twofish,
but with 256-bit keys only and with a minimum of 20 rounds, with 24
as the recommendation.
Coming from a Government department that uses both Type 1 and Type 3
algorithms, I thought the endorsement of 256-bit keys and a safety
margin of 18 rounds (over the current 6 rounds attacked by the PUBLIC)
was significant.
[1] csrc.nist.gov/encryption/aes/round2/comments/20000515-dbutler.pdf
--
+-------------------------------------------------------------------+
| David Crick [EMAIL PROTECTED] RSA 22D5C7A9 DH BE63D7C7 87C46DE1 |
| Damon Hill Tribute Site: http://www.geocities.com/MotorCity/4236/ |
| M. Brundle Quotes: http://members.tripod.com/~vidcad/martin_b.htm |
+-------------------------------------------------------------------+
------------------------------
** 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
******************************
