Cryptography-Digest Digest #206, Volume #12 Tue, 11 Jul 00 18:13:01 EDT
Contents:
Questions!!!! ("George Gordon")
Re: Proposal of some processor instructions for cryptographical applications (Andrew
Molitor)
Re: Steganographic encryption system (Andrew McDonald)
exports? ("George Gordon")
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: DES Analytic Crack (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: One plaintext, multiple keys (Zulfikar Ramzan)
Re: Quantum Computing (Was: Newbie question about factoring) (Nick Maclaren)
Re: One plaintext, multiple keys (David A Molnar)
Re: Base Encryption FAQ (immune from plain-text attacks)) ("Adam Durana")
Re: Random Numbers (Mok-Kong Shen)
Re: Quantum Computing (Was: Newbie question about factoring) (Bill Unruh)
Re: NTRU PKC ("Joseph Ashwood")
----------------------------------------------------------------------------
From: "George Gordon" <[EMAIL PROTECTED]>
Subject: Questions!!!!
Date: Tue, 11 Jul 2000 16:21:14 -0400
1) I read in the literature that impossible differentials can be found for
*any* Feistel cipher for up to 5 rounds. (Schneier, Biham) My question is
how is that possible for a design like Karn, MDC, etc where one side is a
full hash? ie: 5-round Karn. It doesn't make sense to me.
2) For RC4, is the full entropy of the key apparent in the output stream for
short messages? ie: a simple message like "Hello" ? How long must the output
stream be run for full key entropy to be apparent?? I'm assuming a 128-bit
key.
3) In Blowfish the F-function: F(x) = (((s1[a] + s2[b]) xor s3[c]) + s4[d])
is equal to F(x) = (((s1[b] + s2[a]) xor s3[c]) + s4[d]) *if* s-box 1 and 2
are equal values. Can anything be made of that?
4) Do the key-dependant S-boxes and the key-dependant subkeys in Blowfish
interact in any way to weaken the cipher or reduce it's bijectivity?
Thanks for any answers,
George
------------------------------
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
From: [EMAIL PROTECTED] (Andrew Molitor)
Date: Tue, 11 Jul 2000 20:29:56 GMT
In article <[EMAIL PROTECTED]>,
Maynard Handley <[EMAIL PROTECTED]> wrote:
>I don't buy this. The case we care about (or at least I care about) is
>cached data. The CPU already sees the cache as essentially a 256 bit wide
>structure and misaligned loads are not expensive because there isn't
>really a "byte" concept---the appropriate bits are simply pulled in.
Doesn't this imply 8x as many wires someplace, for bit enables
as opposed to byte enables, inside the chip?
Luckily, as we all know, wires are free inside a highly
integrated part ;) This also implies that for ordinary byte/word/long
operations (almost all the time) somebody has to drive 8x as many
microamps down some wires, the problem of getting all the stupid
signal to arrive at the same time is compounded 8-fold.
I know, why don't we analyze actual instruction streams
and see what the actual utility of bit-addressing would be, and
try to sort out what the best tradeoffs would be. It's probably
nearly impossible to justify bit-addressing just from the point
of view of ISA complexity, let alone from an implementation standpoint.
------------------------------
From: [EMAIL PROTECTED] (Andrew McDonald)
Crossposted-To: comp.os.linux.development.apps,uk.comp.os.linux
Subject: Re: Steganographic encryption system
Date: Tue, 11 Jul 2000 21:31:57 +0100
On Mon, 10 Jul 2000 21:09:59 +0100,
phil hunt <[EMAIL PROTECTED]> wrote:
> Andrew McDonald <[EMAIL PROTECTED]> wrote:
> >phil hunt <[EMAIL PROTECTED]> wrote:
> >
> >> (I am aware of stegFS, which is a steganographic file system for Linux.
> >
> >Oh, I think I might have heard of that one. ;-)
>
> I think you might :-)
>
> Incidently, it was a main inspiration behind my system.
>
> BTW, did you know that there's another Linux FS calling itself the "Steganographic
> File System"? (Confusing name, or what). It was written by two South Africans, but
> unfortunately its web page seems to be down.
I believe you are referring to vs3fs. We considered that although
this claimed to be inspired by the idea of the Steganographic File
System (originally proposed by Anderson, Needham and Shamir), it
didn't actually provide true steganography. It marks blocks as 'might
be used' which leaks information.
> >> in StegFS, keys have "levels of secretness":
> >> if you decrypt with one key, you automatically have access to all the data
> >> encypted with "less secret" keys -- in stes, all keys are as secret as
> >> each other).
> >
> >Later versions are more flexible in this area (e.g. have a look at
> >stegfsctrl).
>
> Do you have a URL for this?
If you have a look at the man page for stegfsctrl (in the 'man'
directory in the stegfs-tools tarball) it should give some
explanation - basically you can add/remove security 'levels' from
security 'contexts' (sets of levels).
Andrew
--
Andrew McDonald
[EMAIL PROTECTED]
http://www.mcdonald.org.uk/andrew/
OpenPGP DSA/ElG 1024/2048 3EDE 0FBC 6138 DCA0 FC8E C508 FCBB A9C8 F2DE ED36
------------------------------
From: "George Gordon" <[EMAIL PROTECTED]>
Subject: exports?
Date: Tue, 11 Jul 2000 16:37:02 -0400
What's the deal with www.cryptography.org/source ? Do any of you other
readers know ?
George Gordon
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Tue, 11 Jul 2000 22:54:18 +0200
Runu Knips wrote:
> Mok-Kong Shen wrote:
> > Runu Knips wrote:
> > > And, well, Serpent contains a really complex initial (and final)
> > > bit permutation, even if I don't understand whats the use for it,
> > > except that the cipher is seriously slowed down in software.
> >
> > It seems to be the majority opinion that the IP and inverse IP of
> > DES are entirely useless. Does anyone know any probable
> > design rationale for that?
>
> Well, I already said this statement was <censored> !! ;-)
Sorry, I don't understand the word 'censor' in this context. (I came
to know what censorship means, when long ago I was living in a
region occupied by foreign army in war.) I am the questioner in
the question I formulated above and it is besides about DES, not
Serpent. That same question I posed was also once raised in the
group quite a time ago, but I don't remember that it ever got a
good answer or even an half-good answer.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: DES Analytic Crack
Date: Tue, 11 Jul 2000 22:53:21 +0200
Volker Hetzer wrote:
> Mok-Kong Shen wrote:
> > I misunderstood you. You did mention BDD, but I didn't identify that
> > with your second approach. BDD, if I don't err, is a special form
> > of boolean optimizations which the electrical engineers have used to
> > simplify their circuits.
> It can be used for that too. But the more exciting use is for solving those
> equations.
>
> > So, for example, the equations describing the
> > S-boxes can be optimized with that. But the formal equations
> > describing DES in terms of bits as variables after optimizations are,
> > I guess, still beyond the reach of current resources to handle, in time,
> > if not in storage.
> How many bits are there? Bdd's have been used up to several hundred bits.
> Are those equations available for download anywhere?
Douglas Gwyn said that his former colleague has computed the set of
equations. But I doubt that he can help you since, according to him,
the project no longer exists.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Tue, 11 Jul 2000 22:53:33 +0200
Holger Bettag wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> writes:
> > Holger Bettag wrote:
> > > "Vector permute" would be the most outstanding candidate. Together with
> > > "vector select" and the bitwise shifts/rotates, one can build almost
> > > arbitrary bit permutations.
> >
> > Would you please explain a little bit these instructions and illustrate
> > with a tiny (reduced) example of how to effect an arbitrary permuation?
> >
> (shameless plug) There is an old text I once wrote about AltiVec:
> http://www.sci.fi/~saffron/transamour/altivec.htm
> In the last quarter, vector select and vector permute are described and
> small examples are given. (Beware, the web site has collected quite a bit
> of dust. End of plug)
>
> As for how to do an arbitrary 128x128 permutation, you start out by viewing
> the 128 bits as a vector of 16 bytes. Now, for each of the eight bits in all
> bytes, you do the following:
>
> 1. move the byte containing the corresponding source bit to the position
> of the byte containing the current destination bit.
> (one single vector permute does this for all 16 bytes, requiring a
> precomputed vector specifying the byte-wise permutation)
>
> 2. move the source bit in each byte to the position of the current destination
> bit. (one bytewise vector rotate does this in parallel for all 16 bytes,
> requiring a precomputed vector specifying the shift-amount for each byte)
>
> 3. copy the correctly positioned source bit to the destination vector
> (one vector select instrucion does this for all 16 bytes, requiring a
> precomputed vector specifying a mask that depends only on the current
> bit position, not the actual permutation)
>
> (4. repeat for all 8 bits)
>
> So, all in all you need 16 vectors of precomputed data that specify the
> exact permutation (but AltiVec gives you 32 vector registers to work
> with), and you either need 8 more mask values for the vector select, or
> you calculate the masks on-the-fly if you cannot spare the registers.
[snip]
Thanks. I understand now how it works. One needs however a bit
of computation to determine from the desired permuation the various
moves and rotates, as far as I can see.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Tue, 11 Jul 2000 22:53:43 +0200
Michael Dales wrote:
> Hmmmm. In your original posting you said you were providing suggestions
> for "future processors" - thus what's to stop Processor/FPGA hybrids
> becoming common in the future? Do you know something we don't? ;-) The
> rate at which acceptance of FPGAs is increasing suggests that
> reconfigurable logic will become common place in the not too distant
> future.
I do believe that a computer with reconfigurable logic can indeed be
desirable in certain situations. One issue that I think could be essential
is that the programming should be relatively easy, i.e. there need to
be good tools to support the user without much hardware expertise
to do the job, which I was told is not quite yet the case with FPGA.
M. K. Shen
------------------------------
Date: Tue, 11 Jul 2000 16:46:01 -0400
From: Zulfikar Ramzan <[EMAIL PROTECTED]>
Subject: Re: One plaintext, multiple keys
While it's not studied explicitly, AFAIK, when people use block ciphers in "hash
function mode" -- that is as a cryptographic hash funtion, then often the message
is kept the same, and the key is varied.
For example, to use the AES_k(m) (where k is the secret key, and m is the
message) as a hash function on an input x, one would compute:
HASH(x) = AES_x(IV).
Where IV is a fixed constant. To hash larger messages, one would employ some type
of chaining mechanism, etc,.
The point is that if it turned out that a block cipher was "weak" if the same
message was encrypted under different keys, this might mean that the resulting
variant of the cipher in hash function mode may have weaknesses as well; e.g. if
the outputs of the hash function had far from a uniform distribution in this case,
then collisions might become easier to find.
Hope this sheds some more light on the subject.
Zully.
Doug Kuhlman wrote:
>
> Believe it or not, I'd actually gotten the RSA example already. It
> seemed reasonably obvious. And Mok-Keng is right. I was asking for an
> example of a block cipher with/without this property.
>
> Is it even being studied? Are the AES candidates examined if the same
> plaintext is encrypted with multiple keys? Would a little salt at the
> beginning/end solve my problem?
>
> OK, I'm excessively stupid (or maybe just lazy). I couldn't even come
> up with examples like that. I thought if I could (or could convince
> someone else to), it might lead me to seeing how to avoid that problem
> in general.
>
> David A Molnar wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > > [snip]
> >
> > > He was however asking for an example of block cipher, I suppose.
> >
> > I know. I just wanted to give a somewhat natural example other than OTP.
> > I don't know of any natural examples for block ciphers, although it seems
> > you could come up with some explicitly stupid examples without too much
> > work.
> >
> > -David
--
--Zully
=======
Zulfikar Ramzan (AKA Zully)
Laboratory for Computer Science, MIT
NE43-311, (617) 253-2345
http://theory.lcs.mit.edu/~zulfikar/homepage.html
------------------------------
From: [EMAIL PROTECTED] (Nick Maclaren)
Crossposted-To: comp.theory
Subject: Re: Quantum Computing (Was: Newbie question about factoring)
Date: 11 Jul 2000 20:53:39 GMT
In article <[EMAIL PROTECTED]>,
Tony T. Warnock <[EMAIL PROTECTED]> wrote:
>
>That's true. I was basing my comment on the article by van der Poorten and
>Loxton in Crelle's Journal vol 392, p57, that (purported, there may be an
>error) that the bits of an algebraic number can not be generated by a finite
>state machine. Bit strings generated by finite state machines must be either
>rational or transcendental.
Well, as it stands, that statement is clearly false! As finite state
machines necessarily repeat, they can generate only rational numbers.
And, obviously, they can generate any rational number.
Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: [EMAIL PROTECTED]
Tel.: +44 1223 334761 Fax: +44 1223 334679
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: One plaintext, multiple keys
Date: 11 Jul 2000 20:36:17 GMT
Doug Kuhlman <[EMAIL PROTECTED]> wrote:
> Believe it or not, I'd actually gotten the RSA example already. It
> seemed reasonably obvious.
Yeah, that's the nice thing about it. It's really obvious once you think
about it a little bit in the right way...
> OK, I'm excessively stupid (or maybe just lazy). I couldn't even come
> up with examples like that. I thought if I could (or could convince
> someone else to), it might lead me to seeing how to avoid that problem
> in general.
Well, the one which came to my mind wasn't quite in the spirit of what you
wanted....consider
STUPID (m, key) = E(m, key) || r XOR key
where E() is any block cipher, m is a message, || concatenation, and
r is a random number which is kept constant for all keys.
Given messages encrypted with just one key, r XOR key is like a
one time pad. Given messages encrypted with different keys, you can
recover the XOR of the keys. If you ever get a message where you know
the key (such as if someone sends a message to you), you can recover r
and recover all keys.
It's not quite in the spirit of what you wanted because there's no
dependence on the message m. I'm fairly sure that you could come
up with a similar, explictly stupid example that is in the spirit
of what you wanted, but not sure it would tell us much.
by "explicitly stupid" I mean the kinds of examples that have
a block cipher output its own key or part of the message in crudely
disguised form. These suffice to show that such ciphers can exist, but
they don't seem to tell us much about whether or not practical ciphers
have this property.
Sorry I'm not more helpful. :-\
-David
------------------------------
From: "Adam Durana" <[EMAIL PROTECTED]>
Subject: Re: Base Encryption FAQ (immune from plain-text attacks))
Date: Tue, 11 Jul 2000 17:11:02 -0400
> Why is Base Encryption strong?
>
> Answer:
> Base Encryption utilized many unique properties that are
> unbreakable. It provides dynamic base (symbol set), dynamic
> algorithms (operators and operations), and one-time-pad security
> without the inconveniences. It is a full-fledged cypher that easily
> fits into the internet's web-centric model.
When you say dynamic operators are you counting say addition in base X as a
different operation than addition in base Y? And about being as secure as
OTP, that just isn't true.
> Why is Base Encryption Strong?
>
> Answer:
> It is basically immune to brute-force attacks. You are not able
> to permutate on a n+1 basis like static length keys. You do not
> know the symbol set. You do not know the length. You do not
> know the algorithms involved. You do not know anything! Even
> if you know, you don't know if your "key" is correct! See below.
If you don't have a symbol set, key length, block length or algorithm (which
would incorperate the latter), then you don't have a method of encryption.
Once you define a set of bases, key lengths, block lengths and algorithms
that can be used for encryption, it can be brute forced. And even if each
of those options have infinite possibilities, I could still brute force it,
because I can keep testing different combinations of the options until I get
the right one. Now depending on what type of search techniques and what
options are actually used the search may take 1 second or 1 billion years.
> Why is Base Encryption Strong?
> It utilizes the unique (I invented it first!) throw away
> algorithms. Most encryptions these days can utilize throw-away
> keys. But in Base Encryption, because the algorithms are
> dynamic, in streaming cyphers or just plain normal encryptions
> you can change algorithms on the fly based on arbitrary factors.
> (time, length, etc).
Like someone else said using different bases during encryption isn't
anything new. I believe a wtshaw makes frequent posts about algorithms
using different bases.
> Why is Base Encryption strong?
>
> Answer:
> In addition, base encryption is immune to plain-text-attacks.
> Because multiple algorithms can generate a plain-text, plain
> text attacks are useless against Base Encryption.
No plain text attacks are not useless. Multiple algorithms can decipher
cipher text to plain text, but only one algorithm and key will decipher the
cipher text to the correct plain text. There maybe some freak chance that
you find an algorithm and key that will decrypt the cipher text generated by
a different algorithm and key, but how likely is that? Hopefuly not at all.
> Why is Base Encryption Strong?
>
> Answer:
> Base Encryption is internet-ready, and modular. Because the
> algorithm can be modified on the fly, you can use adaptive
> plug-and-play cypher engines with it. Simply plug in twofish,
> RC6, IDEA, as an augmentative step in the algorithm! Make one
> up yourself and use it like another operator!
So just skip "base encryption" and lets all use personal secret algorithms!
Do you see the problem with this?
I suggest you learn more about cryptology before you make any more of these
outlandish claims again. And next time you write an FAQ, it might be a good
idea to answer more than 1 question in it.
- Adam
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random Numbers
Date: Tue, 11 Jul 2000 23:28:19 +0200
John Savard wrote:
> <[EMAIL PROTECTED]> wrote, in part:
>
> >I don't know whether it is (or easily) possible to prove rigorously that
> >your procedure is exact. I would simply throw away the out of range
> >values.
>
> Oh, it is quite possible.
>
> Let us say that I want numbers that are from 0 to 999, and I have a
> source of numbers from 0 to 2056.
>
> If every number from 0 to 2056 is equally likely, then it does
> immediately follow:
>
> taking the last three digits gives you a number from 0 to 999 that is
> unbiased, because 0 and 1000 together are just as likely as 1 and
> 1001;
I am not quite sure of the above. The numbers from 0 to 1999
contribute a count of 2 to each of the numbers from 0 to 999.
The rest 2000 to 2056 evidently don't add equal counts to
each of the numbers from 0 to 999.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Quantum Computing (Was: Newbie question about factoring)
Date: 11 Jul 2000 21:19:00 GMT
In <[EMAIL PROTECTED]> "Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
>Bill Unruh wrote:
>> ... NMR computations are the the only computers which have been
>> created with more than one or two qubits, but ...
>Check out the news about Josephson junctions.
>From what I have seen that is single bit coherence. A few steps away
from something useful.
The press reports and the facts can sometimes be slightly divergent.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: NTRU PKC
Date: Tue, 11 Jul 2000 14:15:00 -0700
Ok, I think we've played around off-topic long enough, let's get back to
something on-topic.
It's personal policy to abuse any system (whether patented, good or bad) tht
claims to protect data on a users system when it is placed into the hands of
extremely hostile users. Hence the attack I mentioned in that same message
(the attach a recording device to the sound card instead of speakers) was
also explicitly mentioned, and made no use of the presence or lack there of
of the encryption, the same technique applies to making an audio tape of an
MP3 or a song protected by the technique in question.
Joe
"Vin McLellan" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Joseph Ashwood wrote:
>
> > Given that I accept that this was a genuine misunderstanding. I was not
> > referring to NTRU itself as worthless and wasteful, as a matter of fact
I
> > have not yet studied NTRU to make such a determination. However, I was
> > making a similar statement regarding using cryptography to prevent the
> > piracy of MP3s, even given perfect cryptography, the benefits can be
gotten
> > around, and an unrestricted MP3 made, making the protection only an
> > annoyance for legitimate users.
> > Joe
>
> I acknowledge, too, that I should not have used such a complex
> reference in such a jocular and teasing manner, particularly in this
> forum.
>
> I also presume that there were several layers of misunderstanding
> here.
>
> I regret any confusion my use of a perhaps slightly out-of-context
> quote may have caused -- but I still think you should have looked up the
> damn patent before you 'dissed and dismissed it on the Net;-)
>
> _Vin
------------------------------
** 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
******************************
