Cryptography-Digest Digest #930, Volume #12 Sun, 15 Oct 00 07:13:01 EDT
Contents:
Re: Rijndael implementations (Dennis Ritchie)
Re: Optimisation of SHA-256 (Daniel =?iso-8859-1?Q?L=E9onard?=)
Re: Why trust root CAs ? (Vernon Schryver)
Re: Optimisation of SHA-256 (Stephan Eisvogel)
Re: DES chip vendor list (Marc Heusser)
Re: SHA-256 implementation in pure C (free) (lcs Mixmaster Remailer)
Re: Rijndael implementations (Richard Heathfield)
Re: Rijndael implementations (John Savard)
Re: block-cipher silly question? (John Savard)
Re: Rijndael implementations (John Savard)
Re: Using square roots for a secret code? (John Savard)
Re: Is it trivial for NSA to crack these ciphers? ("Douglas A. Gwyn")
Re: block-cipher silly question? ("Douglas A. Gwyn")
Re: Dense feedback polynomials for LFSR (Tim Tyler)
Re: Dense feedback polynomials for LFSR (Tim Tyler)
Re: Rijndael implementations ("Douglas A. Gwyn")
byte != octet [was: Re: Rijndael implementations ] (Rob Warnock)
Re: Rijndael implementations ("Douglas A. Gwyn")
Re: On block encryption processing with intermediate permutations (Mok-Kong Shen)
----------------------------------------------------------------------------
From: Dennis Ritchie <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Date: Sun, 15 Oct 2000 03:37:21 +0000
"Douglas A. Gwyn" wrote (I snip mercilessly):
> But that has little to do with the meaning of "byte", which is a
> contiguous set of bits within a machine word. It happens that to
> encode a limited character set such as ASCII on a machine with
> wide words (e.g. 36 bits) it is more economical to pack the
> characters into bytes than just one per word. That is how "byte"
> first became associated with storage used for character
> representations, but they weren't and aren't synonymous....
OK, sort of. The term seems to have originated at IBM within
the Stretch project. E.g. in "Planning a Computer System"
(McGraw-Hill, 1962) a compilation edited by Buchholz from earlier
IBM documents, "byte" is identified as a term in the
machine data hierarchy corresponding to character in the natural
data hierarchy. (Natural: bit, character, field, record, file;
Machine: bit byte, word, block, reel of tape...etc.) One of the
chapters (by Blaauw, Brooks, Buchholz) is explicit that "byte denotes
a group of bits used to encode a character, or the number of
bits transmitted in parallel to and from input-output units (p. 42).
> The way that "byte" got associated with 8-bit storage was that
> the common ASCII character code readily fit within 8 bits (which
> as a power of 2 became quite common for technical reasons having
> to do with binary addressing), and the kinds of computer that the
> masses of new computer users encountered (Apple II, IBM PC, etc.)
> originally had an ASCIIcentric, power-of-two orientation, with
> 8-bit byte addressability ...
Well, no. Stretch did end up making a similarly explicit choice
to use 8-bit bytes to represent its character set and to carry parts
of the I/O path, while trying to keep the term general or generalizable.
This choice was one of the things that influenced the design of S/360
(whence the "byte" nomenclature became widespread). On
the other hand, the character-set mappings to bytes for Stretch
and for S/360 differed wildly from each other, and both are
distinctly non-ASCII.
True enough that by the 1970s, for new general-purpose
architectures, the 8-bit byte, both for many of the data paths and
for character representation, (usually in ASCII or an extension)
had become enshrined.
Dennis
------------------------------
From: Daniel =?iso-8859-1?Q?L=E9onard?= <[EMAIL PROTECTED]>
Subject: Re: Optimisation of SHA-256
Date: Sat, 14 Oct 2000 23:39:42 -0400
Daniel L�onard wrote:
>
> [some discussion about expanding SHA-256 loop]
>
well, I still did not find how to correctly unroll the main loop, but I
found something "better":
If I keep the loops, it goes faster (long live compiler technology ? :).
If the main loop is kept, it goes faster than if I unroll it.
Also, if the loop to build the W vector is kept (I unrolled it too), my
implementation is faster still.
=================
Daniel L�onard (aka fork)
"The nuclear warhead is one of the Humans' most efficient weapons. They
first tested it on themselves, obliterating several entire cities. The
intervening centuries since the weapon's first use had not dimmed its
effectiveness, as the Black Star proved when it blew apart. It was, from
all accounts, a most impressive display and took - by the standart of
such thing - quite some time as one section after another after another
of the ship erupted."
- Emperor Londo Mollari, Babylon 5 : In the Beginning
------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Subject: Re: Why trust root CAs ?
Date: 14 Oct 2000 22:54:14 -0600
In article <8s6k4o$8bo0j$[EMAIL PROTECTED]>,
Rob Warnock <[EMAIL PROTECTED]> wrote:
>| it is a hassle to transfer
>| your bank's public key from a paper newspaper into your browser compared
>| to letting your browser ask a CA...
>Actually, not any more. There are lots of cheap hand-held bar-code
>scanner/pens these days, the latest hyped use being to scan in URLs from
>magazines so you don't have to type them!! Should be rather easy to print
>the bank's public key in a paper newspaper in machine-readable form...
That's a good point, but it works only for URL's you find in magazines
and newspapers. I find most of the vendors I deal with on the web. About
the only online vendors whose URL's I find in the real world are local,
and I generally want to visit them in the real world and so could take my
smart card or bar-code-reader-with-NVRAM to a teller when first I open an
account.
Another problem is the shear number of domain names. A magazine that
publishes .com 30,000,000 URL's and public keys would probably not able
to use a format that has anything to do with bar code readers as that
notion is currently understood.
You might instead publish CDROM's containing URLs and public keys, but
even with DVD densities and the embarrassing compressibility of domain
names might be more than 1 or 2 disks when the whole world finally gets
in on the act. Worse, the commercial pressures that gave us D&B and
Verisign/Thawte/NetworkSolutions work almost as well in physical media as
on the net.
Vernon Schryver [EMAIL PROTECTED]
------------------------------
From: Stephan Eisvogel <[EMAIL PROTECTED]>
Subject: Re: Optimisation of SHA-256
Date: Sun, 15 Oct 2000 07:34:15 +0200
Daniel L�onard wrote:
> If I keep the loops, it goes faster (long live compiler technology ? :).
> If the main loop is kept, it goes faster than if I unroll it.
> Also, if the loop to build the W vector is kept (I unrolled it too), my
> implementation is faster still.
What CPU do you have? Pentium II class? What you see is the effect of
L1/L2 cache code/data trashing when you unroll your loops. If you keep
the loop, the code will stay in L1 cache and execute much faster than
code that does the same, does away with the conditional branches but
needs to be reloaded from L2 cache or even RAM because it is too large
to be kept in L1 completely. Loop unrolling was nice for 8086...
The effects of conditional branches are even more lessened by the branch
history table (BHT) inside your CPU, which in essence remembers if the
last branches were taken/not taken and helps the branch prediction unit
to keep execution pipelines busy with the correct code. If it didn't
keep track, speculative execution would more often go 'the wrong way'
and make lots of expensive flushes necessary. Today, in many cases
small code equals fast code, well at least as long as you don't f.up
your instruction ordering, cause AGU stalls, etc.
I can recommend the Intel C++ 4.5 compiler (evaluation version is
available from their developer site) and also MSVC6 to get these kinds
of optimizations more easily. MSVC6 produces cleaner assembler code
from a human point of view, but Intel's spaghetti-thing really makes
a Pentium II CPU sweat. I use Intel's.
--
hawo bofh
------------------------------
From: Marc Heusser <[EMAIL PROTECTED]>
Subject: Re: DES chip vendor list
Date: Sun, 15 Oct 2000 09:13:08 +0200
In article <39e725bf$0$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Mark
Currie) wrote:
> Hi,
>
> I am looking for a reasonably up-to-date list of DES chip vendors. Anyone
> have
> such a list or know where I might find one ?
I'm not in the business anymore but there certainly still is a yearly
reference book of all the integrated circuits sorted according to
function - it should be easy to find it there.
sorry, cannot recall the name right now - you'd find it in any
electronics department of a university.
Marc
--
Marc Heusser
remove the obvious CHEERS and COM... from the reply address to reply via e-mail
------------------------------
Date: 15 Oct 2000 07:20:07 -0000
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Re: SHA-256 implementation in pure C (free)
> At http://www.geocities.com/tomstdenis/files/sha256.c you can find a
> free copy of the SHA-256 hash function in C. It's rather easy to drop
> in and use. I hope SHA-256 is in fact secure though... heheheh
Okay, hotshot, now let's see you do SHA-512. No fair peeking at
http://www.deja.com/[ST_rn=ps]/getdoc.xp?AN=681517214.
------------------------------
Date: Sun, 15 Oct 2000 08:44:21 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Roger Schlafly wrote:
>
> Richard Heathfield wrote:
> > In Knuth's TAOCP I (the most obvious example of "books about computers
> > from the days..." and the only such book I had immediately to hand), the
> > body of the text disagrees with you, but the footnote contradicts it,
> > saying that "byte" was "standardized" to 8 bits in approximately 1975.
> > So I find myself in the uncomfortable position of disagreeing with
> > Knuth's footnote (whilst agreeing with his more flexible definition in
> > the body of the text). You would appear to take the opposite (but
> > equally uncomfortable) position.
>
> So if you are referring to a "byte" in the context of a
> pre-1975 computer, then it might be something other than 8 bits.
> But to about 99.99% of the world out there, byte is 8 bits.
Yes, I think your 99.99% figure is closer to the mark than Tom St
Denis's 99.9999% figure, given earlier this week, but of course your
finger is just as much in the air as Tom's.
My current client is writing code which must work on machines with 8
bits per byte, sizeof(long)=4. A fairly typical system, you might think.
But the same code must also work on machines with 32 bits per byte:
sizeof(long) = sizeof(int) = sizeof(short) = sizeof(char) = 1.
Pretending that a byte has 8 bits won't help us. We have to confront the
reality of 32-bit bytes, and ignorance doesn't count as a defence in the
real world.
99.99% of people may think that there are 8 bits in a byte, but then at
least 99.99% of people think this is the first year of the third
Millennium; going with the majority is always comfortable (especially in
ostensibly democratic countries), but all too often it's just plain
wrong.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
66 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (31
to go)
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Rijndael implementations
Date: Sun, 15 Oct 2000 09:23:05 GMT
On Sat, 14 Oct 2000 21:45:05 +0100, Richard Heathfield
<[EMAIL PROTECTED]> wrote, in part:
>In Knuth's TAOCP I (the most obvious example of "books about computers
>from the days..." and the only such book I had immediately to hand), the
>body of the text disagrees with you,
Yes, in the description of the MIX machine, a "byte" is defined as
something with from 64 to 100 values, whose size depends on the base
of the machine at hand. (Thus, a MIX simulator for checking homework
problems once had a byte with 81 values.)
However, since that is virtually the only place where a byte is given
such a definition that most programmers would encounter, and since it
is a definition that flatly contradicts the 8-bit byte instead of
including it as a possibility, I would think it was largely ignored.
But I have seen it claimed that DEC used the term "byte" to refer to
the variable-size characters of the PDP-10.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: block-cipher silly question?
Date: Sun, 15 Oct 2000 09:37:45 GMT
On 14 Oct 2000 22:36:21 GMT, [EMAIL PROTECTED] (David Wagner)
wrote, in part:
>In this case, I cannot see how a cipher with a 8-bit block can be secure.
>(Perhaps this is just my lack of imagination; I'd be happy to be corrected!)
I lack imagination as well, but of course one case where 'anything' is
secure is where the text to be enciphered is just a series of random
bits.
So, if one uses a random session key - enciphered using a more normal
block cipher with a key derived from a user password - to generate a
substitution on bytes, one might indeed be able to get away with using
simple substitution for EKE. Not that I'd recommend anyone trying! But
it almost seems as though it couldn't be attacked except through brute
force, just as if a stronger cipher had been used.
Using "perfect" compression on text, if it existed, would also create
unresolvable ambiguity, and cheating by using an additional layer of
encryption - i.e., random Huffman codes assigned in the compression
phase - would work to, as Mr. Scott has noted.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Rijndael implementations
Date: Sun, 15 Oct 2000 09:31:33 GMT
On Sun, 15 Oct 2000 08:44:21 +0100, Richard Heathfield
<[EMAIL PROTECTED]> wrote, in part:
>My current client is writing code which must work on machines with 8
>bits per byte, sizeof(long)=4. A fairly typical system, you might think.
>But the same code must also work on machines with 32 bits per byte:
>sizeof(long) = sizeof(int) = sizeof(short) = sizeof(char) = 1.
You mean on machines with characters that are four bytes long. (Byte
is _not_ a C keyword.)
However, the problem is with your compiler and operating system in
this case, because doubtless the machine still has AND and SHIFT
instructions. (It is only recently that the profligate use of memory
in search of speed you note has become possible to consider; many
machines used six or eight bit characters despite having no way to
address units of memory smaller than a word.)
Using the term byte to mean "eight bits" in no way implies that all
machines have a character cell that is one byte in size. That many
computers have a six bit character, or that Java uses a sixteen bit
character, is well known. A character cell may vary in size from one
architecture to another, while a byte is now a unit of information.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math
Subject: Re: Using square roots for a secret code?
Date: Sun, 15 Oct 2000 09:42:03 GMT
On Sun, 15 Oct 2000 01:04:59 GMT, [EMAIL PROTECTED] wrote, in
part:
>Can one "continued-fraction" recover the code key for the scheme in this
>rhyme?
Since you are talking about the square roots of fairly large numbers,
there certainly are a multiplicity of possible keys. By excluding some
digits, you have indeed blocked simple mathematical attacks.
But the problem with extracting the digits of a square root is that
you need to manipulate numbers as large as your whole message. So the
scheme is considered slow and clumsy, compared to more conventional
methods.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Is it trivial for NSA to crack these ciphers?
Date: Sun, 15 Oct 2000 09:51:30 GMT
"Stephen M. Gardner" wrote:
> John Savard wrote:
> > Ah, but the number of mathematicians working in the open on
> > cryptography is far smaller than the number working in the NSA.
> How do we know that? How many scientists are there at NSA
> engaged in cryptanalysis research?
NSA is certainly employs more mathematicians than nearly any
other organization in the world; that's well known. Their
tasking breakdown is of course classified. but given that it
is primarily a cryptologic organization it is safe to assume
that a large fraction are working on cryptology.
> > Also,
> > the NSA has access to the open literature, like anyone else.
> Yes, but they do not have access to the open give and take in
> international forums. Much of the real creative work in science
> takes place during conversations with colleagues from around the
> world.
NSA researchers do in fact participate in the open community.
Of course, they cannot disclose breakthroughs that could have
significant consequences for the national security mission.
One thing you are completely overlooking is that there has
been a continued concentration of cryptologic effort in NSA
and allied organizations for many decades, producing a
"corporate memory" and momentum far in excess of anything
found in a university department.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: block-cipher silly question?
Date: Sun, 15 Oct 2000 10:00:30 GMT
David Wagner wrote:
> In this case, I cannot see how a cipher with a 8-bit block can be
> secure.
Easy -- for each block step the key-scheduling algorithm once.
That's in effect a polyalphabetic with near-random key, and any
chance of cracking it is going to lie in defects in the key
scheduling algorithm.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Reply-To: [EMAIL PROTECTED]
Date: Sun, 15 Oct 2000 09:43:50 GMT
Joaquim Southby <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]> Tim Tyler, [EMAIL PROTECTED] writes:
:>It may be true that making the polynomial part of the key may have
:>positive security implications - but you need to be doing something with
:>the LFSR that makes its output inaccessible to an attacker, as well,
:>for the security to get off rock bottom.
:
: If I can make the output inaccessible to the attacker, why do I need to
: encipher at all? Why not just make the plaintext inaccessible instead?
As an example of a technique that makes the LFSR output inaccessible to an
attacker, consider a LFSR-based self-shrinking generator.
Why can't you do this trick with the plaintext? Because it mangles it
irretrievably, so the recipient can't recover the message ;-(
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Free gift.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Reply-To: [EMAIL PROTECTED]
Date: Sun, 15 Oct 2000 09:49:36 GMT
Joaquim Southby <[EMAIL PROTECTED]> wrote:
: OTOH, there is nothing that says you have to use a primitive polynomial.
It helps - if you want to be able to claim you're not using a short period.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Florist: Petal pusher.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Date: Sun, 15 Oct 2000 10:21:42 GMT
Dennis Ritchie wrote:
> OK, sort of. The term seems to have originated at IBM within
> the Stretch project. ... "byte denotes
> a group of bits used to encode a character, or the number of
> bits transmitted in parallel to and from input-output units ...
Absent any information to the contrary, I'll grant that to the
people on the Stretch project a "byte" was always associated
with a character. However, in approximately the same time frame
(within a few years at most), other computer architects such as
the ones at CDC were not necessarily associating characters with
bytes, and many CDC machines had what they called "byte"
operations that would operate on a bit field that was specified
by the programmer. The most obvious use of this would indeed be
to pack characters into machine words, but they were used for
many non-character purposes as well.
I think the word "byte" itself arose from making a long I
instead of short I in "bit", maybe also punning about a
chomp ("bite") taken out of a machine word.
> > The way that "byte" got associated with 8-bit storage was that
> > the common ASCII character code readily fit within 8 bits (which
> > as a power of 2 became quite common for technical reasons having
> > to do with binary addressing), and the kinds of computer that the
> > masses of new computer users encountered (Apple II, IBM PC, etc.)
> > originally had an ASCIIcentric, power-of-two orientation, with
> > 8-bit byte addressability ...
> Well, no. Stretch did end up making a similarly explicit choice
> to use 8-bit bytes to represent its character set and to carry parts
> of the I/O path, while trying to keep the term general or
> generalizable.
I was specifically referring to the use of "byte" with modern disk
and RAM devices, which cannot reasonably be blamed on Stretch.
> This choice was one of the things that influenced the design of
> S/360 (whence the "byte" nomenclature became widespread).
I agree that with the advent of System/360 "byte" was used
primarily to denote the smallest conveniently accessed units
of a standardized fixed size, 8 bits as it happened. (Not
surprisingly in a Western culture, where 8 bits is the
smallest power of 2 that can hold the entire alphabet.)
> True enough that by the 1970s, for new general-purpose
> architectures, the 8-bit byte, both for many of the data paths and
> for character representation, (usually in ASCII or an extension)
> had become enshrined.
Yes, but the point is that a standardized size doesn't mean
that other sizes are impossible. Egg cartons usually hold
12 eggs, but a 16-egg carton still qualifies as an egg carton.
In fact I've seen a lot of confusion among newcomers over the
use of the term "byte" in the C standard to designate the
implementation's choice for the smallest unit used to compose
data objects. It is not necessarily 8 bits, although that is
by far the most common choice. In these days of cheap memory,
it is not entirely unreasonable to have 32-bit bytes.
------------------------------
From: [EMAIL PROTECTED] (Rob Warnock)
Subject: byte != octet [was: Re: Rijndael implementations ]
Date: 15 Oct 2000 10:23:46 GMT
John Savard <[EMAIL PROTECTED]> wrote:
+---------------
| But I have seen it claimed that DEC used the term "byte" to refer to
| the variable-size characters of the PDP-10.
+---------------
Indeed, and the instructions which manipulated bytes & byte pointers were:
LDB LoaD Byte
ILDB Increment [byte pointer and then] LoaD Byte
DPB DePosit Byte
IDPB Increment [byte pointer and then] DePosit Byte
IBP Increment Byte Pointer
ADJBP ADJust Byte Pointer
These mnemonics and meanings are still used today in the ANSI Common Lisp
standard, which includes the LDB & DPB operators:
<URL:http://www.xanalys.com/software_tools/reference/
HyperSpec/Body/acc_ldb.html>
<URL:http://www.xanalys.com/software_tools/reference/
HyperSpec/Body/fun_dpb.html>
However, PDP-10 byte pointers were too machine-dependent for inclusion
in ANSI Common Lisp, so it was replaced with a machine-independent notion
called a "byte specifier":
<URL:http://www.xanalys.com/software_tools/reference/
HyperSpec/Body/fun_bytecm_by_yte-position.html>
(byte size position) => bytespec
(byte-size bytespec) => size
(byte-position bytespec) => position
BYTE returns a byte specifier that indicates a byte of width size
and whose bits have weights 2^position + size - 1 through 2^position,
and whose representation is implementation-dependent.
BYTE-SIZE returns the number of bits specified by bytespec.
BYTE-POSITION returns the position specified by bytespec.
Examples:
(setq b (byte 100 200)) => #<BYTE-SPECIFIER size 100 position 200>
(byte-size b) => 100
(byte-position b) => 200
Bytes other than 8 bits *are* still used...
-Rob
=====
Rob Warnock, 31-2-510 [EMAIL PROTECTED]
Network Engineering http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. PP-ASEL-IA
Mountain View, CA 94043
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Date: Sun, 15 Oct 2000 10:30:35 GMT
John Savard wrote:
> Richard Heathfield wrote, in part:
> >But the same code must also work on machines with 32 bits per byte:
> >sizeof(long) = sizeof(int) = sizeof(short) = sizeof(char) = 1.
> You mean on machines with characters that are four bytes long. (Byte
> is _not_ a C keyword.)
"Byte" is not a keyword in the grammar, but it *is* a technical
term in the language specification (standard). He meant what he
said, 32-bit bytes.
> Using the term byte to mean "eight bits" in no way implies that all
> machines have a character cell that is one byte in size.
In C standardese, a byte is the smallest unit of data-object
addressability; e.g. it is the unit reported by sizeof. It is
a requirement imposed by the C standard on any conforming
implementation that an object of type "char" occupies exactly one
byte. Type "char" is an integer type, not necessarily used for
character representation although it can be used as such for at
least the limited characters in the basic execution character set
listed in the C standard. It is consistent both with the C
standard and with the traditional meaning of "byte" for a C
implementation to use 32-bit bytes.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encryption processing with intermediate permutations
Date: Sun, 15 Oct 2000 12:43:27 +0200
Addendum:
The following is an explanation of the scheme in a more
formal way.
Let's assume that the block cipher is of the general
Feistel type, i.e. using one half of the block to process
the other half and vice versa and that each block has two
words, denoted e.g. by A0 and B0, and that the message
consists of two blocks only. The encryption processing
done by the i-th cycle (two rounds) is denoted by the
functions R and S and that of the (i+1)-th cycle by T
and U, these functions being dependent upon the round
keys.
Normal scheme:
Input of i-th cylce: A0 B0 C0 D0
Output of i-th cycle and input of (i+1)-th cycle:
A1=R(A0,B0) B1=S(A0,B0) C1=R(C0,D0) D1=S(C0,D0)
Output of (i+1)-th cycle:
A2=T(A1,B1) B2=U(A1,B1) C2=T(C1,D1) D2=U(C1,D1)
We have
A2=T(R(A0,B0),S(A0,B0)) B2=U(R(A0,B0),S(A0,B0))
C2=T(R(C0,D0),S(C0,D0)) D2=U(R(C0,D0),S(C0,D0))
Proposed scheme:
Input of i-th cylce: A0 B0 C0 D0
Output of i-th cycle:
A1=R(A0,B0) B1=S(A0,B0) C1=R(C0,D0) D1=S(C0,D0)
Permutation (assumed, in general different for different
messages), resulting in input to (i+1)-th cycle:
A1'=B1 B1'=C1 C1'=A1 D1'=D1
Output of (i+1)-th cycle::
A2=T(A1',B1') B2=U(A1',B1') C2=T(C1',D1') D2=U(C1',D1')
We have
A2=T(S(A0,B0),R(C0,D0)) B2=U(S(A0,B0),R(C0,D0))
C2=T(R(A0,B0),S(C0,D0)) D2=U(R(A0,B0),S(C0,D0))
Note that (1) In the normal scheme, the A2 etc. are each
a function of two variables (words of input to i-th cylce),
while in the proposed scheme the same are each a function
of four variables. (2) Since the permutation is unknown,
the opponent does not know the exact 'structure' of the
functions for A2 etc. It could be, e.g. that what is at
the position of A2 (the first word of four above) is
in fact the function given by D2 above instead. In other
words, he has a problem of 'identification'.
We also note that the PRNG is not reset during the session
and one can maintain a record of the current values of the
seed of the PRNG at the end of each (legitimate) message
so that it is very easy to check whether there has been
'additional' processing with the scheme introduced by the
opponent using chosen plaintext or chosen ciphertext.
In the case of chosen ciphertext, the receiver will not
be able to legibly read ensuing legitimate messages in the
session due to loss of synchronization of the PRNG.
It may also be noted that we are basically treating each
cycle of the given block cipher (applying successively
to all blocks of a message) as an individual 'cipher'
(considering the entire message as a single 'block') and
thus the succession of cycles may be considered sort of
multiple encryption with these 'ciphers'. The insertion
of a permutation between two such ciphers works then in
my view in the sense of a scheme denoted by RST in one
of Shannon's paper (here insertion of the permutation S
between two ciphers R and T).
M. K. Shen
------------------------------
** 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
******************************
