🚀 go-pugleaf

In article <Bw1614.2tM@vcd.hp.com> egurney@vcd.hp.com (Ed J. Gurney) writes:
>I've been working with the following encryption scheme and am wondering
>how hard it would be (or if it's even possible at all) to devise a method
>of "reversing" it.  Someone has told me this is an "NP-Hard" problem,
>but I thought I'd ask all you net.gods.  Here's a description:

>The system works by encrypting the data in 8 byte chunks.  So repetitive
>data (8-byte aligned) always appears the same way in the encrypted data.

Okay, sounds like DES in ECB mode (8 bytes = 64 bits).


>This particular encryption method uses an 8 byte key, which is in turn 
>passed to a routine to generate a (unique) sequence of 32 bytes used in
>the actual [en|de]cryption.

(Sorry for the byte->bit coversion; I'm used to thinking in terms
of bits):
Okay, a 64 bit key that gets mapped to a 256 bit key internally;
a fairly common scheme for a multi-round encryption scheme.

>My question is this:  Assuming you know for a fact that a certain eight
>bytes of encrypted data decrypt to a known set of eight plaintext bytes,
>can you find the original key and decrypt the rest of the data?  The only
>information you have is the decryption routine written in C, the eight
>encrypted bytes, and the eight plaintext bytes.  The decryption routine
>is _not_ the same routine used for encryption.  (i.e., feeding the plaintext
>and a key to the decrypter does not generate the encrypted data.)

This is known as a "known plaintext" attack, and is considered to be an
important property for an algorithm to be considered secure.  It
_really_ depends on your specific algolrithm.  Most attemts to create
an algolrithm that would do this have fallen to cryptanalysis; the only
two that I know of that have resisted attack (so far) are DES and IDEA.


>A brute force approach does work (I've verified that, but it takes a long
>time to try all 2^32 possible combinations, even on a relatively fast RISC
>machine.)

Where did 2^32 come from?  The 32-byte internal state would give you
2^256 possibilities, but this is irrelevant since the state was
deterministically generated from your 2^64 bit (8 byte) key.  A
strong cryptosystem leaves the cryptanalyst with nothing but brute-force
to work with, and has a key space that makes brute-force infeasable.


>           This is probably acceptable because the number of keys will be 
>very high and would take a long time to find them all.  Assuming that
>                  Plaintext + Key = Data
>it follows there should be some way to then apply
>                  Data + Plaintext = Key
>I want to know if this logic holds, or if this system is "immune" to that 
>sort of approach.

It may be possible to create an encryption system that would be immune
to this approach.  I have no way of knowing if the specific system that
you are considering has this property from the description that you
have given in your posting.


>If it matters, the decryption algorithm consists of the routine to generate
>a 32 byte "subkey" from the original 8 byte key and another routine with an 
>8-cycle loop that exclusive ors, rotates left and adds byte-sized
>operands.

Again, hard to say with this vauge description, but your system probably
has weaknesses.  DES uses simple operations too, but one of the critical
components are its "S-boxes", which do a non-linar substituton transform;
if your "byte-sized operands" are non-linar, data/key-dependant values,
then your scheme _may_ have promise, but the likelyhood is low (based on
history).


I'd say that you are looking for most of the important qualities in
a good cyphersystem, but I have doubts that you have found a good
algolrithm.  As others have said before: you really should get a
fair amount of experience in cryptanalysis before trying to invent
a new cryptosystem -- otherwise you'll probably miss guarding against
many well known attacks.


		--Ken Pizzini