Cryptography-Digest Digest #956, Volume #11 Tue, 6 Jun 00 13:13:00 EDT
Contents:
Re: Could RC4 used to generate S-Boxes? (Mark Wooding)
Re: Towards an attack on Storin (tomstd)
Re: Could RC4 used to generate S-Boxes? (Simon Johnson)
Re: Comfort csybrandy ! (Was: Attack on SC6a (sci.crypt cipher))
([EMAIL PROTECTED])
Re: Multiplication in Storin (tomstd)
Re: Could RC4 used to generate S-Boxes? (tomstd)
Re: Solution for file encryption / expiration? (Frank M. Siegert)
Re: Question about recommended keysizes (768 bit RSA) ("Tony T. Warnock")
Re: do you need unrestricted FREE S/MIME certificate ? than read message ...
(Dagnabbit!)
Re: Towards an attack on Storin (Mark Wooding)
Re: Solution for file encryption / expiration? (Mark Wooding)
Re: Some dumb questions (Volker Hetzer)
Re: Some citations (Paul Koning)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Could RC4 used to generate S-Boxes?
Date: 6 Jun 2000 15:46:09 GMT
T.Williams <[EMAIL PROTECTED]> wrote:
> Runu Knips wrote:
>
> > Hmm. For me, a s-box is an operation of the form:
> >
> > f(x) -> y
> >
> > where f is bijective and should have some other good properties
> > already discussed in this thread.
No. Bijectivity isn't actually a necessary feature; it helps security,
though. For example, Blowfish's S-boxes aren't necessarily bijective --
these are the `weak keys' that Vaudenay found. DES's S-boxes aren't
bijective either: in particular, they're source-heavy. Non-bijectivity
is a bad idea in general: it means that you can get nonzero input
differences sent to zero output differences, giving you an easy 2-round
iterative characteristic.
> > The main point about it is, that it is an operation or function,
> > not a dynamically changing mapping, i.e. for the same x you
> > always get the same y.
This is true.
An `S-box' is a function, possibly parameterized by the key, and usually
implemented as a look-up table for speed (or because algebraic
expressions of the function are too horrible to contemplate).
> Ah, but this is not always the case. Remember Merkle's Khufu and
> its ever changing s-boxes?
Khufu doesn't have `ever changing s-boxes'. It has a key-dependent
S-box for each 8 rounds. You use the same S-boxes in the same sequence
for each block.
-- [mdw]
------------------------------
Subject: Re: Towards an attack on Storin
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 06 Jun 2000 08:58:07 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>> I might possibly have a valid idea for starting a differential
>> attack (this attack may not be valid, but I think it is):
>
>Could you please be more specific about what things are
differences,
>which pairs you're talking about and so on?
Sure no prob, keep in mind my attack is not particularly
efficient and won't even break 3 rounds easily...
What you do is look for an input tuples (a, b, c, d) (where the
lsb of each word is the same in the tuple) where after one round
the lsb is equal to the 12th bit. This will happen with a
probability of 2^-4 (i.e if you guess the key bits for the lsbs
right).
Guessing the key bits right for one round will be
distuingishable if the lsb equals the 12th bit because of the
x' = x xor (x >> 12)
Where after even multiplications the lsb of "x" is zero.
Anyways, there are 16 different possible tuples (one bit per
word).
I don't think this can't be used to attack more then one round
efficiently though...
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Could RC4 used to generate S-Boxes?
Date: Tue, 06 Jun 2000 15:50:50 GMT
In article <8hiifo$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Guy Macon) wrote:
> Simon Johnson wrote:
> >
> >
> >Strictly by definition, RC4 does have an s-box; One value get
> >substituted for another. Wether it slowly evolves makes no difference
> >to its name; it is still an s-box. However, like one of you stated,
it
> >is not an S-Box in the fiestel sense of the word.
> >
>
> Could you post the definition of "S-box" and "S-Box in the fiestel
> sense of the word"? I am confused.
>
>
Sure, as i understand it.... An S-Box stands for a substiution box; a
value is entered and is subsituted for another.
An s-box's size is defined in the the (number of bits inputed)x(number
of bits outputed)
e.g: an 8x8 S-box takes 8 bits and subsitutes it for another 8-bits.
e.g.2: an 8x32 S-box takes an 8-bit value and subsitutes it for an
32-bit value.
Now, this is my simpler difinition, which altough correct, is
non-standard.
The reason for this is that in a block cipher, the s-box are non time
varient;Once encryption starts they don't change (note some ciphers have
key dependent s-boxes; but they are fixed once set.)
However, in RC4 the S-box slowly changes and is therefore time-varient,
plus it is used in a very different manner. As Tom quite rightly pointed
out, the 's-box' in RC4 is the internal state of the stream cipher.
In block ciphers the s-boxes are used to make the cipher obey many a set
of desirable criteria. It makes the cipher much harder to analyse. I
won't list them here, because it would be an incomplete list.
Basically the lesson here is not to use my definition :)
=======
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Comfort csybrandy ! (Was: Attack on SC6a (sci.crypt cipher))
Date: Tue, 06 Jun 2000 15:49:09 GMT
Well, I tried. I guess I should have analyzed it more, however I
simply do not have the time to learn. Since my algorithm has been
declared as crap in it's current version, does anyone have suggestions
on how to fix it? Also, what aspects of it do people like?
csybrandy
In article <[EMAIL PROTECTED]>,
Runu Knips <[EMAIL PROTECTED]> wrote:
> tomstd wrote:
> > [...]
>
> Oooops. Before I've even recognized there is a new cipher there is
> already an attack !
>
> Comfort to the author of SC6a ! It really hurts to get one's cipher
> broken so fast.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: Multiplication in Storin
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 06 Jun 2000 09:00:50 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>
>> However multiplication has good properties which
are 'directed' which
>> is a bad thing. For example the lsb is linear (AND) and the
next bit
>> is a tad less linear...
>
>Indeed. If the multiplication were perfect, I wouldn't need
eight
>rounds, or the other bells and whistles like the linear
transformation.
>
>> Not to mention that interpolation attacks could go right thru
the
>> matrix (maybe not the round key xor).
>
>I thought interpolation attacks were about interpolating
relationships
>in GF(2^n), not over the integers.
>
>Integer addition (with carries) and XOR interact in a slightly
nonlinear
>way (enough to protect RC5 from an unhappy fate in a mod 3
attack, for
>example). Integer multiplication is basically lots of
additions done at
>different bit offsets. It makes the effect much more
pronounced near
>the top end of the result, and the linear transformation should
(in
>theory) provide the low end with the same benefits.
The only good bits from a multiplication are the ones around the
top bit of the word, but remember a n-bit multiplication
produces a 2n bit result. So if for example your input is xxxx
* xxxx = XXXXXXXX you actually want the 'x' bits of the result
noted as XXxxxxXX. Or more percisely XXxyyxXX the 'y' bits
since they depend on more bits then anything else.
On the x86 you can do a full 32x32=64 multiply and SHRD your
answer :)
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: Could RC4 used to generate S-Boxes?
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 06 Jun 2000 09:08:37 -0700
In article <8hj6kh$59e$[EMAIL PROTECTED]>, Simon Johnson
<[EMAIL PROTECTED]> wrote:
>In article <8hiifo$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Guy Macon) wrote:
>> Simon Johnson wrote:
>> >
>> >
>> >Strictly by definition, RC4 does have an s-box; One value get
>> >substituted for another. Wether it slowly evolves makes no
difference
>> >to its name; it is still an s-box. However, like one of you
stated,
>it
>> >is not an S-Box in the fiestel sense of the word.
>> >
>>
>> Could you post the definition of "S-box" and "S-Box in the
fiestel
>> sense of the word"? I am confused.
>>
>>
>
>Sure, as i understand it.... An S-Box stands for a substiution
box; a
>value is entered and is subsituted for another.
>An s-box's size is defined in the the (number of bits inputed)x
(number
>of bits outputed)
>
>e.g: an 8x8 S-box takes 8 bits and subsitutes it for another 8-
bits.
>e.g.2: an 8x32 S-box takes an 8-bit value and subsitutes it for
an
>32-bit value.
Another key way of looking at sboxes is pretend your 8x8 sbox is
really eight 8x1 sboxes That are lined up... i.e
S1 : 0 1 1 0 0 1 1 ...
S2 : 1 1 0 0 0 1 1 ...
.. and so on.
And that you take your input to specify a column and you read
the bits out. This concept threw me off at first but it's
essential for analyzing sboxes.
Similarly for 8x32 sboxes you have 32 8x1 sboxes lined up...
>Now, this is my simpler difinition, which altough correct, is
>non-standard.
Essentially you are right, an s-box is just a subtitution table
that takes an 'n' bit input and produces an 'm' bit output.
It's fixed during encryption for block ciphers (otherwise it
would be a stream cipher).
>The reason for this is that in a block cipher, the s-box are
non time
>varient;Once encryption starts they don't change (note some
ciphers have
>key dependent s-boxes; but they are fixed once set.)
>
>However, in RC4 the S-box slowly changes and is therefore time-
varient,
>plus it is used in a very different manner. As Tom quite
rightly pointed
>out, the 's-box' in RC4 is the internal state of the stream
cipher.
>
>In block ciphers the s-boxes are used to make the cipher obey
many a set
>of desirable criteria. It makes the cipher much harder to
analyse. I
>won't list them here, because it would be an incomplete list.
>
I disagree, following the crieria makes them easy to analyze,
which is a desirable property. You must distuingsh between
broken and analysed. For example the sboxes in CAST form
perfectly non-linear sboxes (i.e max bias is 2^-sqrt(32)) with
low xor-pairs (i think DPmax is 2^-31). But CAST is hardly
broken.
>Basically the lesson here is not to use my definition :)
>
Nah just grow on your definition.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (Frank M. Siegert)
Subject: Re: Solution for file encryption / expiration?
Date: Tue, 06 Jun 2000 16:16:19 GMT
On 6 Jun 2000 15:01:38 GMT, [EMAIL PROTECTED] (Mark Wooding) wrote:
>> (Which cannot be displayed after a certain amount of time, and I guess
>> encrypted to prevent copying too)
>
>Encryption doesn't prevent copying. You just copy the ciphertext.
It will stop people from 1) altering the PDF contents, 2) print the
contents and 3) drag&drop text elements
2) is improtant because when printing to a PS file you can easily
strip any encryption by redistilling it again.
This PDF 'native' encryption uses RC4 with a 40 bit key. This may stop
Joe User but will most likely crumble under a determined attack.
Another problem: A PDF/eBook/Whatever reader will need the decrypted
contents to display it on screen - so somewhere in the machine the
file is completely decrypted as soon as you see it.
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy.anon-server,alt.security.pgp
Subject: Re: Question about recommended keysizes (768 bit RSA)
Date: Tue, 06 Jun 2000 10:15:09 -0600
Reply-To: [EMAIL PROTECTED]
Actually both the CDC7600 and Cray-1 Serial 1 were out in 1977.
Bob Silverman wrote:
> In article <[EMAIL PROTECTED]>,
> Jerry Coffin <[EMAIL PROTECTED]> wrote:
> > In article <8hh40c$ktj$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
> >
> > You've got two possibilities: you can compare high-end machines then
> > to high-end machines now, or you can compare low-end machines then to
> > low-end machines now. You can NOT, however, get anything approaching
> > meaningful results by comparing a high-end machine then to a low-end
> > machine now (or vice versa).
>
> The VAX was NOT a "high-end" machine in 1977. It simply happened to
> be the first 32 bit machine built by DEC.
>
> You want a "high-end" machine in 1977? Try the CDC-6600.
>
> --
> Bob Silverman
> "You can lead a horse's ass to knowledge, but you can't make him think"
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
Date: 6 Jun 2000 16:24:14 -0000
From: [EMAIL PROTECTED] (Dagnabbit!)
Subject: Re: do you need unrestricted FREE S/MIME certificate ? than read message ...
Crossposted-To:
alt.privacy,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
On Mon, 05 Jun 2000 11:34:18 -0400 jungle <[EMAIL PROTECTED]> wrote:
>do you need unrestricted FREE S/MIME certificate ? than read message ...
Do you need remedial help in English grammar and word usage? Then see your
local elementary school...
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Towards an attack on Storin
Date: 6 Jun 2000 16:29:06 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> What you do is look for an input tuples (a, b, c, d)
For the avoidance of doubt, this is a single plaintext, with its four
component words labelled a, b, c, d.
> (where the lsb of each word is the same in the tuple)
Here, lsb is the least significant /bit/, I presume (rather than /byte/,
which I've also seen).
> where after one round the lsb is equal to the 12th bit.
Yes. This is correct.
> I don't think this can't be used to attack more then one round
> efficiently though...
I think I understand now. Thanks for clarifying. I think you confused
me by calling it a differential attack in your introduction. It looks
more like a linear attack, actually.
I believe that, at four rounds, I'm still the record-holder for attacks
on Storin, even though I `cheated' by using a 2^{144} work-factor. I've
a feeling this work factor can be reduced by using largish precomputed
tables, but I've not sorted out the details yet.
Other interesting avenues I've not seen explored yet:
* The suggestion I made in the original proposal of noticing when one
of the input words to the matrix is zero. I now believe that this
isn't doing to work well.
* Integer differential attacks, approximating the key mixing and
`linear' steps. This worries me the most, I think, so I'll have to
try doing some work on it.
* Matsui's linear cryptanalysis.
* A variant of the Square attack: take a set of 2^{24} chosen
plaintexts p_i for 0 <= i < 2^{24}, each equal to (i, x, y, z) for
fixed x, y, z. Call the words which differ `active', and, if each
active word runs through all 2^{24} possibilities, label the set
`balanced'. The initial set is balanced by definition. After the
first matrix multiply, linear step and the next key mixing, the set
will still be balanced, but all of the words will be active. Maybe
by using the ideas of the Square attack, this can be extended to
attacking 3 rounds. I don't think the similarity to Square and
Rijndael is sufficient to carry this very far.
* Tom mentioned interpolation attacks. I'd be interested to see any
results from this.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Solution for file encryption / expiration?
Date: 6 Jun 2000 16:32:35 GMT
Frank M. Siegert <[EMAIL PROTECTED]> wrote:
> >Encryption doesn't prevent copying. You just copy the ciphertext.
>
> It will stop people from 1) altering the PDF contents
Oh. Why is this an issue? People can write notes in their books. This
is considered good scholarly practice. (I don't do it myself because it
makes the books manky.)
> Another problem: A PDF/eBook/Whatever reader will need the decrypted
> contents to display it on screen - so somewhere in the machine the
> file is completely decrypted as soon as you see it.
Not only that, but the free PDF viewers can read `encrypted' files. I
expect that GhostScript-based viewers will be quite happy to print the
file.
-- [mdw]
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Tue, 06 Jun 2000 17:01:19 +0000
Mok-Kong Shen wrote:
>
> Mark Wooding schrieb:
[...]
> Your argument is correct. But it lacks the desired 'concreteness' of
> solution to my problem. Note that I can only assume the frequencies
> of the characters in the language (at best that the frequency values
> assumed are exact) but otherwise I have no additional informations
> (digrams etc. are assumed to be largely destroyed through e.g. a
> simple transposition). One has to show a 'concrete' way how to get
> anything from the xor of the two messages.
You are phrasing that like it's a study exercise...
As to "concreteness", what exactly do you want?
Assume you've got two messages encrypted with the same keystream
xored together in such a way that the key falls out.
Then you go on by making (and testing) assumptions about the
two messages.
Like language (character distribution), format (header information)
and so on. You compute the likelyhood of certain characters in the
xor-stream and check.
This increases your knowledge about the two messages, making it possible
to make further assumtions (guessing words and so on).
> Note also that, if the
> OTP is used exactly twice, then (1) the xor of different pairs of
> messages (each pair has the same OTP segment, but different pairs
> have different segements) are essentailly unrelated to each other and
> (2) if there is a number of messages intercepted, one has to correctly
> pair the messages according to the OTP segment used (how is that
> going to be done?).
Just like the whole idea of re-using an OTP keystream, it relies on the
stupidity of the people communicating. You test different variants
of reuse.
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Some citations
Date: Tue, 06 Jun 2000 12:17:21 -0400
Mok-Kong Shen wrote:
>
> I think that the following citations may be of some interest,
> because they may presumably not be unanimously accepted by
> us all and hence could trigger some discussions:
>
> Bandwidth expansion is not necessarily either a drawback
> or a strength of a system, merely a feature.
That makes sense.
> The Kerckhoffs principle is neither a correct description
> of, nor a self-evident prescription for, all secrecy
> design projects.
So what principle would be substitute? Or would he just
drop Kerckhoff's principle? If so I would ask "what possible
good would that serve?"
paul
------------------------------
** 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
******************************
