Cryptography-Digest Digest #250, Volume #11 Sat, 4 Mar 00 02:13:02 EST
Contents:
Re: Decompiling/Tamper Resistent (Samuel Paik)
Re: Cellular automata based public key cryptography ("Trevor Jackson, III")
Re: Best language for encryption?? ("Douglas A. Gwyn")
Re: Cellular automata based public key cryptography ("Trevor Jackson, III")
Re: Best language for encryption?? ("Douglas A. Gwyn")
Re: Can someone break this cipher? ("Douglas A. Gwyn")
Re: brute force attack on a 128 bit SSL key? ("Douglas A. Gwyn")
Re: Far out crypto claims ("Douglas A. Gwyn")
Re: Cellular automata based public key cryptography ("Douglas A. Gwyn")
Re: NIST, AES at RSA conference (David A Molnar)
Re: On jamming interception networks (David A Molnar)
Re: very tiny algorithm - any better than XOR? (Carl Byington)
Re: very tiny algorithm - any better than XOR? (Carl Byington)
Explaination of method question (Nemo psj)
----------------------------------------------------------------------------
From: Samuel Paik <[EMAIL PROTECTED]>
Subject: Re: Decompiling/Tamper Resistent
Date: Sat, 04 Mar 2000 04:10:08 GMT
Andru Luvisi wrote:
> [EMAIL PROTECTED] writes:
> > In order to protect our intelectual property (software) from decompiling
> > freaks, we need to build our crypto software in a tamper resistent
> > device for our network crypto cards.
> >
> > Any advice on how this may be done?. Is this some kind of special
> > EEPROM or a sealent in the box?
>
> You can't. And even if you could, it would be a bad idea, since it
> makes your product less valuable to people who purchase it.
I'll point out that stevei asked for tamper-resistant, not tamper-proof.
A number of commercial programmable devices (from EEPROMs to complete embeded
computer systems on a chip) have features to try to make read-out of the
programming difficult. Check datasheets from various vendors. (for an
example of the latter, see http://www.ibutton.com/)
You are likely to get a number of messages noting that this will not
appreciably increase security. Tamper-resistent packaging and devices
may discourage casual intruders, but will not stop serious ones.
--
Samuel S. Paik | http://www.webnexus.com/users/paik/
3D and multimedia, architecture and implementation
You dont know enough about X86 or kernel architectures to argue with me.
- <38b2dc12$0$[EMAIL PROTECTED]> "Leon Trotsky" to Terje Mathisen
------------------------------
Date: Fri, 03 Mar 2000 23:39:21 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Cellular automata based public key cryptography
Wolfram did some work on automata ciphers. They turned out to have weaknesses,
but it worth a look. I regret that I don't know of any online references.
Tim Tyler wrote:
> I've recently developed an interest in public key cryptography based on
> cellular automata.
>
> This was pioneered in the 1980s by the Chinese cryptographer, Tao Renji.
>
> I've compiled a bibliography of his work at http://alife.co.uk/ca/taorenji/
>
> Since this work was largely published in Chinese - and is thus not
> terribly accessible to me - I've redeveloped the basic ideas behind the
> system.
>
> A preliminary description of my explorations is available on the web.
>
> The basic idea is a technique for generating reversible finite automata
> whose inverses have domains that are unboundedly large.
>
> This technique generates "quasi-linear" automata with "weak" inverses.
>
> I describe this technique at http://alife.co.uk/ca/largeinverse/
>
> This technique can be used as the basis of a public key cryptosystem:
>
> The basic idea involves generating two finite invertable cellular automata.
> At least one of the automata should contain a significant number of
> non-linear components. The two automata are combined, to form a third
> automata which is then published as the public key.
>
> Combining the two automata is done by creating a third automata
> which is equivalent to applying them in sequence. This is done by
> algebraic combination, and expanding out the resulting terms.
>
> To encrypt data, it is passed through the published automata.
>
> To decrypt, the inverses of the two automata are applied in sequence.
>
> This relies on the fact that finding the inverse of the public automata
> - without knowledge of its components - is a difficult problem.
>
> It can be difficult to decompose a composite automata into its component
> parts - in very much the same way that it is difficult to factor the
> product of two large primes.
>
> http://alife.co.uk/ca/publickey/ describes the proposed process in
> a little more detail.
>
> I have not yet built any sort of system based on these ideas.
>
> It appears that the resulting system should work /extremely/ rapidly when
> implemented in appropriate hardware - but may have large keys.
>
> I have not yet managed to read a single one of Tao Renji's papers, or
> any of those cryptanalysing his system. /All/ my knowledge of his work
> comes from the pages of "Applied Cryptography" (2nd ed. p.500) :-(
>
> I am keen to learn more about the original work, so I can avoid
> duplicating it, and to learn from previous exploration of the area.
>
> If anyone can help me by providing me with details that I do not already
> have access to, that would be very helpful. For example, if there are any
> books in print containing any of the papers in my bibliography, I'd be
> interested to learn about this.
>
> I do not yet have much familiarity with other public key cryptosystems.
>
> If there are other methods - which do not rely on large prime numbers,
> the discrete logarithm problem, etc - and which might bear some possible
> relationship to the system I describe - a pointer might be useful to me.
>
> Any comments about the proposed system would also be welcomed.
>
> Please don't advise me that my descriptions are currently vague and
> incomplete, though - since I'm aware of that already.
> --
> __________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
>
> Never call a man a fool. Instead, borrow from him.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Best language for encryption??
Date: Sat, 04 Mar 2000 04:32:09 GMT
Paul Schlyter wrote:
> What's the major differences between C-99 and C-89?
I don't have a convenient list at hand, but such a list has been
posted in places like comp.std.c and comp.lang.c.moderated, by
Clive Feather and Peter Seebach as I recall, maybe also Larry Jones.
So a search through last year's archives should turn it up.
One "new" thing in C99 is that it incorporates the stuff I
previously mentioned that amended C89. Beyond that, there
is support for complex numbers (and optionally pure imaginary
numbers), type-generic math functions, variable-length arrays,
"noalias" specifier to improve optimization, empty arguments
for function-like macros, headers for a Boolean type and
specified-width integers, "inline" functions, larger minimum
maximum limits, on-the-fly variable declaration, \u and \U
sequences for universal character specification, optional
IEEE/IEC floating-point binding, other features I don't
remember right now, and numerous small improvements.
> Did C-99 finally get e.g. classes and exceptions?
No; they were proposed and discussed, but never attained a
consensus.
------------------------------
Date: Fri, 03 Mar 2000 23:41:56 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Cellular automata based public key cryptography
Wolfram did some work on automata ciphers. They turned out to have weaknesses,
but it worth a look. I regret that I don't know of any online references.
Tim Tyler wrote:
> I've recently developed an interest in public key cryptography based on
> cellular automata.
>
> This was pioneered in the 1980s by the Chinese cryptographer, Tao Renji.
>
> I've compiled a bibliography of his work at http://alife.co.uk/ca/taorenji/
>
> Since this work was largely published in Chinese - and is thus not
> terribly accessible to me - I've redeveloped the basic ideas behind the
> system.
>
> A preliminary description of my explorations is available on the web.
>
> The basic idea is a technique for generating reversible finite automata
> whose inverses have domains that are unboundedly large.
>
> This technique generates "quasi-linear" automata with "weak" inverses.
>
> I describe this technique at http://alife.co.uk/ca/largeinverse/
>
> This technique can be used as the basis of a public key cryptosystem:
>
> The basic idea involves generating two finite invertable cellular automata.
> At least one of the automata should contain a significant number of
> non-linear components. The two automata are combined, to form a third
> automata which is then published as the public key.
>
> Combining the two automata is done by creating a third automata
> which is equivalent to applying them in sequence. This is done by
> algebraic combination, and expanding out the resulting terms.
>
> To encrypt data, it is passed through the published automata.
>
> To decrypt, the inverses of the two automata are applied in sequence.
>
> This relies on the fact that finding the inverse of the public automata
> - without knowledge of its components - is a difficult problem.
>
> It can be difficult to decompose a composite automata into its component
> parts - in very much the same way that it is difficult to factor the
> product of two large primes.
>
> http://alife.co.uk/ca/publickey/ describes the proposed process in
> a little more detail.
>
> I have not yet built any sort of system based on these ideas.
>
> It appears that the resulting system should work /extremely/ rapidly when
> implemented in appropriate hardware - but may have large keys.
>
> I have not yet managed to read a single one of Tao Renji's papers, or
> any of those cryptanalysing his system. /All/ my knowledge of his work
> comes from the pages of "Applied Cryptography" (2nd ed. p.500) :-(
>
> I am keen to learn more about the original work, so I can avoid
> duplicating it, and to learn from previous exploration of the area.
>
> If anyone can help me by providing me with details that I do not already
> have access to, that would be very helpful. For example, if there are any
> books in print containing any of the papers in my bibliography, I'd be
> interested to learn about this.
>
> I do not yet have much familiarity with other public key cryptosystems.
>
> If there are other methods - which do not rely on large prime numbers,
> the discrete logarithm problem, etc - and which might bear some possible
> relationship to the system I describe - a pointer might be useful to me.
>
> Any comments about the proposed system would also be welcomed.
>
> Please don't advise me that my descriptions are currently vague and
> incomplete, though - since I'm aware of that already.
> --
> __________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
>
> Never call a man a fool. Instead, borrow from him.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Best language for encryption??
Date: Sat, 04 Mar 2000 04:34:29 GMT
wtshaw wrote:
> > > what a crock, ...
> <[EMAIL PROTECTED]> wrote:
> > It certainly is a crock, but it's your fault for having a crappy
> > program design. Instead of trying to write BASIC in C, you should
> > learn to use C on its own merits. (Same for *any* language.)
> One has to start somewhere, and I have not the time to waste if I
> can help it.
My point was that you are wasting your time if you're trying to
program in C as if it were BASIC.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Can someone break this cipher?
Date: Sat, 04 Mar 2000 04:39:07 GMT
Daniel wrote:
> is there a standard procedure to be followed if it is
> an unknown cipher? How would a professional cryptographer/
> cryptoanalyst go about this cipher?
There are rather large textbooks on the subject; it cannot be
done justice in this forum. The sci.crypt FAQ has references.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: brute force attack on a 128 bit SSL key?
Date: Sat, 04 Mar 2000 04:46:56 GMT
Paul Koning wrote:
> That doesn't clarify anything (for me anyway). Does it produce
> inaccurate answers? If so, why? And in what direction? What
> approach would you use instead, and why?
The argument on the basis of k*T per operation makes several
unnecessary assumptions, for example that the mean free path
is a limiting factor. That means it's assuming irreversibility,
but as we now know, computers can be built with reversible gates.
Also, the temperature of the supposed cosmic background radiation
is irrelevant; systems can and have been cooled to lower
temperatures.
If you want a much better estimate of the actual limits, check
out Feynman's exposition in the book "The Pleasure of Finding
Things Out".
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Far out crypto claims
Date: Sat, 04 Mar 2000 04:54:31 GMT
[EMAIL PROTECTED] wrote:
> I said "If I were a fanatic believer".
I appreciated that point. I was just addressing (briefly)
the argument you presented. Of course, a *real* True Believer
is not swayed from his predetermined position by any amount
of debate. But onlookers might be..
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cellular automata based public key cryptography
Date: Sat, 04 Mar 2000 04:58:42 GMT
"Trevor Jackson, III" wrote:
> Wolfram did some work on automata ciphers.
I'm pretty sure this was written up as a Scientific American article
within the past few years.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: 4 Mar 2000 05:12:08 GMT
John Savard <[EMAIL PROTECTED]> wrote:
> Well, allowing the user to alter the algorithm, within limits, is a
> good idea.
Let's just hope we know a *lot* about what limits are proper when
designing the user modification mechanism.
-David
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: On jamming interception networks
Date: 4 Mar 2000 05:17:31 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Douglas A. Gwyn wrote:
>> That argument isn't even worthy of a sophomore.
> Do you really mean that nonclassical logics are familiar to
> the sophomores (or at least in the US)?
Well, a friend of mine did a paper on nonclassical logics as a project for
a class on logic last term. He's a sophomore. There were other sophomores
in the class, as well.
I do not think that's what was meant by the statement "That argument isn't
even worthy of a sophomore", however.
------------------------------
From: [EMAIL PROTECTED] (Carl Byington)
Subject: Re: very tiny algorithm - any better than XOR?
Date: 4 Mar 2000 05:58:14 GMT
=====BEGIN PGP SIGNED MESSAGE=====
In article <89o9j3$9tj$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
>50 bytes of code space on a AVR is only 25 instructions at the most.
>That's very limited for a block cipher. You may either want to make
>use of a independant encryption chip [like a IDEA chip etc..] or give
>at least 512 bytes of codespace. I only worked with the AVR8015 which
>[if I remember] had a few kb of codespace available.
Yes, the constraints on this are rather extreme. We get 50 bytes of code
space, no more than 30 bytes of ram, and no ability to add any extra
hardware like an encryption chip.
>> I did look at TEA, but I don't see any way to get that into anything
>> like 50 bytes on this processor.
>
>Well if you design it modular enough [around the 32-bit functions
>required] you should be able to fit tea in around 256 words on an AVR.
Actually the C compiler did TEA in about 400 bytes.
>This code will be much too slow if you are doing a comm link of some
>sort. Have you considered simpler ciphers such as RC5?
Only a bit too slow. I am now considering something like:
void decrypt(word8 *k, word8 *v)
{
int i, j, r;
for (r=3; r>-1; r--) {
for (i=6; i>-1; i--) {
for (j=3; j>-1; j--) {
// feistel network v[i], v[i+1] form the 16 bit block
// L = v[i]
// R = v[i+1]
word8 t = v[i];
v[i] = v[i+1] ^ ((rotate_left(t) + k[r*4+j]) & 0xff);
v[i+1] = t;
}
}
}
}
Basically 4 rounds with 7 overlapping 16 bit blocks. Four bytes of the
key is used in each round. RC5 is too complicated - not a chance to do
it in 50 bytes on this processor. From the instruction timings, it looks
like this will meet our performance goals.
>OT: BTW what C compiler are you using with the AVR?
Not sure - some other folks are doing all the C stuff for the main
application. I am handcoding this part in assembly.
- --
PGP key available from the key servers.
Key fingerprint 95 F4 D3 94 66 BA 92 4E 06 1E 95 F8 74 A8 2F A0
=====BEGIN PGP SIGNATURE=====
Version: 4.5
iQCVAgUBOMCl7NZjPoeWO7BhAQGBNwP8DHLO8H/2Jr+mBMEU80kFvxyp02BnNoZG
qiGJvzANhSfCh+jvpddoakMzYU9Wm5BPx6yJOCIkS4gNqdf0hdTR+AAs1vc/ZoZB
dLP7NiqJrUF2HpoksF92Qz6kB3gI7ctpK0brBr/a+70lwI70l9qfy3ah2aP+SSIF
/uGgTETHdVA=
=IUEV
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Carl Byington)
Subject: Re: very tiny algorithm - any better than XOR?
Date: 4 Mar 2000 06:10:30 GMT
=====BEGIN PGP SIGNED MESSAGE=====
In article <89nrau$u9s$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
>Can I ask what the application is? Maybe you could use some of the
>cpu program space to code a small interpreter, and run "programs" from
>the eeprom, migrating other parts of your application to eeprom except
>for the speed critical parts.
Already doing that. Much of the program code space is used by the
interpreter, and much of the ram is used by the global variables for
the interpretive code in eeprom. The rest is used for the time sensitive
communications stuff.
>Ignoring security issues, trying to do rc4 with 5 or 6 bits will
>likely blow your 50 byte code limit because of the extra code needed
>to shift the bits around to emit the output stream as 8-bit bytes.
>
>How about a simple additive RNG? That should run faster and take less
>code than a bit-twiddling LFSR. Cryptanalysis methods for it are well
>known, but unlike xor, you at least have to know what you're doing to
>break it. Since, as you say, attackers can get the plaintext by probing
>the hardware, high cryptographic security might worth much trouble.
Does the following give better security than a simple additive RNG?
void decrypt(word8 *k, word8 *v)
{
int i, j, r;
for (r=3; r>-1; r--) {
for (i=6; i>-1; i--) {
for (j=3; j>-1; j--) {
// feistel network v[i], v[i+1] form the 16 bit block
// L = v[i]
// R = v[i+1]
word8 t = v[i];
v[i] = v[i+1] ^ ((rotate_left(t) + k[r*4+j]) & 0xff);
v[i+1] = t;
}
}
}
}
We only have 4 rounds with 7 overlapping 16 bit sub blocks, and each
round only uses 4 bytes of the key. But it does meet the space and
(I think) the performance requirements.
- --
PGP key available from the key servers.
Key fingerprint 95 F4 D3 94 66 BA 92 4E 06 1E 95 F8 74 A8 2F A0
=====BEGIN PGP SIGNATURE=====
Version: 4.5
iQCVAgUBOMCoqNZjPoeWO7BhAQFwYAP5AWm2qQ+0LYcnz5W0sDCuNWsIijgtne2O
45pIkT93Ckj1McsPL4pDC0/+bgsSBfDCdyBQWqJ0l2pzPZItRGHDVkk6bkdp11yW
iRBoBg6TT6whyIaX1QRCQoxwsUVXWuujuBUsILgqAv2wq0Bk5Nkng3ios/UUalOK
6GjGgv1nlr0=
=0IF0
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Subject: Explaination of method question
Date: 04 Mar 2000 06:33:12 GMT
Soon I may be asking if someone can lay an attack on my encryption algy so
i can find the problems with it and hopefully defeat them. I have written an
explaination and uploaded it on my site I'm hoping maybe some of you could
check it out and tell me if the explaination is enough to explain the
encryption algy or weather it seems that with the info provided there is
something missing.
http://home.cyberarmy.com/puregold/Enigma%20Enc.zip
this is the url to the zip containing the explaination of the algy.
Also if any of you know where to find proven methods of crypto that have not
been broken in VB source i'd be greatfull the onlythings i can find are c and
VC and Java
-Pure (thanx)
------------------------------
** 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
******************************
