From: jhmeyers@miu.edu (John H Meyers)
Subject: Simple encryption on HP48
Date: 25 Apr 1997 00:00:00 GMT
Message-ID: <5jpm1r$o81$1@news.iastate.edu>
Organization: M.U.M. (Author's personal opinion only)
Newsgroups: comp.sys.hp48


In this article, we will examine a too-simple encryption method
found on a Goodies Disk; we will then offer a good replacement
which should work on any HP48S/SX/G/GX.

The program CODER on Goodies Disk #5 does simple "encryption"
by XORing the "plaintext" string with a repeated "key" string.

How well does this "scramble" the original message?

Imagine the original plaintext to be cut up into "blocks" of the
same length as the key, and call these blocks A, B, C, D etc.

After XORing each block with the repeated key K,
we have: AK, BK, CK, DK etc.  (the "encrypted" message)

XORing each adjacent pair of the above, we have:
AB, BC, CD, DE etc. (because AK*BK = AB*KK = AB*0 = AB).

Note that no matter what the original key K was, we now
have something reflecting the original plaintext only;
the key K has been completely eliminated!
To do this, all we need to know is the length of K.

If we can now "guess" any part of the original plaintext of the same
length as K, let's say we guess what "C" is, we will then be able to
immediately find its immediately neighboring text(s) via "XORing out"
the value of C, and we can easily "cascade" this all the way
through the message to obtain the entire original plaintext.

Even a correct guess of one or two letters will reveal the
corresponding letters in all the other "blocks," so it
doesn't look as though this message will be hard to "crack."

Is guessing the correct length of K very difficult?
well, what's the longest key you would ever consider
typing into your HP48?  How long would it take to try
each integer length value up to that number?

The set of characters from which we choose a "key" is also
generally much smaller than the set of all 256 possible
characters, which generally immediately "gives away"
the fact that we have encoded the plaintext using a
plain text key, and suggests the above line of attack.

-------------------------------------

A small improvement upon the method of XORing with a key
is to generate a "random" stream of bytes from the key,
and to make sure that this stream of bytes, which we will
XOR with the original plaintext, does not ever repeat!

Since it just so happens that we have a "random" number
generator built into the HP48, we could use as our "key"
an original *number* with which we "seed" the output of
all subsequent RAND commands, using the RDZ command to
initialize the random number generator.

The program supplied below accepts an input string and
a *numeric* encryption key, and then XORs the string
with "random bytes" generated as above.

The random number generator does not repeat its whole sequence
for a good long while (on the order of 10^12, it is said), and
you have a choice of well over 10^12 numeric "seed" values,
since the value of the exponent is used as well
(except that E-13 thru E-16 give identical results).

If you use the same key with two or more texts, however,
all anyone need do is XOR those encrypted texts together,
as above, and presto -- the "key" is completely "canceled out,"
leaving the XOR of the two plaintexts alone, which may provide
plenty of clues to decipher those plaintexts.

We can actually remedy this situation, but first let's
supply a very short encryption program CRYPT, based on
the above adjustment to the original "coder":

%%HP: T(3); @ \-> is "right arrow" etc.
@ Stack args and results:  "string" real --> "encrypted/decrypted"
\<< DUP NOT { EXP } IFT RDZ \->STR DUP "" 1 ROT SIZE
    START RAND 256 * CHR + NEXT XOR \>>

If the level-2 object is not already a string, it will be converted
to a string; the number you choose as a "key" must be on level 1;
zero is not recommended, but I included a "safety" feature to
replace zero with 1 if zero is specified, because 0 RDZ causes
the random seed to be set randomly, according to the instantaneous
time, and you would not otherwise be able to reproduce that seed.

It is naturally better to use a hard-to-guess number of many digits
than a simple number of one or two digits; another strategy is to
remember a sequence of functions like Sqrt, LOG, SIN, etc. which
you apply to an originally "simpler" number that you can remember.

To use a familiar text string as a key instead of a number,
use the HASH function below.

To decrypt, use the same key again on the encrypted string.
If a different key is used, then both keys must be used again,
in any order, to decrypt the "doubly-encrypted" file.

The program is fast enough for any small texts.

For larger texts, a 1000-character file took 25 seconds
using the above pure User-RPL version.

Replacing the "+" command with #5193h SYSEVAL (note the HEXadecimal
address) cut that time down to 21 seconds; this system function
concatenates two *strings* only; do not try to use it for
any other kind of "addition"!

Using Joe Horn's PACK program on the program containing the SYSEVAL
brings it down further to 18 seconds per 1000 characters.

A pure SysRPL version might improve this further, but note that the
main time consumer is that one small loop creating random characters,
before the final XOR; even in the complete package below, this
same loop is the only significant place where time may be saved.

-----------------------------------

What about the problem of using the same key more than once?

This can be solved by creating a random value, dependent upon
the instantaneous time, and combining that value with the
user-supplied key value.  The random value is included
along with the encrypted text, so that it will again
be available at the time of decrypting the text.

When this strategy is used, not only is it impossible
to connect two or more messages to "eliminate" the
key from their combination, but you can even encrypt
the same plaintext repeatedly using the same key,
and each ciphertext will be completely different,
so that you can not recognize repeated text
either in the same or in different messages.

The set of programs below implements this strategy
and offers a complete encryption/decryption package.

The reasons why stream XORing is not ideal for many purposes
are often mentioned in newsgroup sci.crypt; however, what we
have here is a pretty satisfactory method for the HP48.

With a 32-bit random initial value ("initialization vector"
in crypto parlance) and a key having nearly 40 bits of "entropy"
(the limit for export from the USA under "ITAR" regulations
which classify cryptography as a "munition"),
I think it will prove impervious to attack by any program
running on the slow and memory-limited HP48 itself, unless you simply
choose a "stupid" key having few digits, which can easily be guessed
(guessing common keys is known as a "dictionary attack").

On a very fast workstation, a "brute force" attack (trying all keys)
might not take very long.  However, the attacker would first have to
replicate the exact functionality of the internal HP48 arithmetic and
randomizing logic before even beginning; the slightest difference
between the results of any other system vs. the HP48
could throw the whole thing off.

If the folks from whose prying eyes you want to keep the
confidential scribbles in your HP48 do not feel it to be worth
the investment to develop a replica on a fast PC or workstation,
then you probably needn't be concerned with that possibility.

If you do want a heavier-duty function, such as MD5/Luby-Rackoff,
for your HP48, Steve VanDevender has a 5400-byte ML library
available at <ftp://ftp.efn.org/pub/users/stevev/>; according to his
documentation, it should take about 5 seconds for a 1000-byte string.

Steve is also owed thanks for his previous analysis of the HP48
RDZ and RAND functions, upon which knowledge I have drawn.

Below is the HP48 directory for the system I use; you can download it
all at once via Kermit, or manually type each individual program
(take particular care with any SYSEVALs, which can wipe out memory
upon any mistake -- memory backups are recommended).

The essential part of this system is only 502 bytes;
two non-essential programs totaling 178 bytes more
are included for your interest and amusement.

More notes follow, after the program listings:

---------------------------------------------

%%HP: T(3); @ \-> is RightArrow, \v/ is SqRoot, etc.
DIR @ XOR stream cipher with 32-bit random IV, 12-digit numeric key.
  ENCRYPT @ Plaintext  Numeric_key  -->  Encrypted_text
    \<< RANC SWAP OVER GETK ROT SWAP CRYPT + \>>
  DECRYPT @ Encrypted_text  Numeric_key  -->  Plaintext
    \<< OVER 5 OVER SIZE SUB ROT 1 4 SUB ROT SWAP GETK CRYPT \>>
  CRYPT @ String  Numeric_key  -->  XORed_String
    \<< RDZZ \->STR DUP "" 1 ROT SIZE START RAND
        256 * CHR #5193h SYSEVAL NEXT XOR \>> @ Use &$ or +
  HASH  @ String  -->  Numeric_value
    \<< 0 WHILE OVER SIZE REPEAT OVER   2 OVER SIZE SUB @ TAIL
        ROT NUM RDZZ RAND ROT RDZZ RAND * \v/ END SWAP DROP \>> @ SqRoot
  RANC  @ Make a random 4-character string
    \<< RDZ0 "" 1 4 START RAND 256 * CHR + NEXT \>>
  GETK  @ User_numeric_key  Random_characters  -->  New_numeric_key
    \<< HASH SWAP RDZZ RAND * \v/ \>> @ SqRoot
  RDZ0  @ Replaces 0 RDZ (to get 1E12 possible values, rather than 1E6)
    \<< RCWS 64 STWS TICKS 1E12 DUP2 / * - B\->R RDZ STWS \>>
  RDZZ  @ Does RDZ, but ensures a non-zero argument
    \<< DUP NOT { EXP } IFT RDZ \>>
  WIPE  @ Overwrites unused temporary memory
    \<< MEM DROP { #5F61h SYSEVAL #18DBFh SYSEVAL }
        DUP EVAL WHILE OVER EVAL DUP2 > REPEAT SWAP DROP
        RAND DROP END DROP2 DROP \>>
  TEST  @ Each encryption is different; remove me after testing.
    \<< "ABCDEFGH" 12345 ENCRYPT DUP 12345 DECRYPT \>>
END @ End of the directory

------------------------------

Further notes and explanations:

If you prefer a "key_string" to a numeric key, type your string
and press HASH to convert it to a number.

RDZ0 does what 0 RDZ is supposed to do; however, 0 RDZ uses only
20 bits of the TICKS value, which is not enough to be able to
create different 32-bit random values!  Try repeatedly executing
0 RDZ RAND to see how non-random are the last six or so digits
of each result.  The 0 RDZ cycle can repeat every 2 minutes,
while RDZ0 can not repeat any value for several years.

RDZZ is needed to guard against a zero argument to RDZ,
which would then use the timer to randomize a starting value;
we use RDZZ whenever we want to guarantee a *predictable* value
which will be the same again the next time we use the same input.

Pressing TEST repeatedly will encrypt the same text repeatedly, using
the same key, but it will never look the same twice.  The test also
checks to see that each encrypted message can be successfully decrypted.

Why WIPE?  Well, you may know that deleting computer disk files only
deletes their directory entries, but that the file is still on the
disk, and can still be read at the hardware level.  Things recently
typed into memory are likewise still there, even in the HP48;
the DTEMP program from HACK.LIB can "unerase" all the
temporary objects recently used -- perhaps even your
recently-used key(s) and unencrypted file(s)!

To guard against this devious hacking, WIPE does an initial GC,
and then fills up free memory until another GC occurs.  A very
small amount of information in the "slack" space upon GC can still
escape unwiped, but this wiper is about as far as User-RPL can go.
Don't be surprised if WIPE is slow when there are 100K bytes free;
it can only wipe about 2900 bytes per second.

So much for today's "Tales from the Crypt"
(whatever happened to the original TV series)?

-----------------------------------------------------------
With best wishes from:   John H Meyers   <jhmeyers@mum.edu>

