Simple encryption on HP48
John H Meyers
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 <jhme...@mum.edu>
Stainless Steel Rat
-----BEGIN PGP SIGNED MESSAGE-----
>>>>> "JHM" == John H Meyers <jhme...@miu.edu> writes:
JHM> The program CODER on Goodies Disk #5 does simple "encryption"
JHM> by XORing the "plaintext" string with a repeated "key" string.
JHM> How well does this "scramble" the original message?
Not at all. It takes less than 10 minutes to crack a message "encrypted"
using an XOR algorithm. "Applied Cryptography" is a great book. :)
[...]
JHM> A small improvement upon the method of XORing with a key is to
JHM> generate a "random" stream of bytes from the key, and to make sure
JHM> that this stream of bytes, which we will XOR with the original
JHM> plaintext, does not ever repeat!
Also known as a One Time Pad cypher. As long as the stream of random data
is truely random it will work. If it is not -- and computers are
notoriously bad random number generators -- the encoding cannot be
considered secure.
Just a general FYI, the primary difference between a cypher (code) and
encryption is that there is a 1:1 correspondence between plaintext and
cyphertext whereas there is no such correspondence between plaintext and
encrypted text. This is the potential weakness in OTP; if the stream is
not truely random then a pattern can be found and the code broken. OTP is
nothing more than a code with a keylength identical to the message in
question.
So, while this code is probably more secure than a "generic" XOR with a
fixed-length key, it is only marginally more secure as far as a
professional cryptanalyst is concerned. The numbers are not truely random
and XOR algorithms are weak to begin with.
Caveat emptor.
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv
iQCVAwUBM2EcUZ6VRH7BJMxHAQHGUwQAxO3XAJg4GIjGoXHAlkZumytb7eePfe3d
SxMTSMPEmiNPHxKxwPkAugu+YNACeckc0zvSTD+6YNW0nxXoqao0cymSA5/G9h+r
SywxQkqiVl4UtOVH5v55tFxaZ107PruQ8O/DDYEQKXMkTe+uBXekD5z/5iag43IH
HN2mnAGmOXY=
=pBKy
-----END PGP SIGNATURE-----
--
Rat <rat...@peorth.gweep.net> \ Happy Fun Ball contains a liquid core,
PGP Key: at a key server near you! \ which, if exposed due to rupture, should
\ not be touched, inhaled, or looked at.
Jonathan M. Katz
In article <5k04ah$365$1...@news.iastate.edu> jhme...@miu.edu (John H Meyers) writes:
>From: jhme...@miu.edu (John H Meyers)
>Subject: Re: Simple encryption on HP48
>Date: 27 Apr 1997 18:01:53 GMT
> Just as an aside, note that Bruce Schneier (Crypto authority,
> President of Counterpane Systems, and author of crypto-bible
> "Applied Cryptography"), never bothers to "PGP sign" his own posts;
> consider the number of times you have needed to verify a post sig,
> and see whether all that bandwidth is doing anything productive
> (bring back those cute sig pictures instead, if you ask me :)
I'm a newbie to newsgroups, and I'd like to know how to "PGP sign" my own
postings (if this is possible) and check the PGP signatures of others. If
anyone on this group could point me in the right direction for info, I'd
appreciate it. Since my software may limit my ability to use/check PGP's, I'll
list what I use here:
* Netscape v. 3.0 for Windows 3.1
* Trumpet News Reader v. 1.0 Rev. A
* Eudora v. 2.1.1 (this is not "Eudora Light")
Thanks in advance to those of you who can help or will try.
==JMK==
John H Meyers
In article <wkafmmh...@peorth.gweep.net>
(25 Apr 1997 17:04:20 -0400),
rat...@peorth.gweep.net (Stainless Steel Rat?) squeaked:
> ...BEGIN PGP SIGNED MESSAGE...
Just as an aside, note that Bruce Schneier (Crypto authority,
President of Counterpane Systems, and author of crypto-bible
"Applied Cryptography"), never bothers to "PGP sign" his own posts;
consider the number of times you have needed to verify a post sig,
and see whether all that bandwidth is doing anything productive
(bring back those cute sig pictures instead, if you ask me :)
> computers are notoriously bad random number generators
The algorithm's the thing, not the computer per se.
"Random noise" is sometimes not random; what's this world coming to?
> It takes less than 10 minutes to crack a message "encrypted"
> using an XOR algorithm.
I'm impressed that this could be calculated without considering the
number of independent bits which initialize the RNG, the number of
effective bits in its internal state, its cryptographic strength, the
speed and memory of the platform on which the attempt will be made,
the length of the message, amount of guessable "known plaintext" etc.
An obvious exception is the true "one time pad" (OTP), which is a
genuinely random bit stream having as many completely independent bits
as the length of the plaintext, and is never re-used; this is both
"an XOR algorithm" and also undisputedly absolutely unbreakable,
since for every possible plaintext of the given length, there exists
an OTP stream which could have been the one used to encrypt,
and which is as equally likely as any other OTP stream.
A random number generator (RNG) based stream differs from an OTP
in that it has a fixed number of initial state bits (S), possibly
different from the message length (M); if S > M, then it's still
an OTP as far as that one message is concerned; when S < M
(and it needn't be much less), the number of possible initial states
which produce intelligible plaintext from ciphertext becomes reduced
quickly to one, and it is this which provides the ability to find
the unique decryption in principle, and even the ability to use a
modest amount of ciphertext to do it. However, all of the above
factors influence how much work it will take in the first place
to model the particular generator to begin with, and having done
that on some particular hardware/software platform, how long it
might take to accomplish the task at that level of computing power.
Even if you merely double-encrypt (with the random IV of course),
the result, while still being equivalent to one single XOR,
is harder to deal with than before, particularly if you
introduce a little "weird perturbation" into just one of these,
such as replacing RAND with .7 ^ RDZ RAND, etc.
Compress and encrypt (first remove the give-away "BZ"), etc.
If you want to demonstrate that "10 minute" claim, however, I'll
be glad to send you any desired amount of ciphertext (HP48 memory
permitting) and look forward to your posting the plaintext shortly
afterwards; however, I'll even give you one year to do it on your
HP48, in order to claim your reward of all the Stainless Steel Cheese
(chedinox or whatever) you can eat :)
A mere 40-bit keyspace is considered so "easy" to crack that the
U.S. government seems to have no worry about it, but on the HP48,
if we try to "brute force" (try all keys) at the rate of 1000
per second (much faster than actually possible), 2^40_ms converts
to about 35 years, so the HP48 doesn't seem a likely platform
on which this feat may be accomplished. On my Sharp Wizard,
the seven characters (from a limited character set) that I can use
for a password would seem to be child's play for such an attack
on the level of NSA's supercomputers, were it not for the fact that
the only way to enter the password is the physical pressing of keys :)
"Stupid" (easily guessed) keys can of course reduce this,
as they can for any system whatsoever.
> So, while this code is probably more secure than a
> "generic" XOR with a fixed-length key...
Much more.
> ...it is only marginally more secure as far as a
> professional cryptanalyst is concerned. The numbers are
> not truly random and XOR algorithms are weak to begin with.
John Savard recently wrote a Pretty Good Post (PGP? :) on this
whole issue (with other points not mentioned here) on 1997/04/23
in newsgoup sci.crypt; it was titled "Re: Innocent question:
why isn't a pseudo-random stream-cipher sufficient?" and has
Message-Id: <news:335e18a...@nntp.netcruiser>. It will also be
around long after news server expiry, on <http://www.dejanews.com>.
Weakness is relative. You might point out that if you can guess
about ten consecutive "known plaintext" characters (using just
our plain HP48 RNG directly), that's generally more than enough to
nail down the one and only point in its entire cycle where the
necessary sequence of XOR bytes could have been generated by this
particular RNG, and then all the rest are decipherable from there.
However, the uniqueness of that point is not the same as finding
that point. Your PGP public key p*q can be factored in only one
way, so disclosing your public key absolutely determines and
thus practically gives away your private key, no? (don't reply :)
Try this: I have seeded my HP48 LCRNG using a 10-digit integer
(I'll even tell you that I chose a permutation of all 10 digits
-- now it's 3000 times easier for you to guess!).
Here are the first six digits following the decimal point of the
next 12 consecutive RAND results: 766412, 058106, 883759, 654440,
518061, 713659, 248659, 608019, 880320, 198603, 835851, 648073.
That's certainly enough information to vastly over-determine
the unique state of the HP48 RNG, so now tell me its next output.
Everything is relative, and needs to be considered in its context;
if we keep a household safe at home, it is hardly as secure as a
bank vault, but if what we keep in it is suited to the level of
security it provides, it will be convenient, security-effective
and cost-effective -- and it will also better fit in our house.
500 bytes of programming for securing short texts somewhat well
from prying schoolmates/kids/parents in a calculator is okay, I think,
but I will be very happy to see any really clever and worthy method
surpass this "bang for buck (prog bytes)" ratio on the HP48
(maybe just replace this RNG with a more cryptographically
secure one, perhaps in ML for decent speed). Keep the "IV"
(randomized initializer); it does a lot of good.
I think it would be fabulously more fun for HP48 fans
(and proportionally more strain on poor Richard Nelson :) for any
1997 HP48 Programming Contest to somehow involve a "wide open field"
for, say, the "best" security programs; perhaps a few divisions
from "bantamweight" (Simone?) to "heavyweight" (SteveV?) would
be in order; we could easily fill the newsgroup with a year's
supply of discussion afterwards, and a whole new generation of
future NSA cryptanalysts (insert your own country's organization)
might be born from this flurry of interest, and keep each other
employed for many a year :)
"May the best RAN win!"