1994-01-20 - New PKS (Warlock)
Header Data
From: charliemerritt@BIX.com
To: cypherpunks@toad.com
Message Hash: bd5d0bac7ecb873df576f757d56b16862c6816cb8afa2627ffc6c99c68c4c45d
Message ID: <9401192108.memo.89152@BIX.com>
Reply To: N/A
UTC Datetime: 1994-01-20 04:24:37 UTC
Raw Date: Wed, 19 Jan 94 20:24:37 PST
Raw message
From: charliemerritt@BIX.com
Date: Wed, 19 Jan 94 20:24:37 PST
To: cypherpunks@toad.com
Subject: New PKS (Warlock)
Message-ID: <9401192108.memo.89152@BIX.com>
MIME-Version: 1.0
Content-Type: text/plain
I got this from PRZ (as in PGP)
[Note: see ripem.msu.edu:/pub/crypt/other for source+binary]
WARLOCK - A New Matrix-based Paradigm for Public Key Cryptography
(C) 1993 by William J. Wilson and C. Larry Craig
1. INTRODUCTION
The following narrative briefly reviews the functionality of
contemporary private key and public key (PK) cryptosystems in
meeting current and future private sector security needs. To
assist in meeting these needs, the WARLOCK paradigm for achieving
matrix-based PK cryptosystems is presented and explained. Sys-
tems based on this paradigm are designed as alternatives to RSA
and RSA-hybrid systems by making available single, high-speed,
full bandwidth systems capable of the basic cryptographic func-
tions of encryption, decryption, and source authentication
(digital signature).
The WARLOCK paradigm is outlined in the following paragraphs
with actual examples of system keys and step-by-step encryption,
decryption, and authentications transformations effected by those
keys.
User evaluations, comments and suggestions are solicited on the
WARLOCK paradigm as well as the particular WARLOCK 4.0 PC imple-
mentation (available in C++ source code from file WARLOCK.CPP and
in MS DOS executable code as WARLOCK.EXE). Please direct such
input to WARLOCK@ACM.org or Datasec Systems, PO Box 4152, Hunts-
ville AL 35815-4152, or by calling Wilson at (205) 881-8002.
User suggestions and improvements will be incorporated, as appro-
priate, and improved versions (as well as other implementations
of the WARLOCK paradigm) will made available to interested users
in the future.
*****************************************************************
WARNING: The WARLOCK cryptosystem provided herein is a copy-
righted system protected by patents (awarded and pending) and is
provided solely for private personal use and evaluation only.
Modifications to (or copies of) WARLOCK source or executable
programs must retain the warning and proprietary legend displayed
on the first user screen.
The use of WARLOCK cryptosystems for private-sector commercial or
public-sector governmental purposes is strictly prohibited with-
out proper licensing arrangements. Licensing information can be
obtained from the above-noted sources.
*****************************************************************
2. BACKGROUND
Today's telecommunications and information system designers
contemplating cryptographic technology are confronted with a
relatively limited set of choices and capabilities (e.g. DES,
RSA, proposed NIST DSS (Digital Signature Standard), etc.) which,
even when combined in hybrid systems, are inadequate in our
opinion to the complex security and authentication needs of the
burgeoning information age and the even more daunting require-
ments of the emerging digital multimedia revolution. For exam-
ple, the NIST DSS and RSA systems suffice for authentication but
are too slow for ordinary encryption/decryption functions forcing
users to employ more complicated hybrid systems resulting in
"double exposure". Hybrid systems typically use the DES standard
which has been widely assailed for its all-too-short key length
(56 bits). Nor has the proposed NIST standard met with a warm
reception either since it presently provides only a time-consum-
ing signature capability. In terms of variety, flexibility,
speed, and selectable and provable levels of security, we feel
that contemporary cryptosystems fall short of efficiently meeting
the wide range of known and predicted private sector application
security needs, e.g. encrypted digital voice and video, digital
satellite communication, ISDN, wireless LAN's, source authentica-
tion, IFF (Interrogate Friend or Foe) protocols, smart cards, and
a host of other emerging applications.
To meet these needs, the authors over the past several years have
developed and tested scores of high-speed matrix-based PK crypto-
systems beginning with a patented private-key version of the Hill
cipher and culminating in the development of the WARLOCK family
of PK cryptosystems. Our goal throughout has been the attainment
of a single, full-bandwidth PK cryptosystem paradigm (with digi-
tal signature) of sufficient simplicity, speed, and selectable
levels of security for meeting current and expected cryptographic
needs of the private sector.
3. THE HILL PARADIGM
In 1929 Lester H. Hill proposed a unique, matrix-based, block
ciphering system (1.) unlike any ever proposed before. Although
manifestly linear and later shown to be susceptible of chosen
plaintext attack, Hill's system represented a quantum leap in the
art of cryptography providing for the first time a true block
ciphering capability with strengths substantially beyond those of
the polyalphabetic systems of his day. If fact, if computing
(but not creating) the inverse of a matrix were as difficult as
computing its permanent, Hill would have invented in a single
stroke the first provably secure public key cryptosystem complete
with digital signature. Notwithstanding, Hill's method, employ-
ing standard matrix transformations, established a new direction
whose full cryptographic potential in our opinion is still
unrealized and one capable of nullifying in large measure the
standard tools of conventional cryptanalysis. Apart from the
issue of cryptographic strength, Hill succeeded in inventing the
first two-key cryptosystem and it remained only for Hellman and
Diffie to establish a rigorous mathematical paradigm (2.) for
one-way, two-key public key cryptosystems and for Rivest et al.
to provide the first viable example of such a system (3.).
In a later development, McEliece developed a matrix-based public
key system (4.) based on Goppa error correction codes. Although
inefficient in terms of bandwidth and initially lacking digital
signature, his system demonstrated that workable matrix-based PK
systems were indeed possible. In spite of the fact that the
McEliece system was recently cryptanalyzed (5.), it nevertheless
represented a significant step in the evolution of matrix-based
cryptosystems.
Still later, Rodney Cooper extended Hill's mod 26 systems to
Galois Fields GF(p) and GF(q^n) to create a cryptosystem based on
matrix theory and Galois Fields (6). In essence, Cooper provided
for a matrix of polynomials (subject to two moduli) to be used as
an encryption key with the paramount advantage that such ma-
trices can be made as large as needed to accommodate any required
level of user security. In fact, Patti (7.) has implemented such
extensible multi-magabit cryptokeys in PC-based extended memory
in which he also concatenates random bits with the plaintext
vector prior to encryption to defeat linear attacks (cited in the
above reference) as well as known-plaintext and chosen-plaintext
attack.
Rather than trying to impress a known NP-hard problem into the
service of PK cryptography as others such as Merkle et al. (8.)
have attempted, we have employed a two-step process instead. In
the first step, we developed weak but workable full-bandwidth PK
systems with digital signature capability. In the second step,
we hardened the resulting system by incorporating artificial com-
plexities in the key generation, encryption, and decryption
processes with the goal of attaining selectable and provable
levels of security -- ideally NP-hard.
Payne and McMillen's formula (9.) defines the number of nonsingu-
lar nxn binary matrices possible for each dimension of n and
thereby the number of reversible linear mappings of n-bit strings
possible with such matrices. It is worth noting that such map-
pings are a tiny subset of the full range of (2**n)! possible
mappings of unique n-bit values. Unfortunately, as Chaitin has
noted in another context (10.), all but a small fraction of these
mappings are essentially noncomputable and can be effected only
by table lookup -- as the small S-box mechanisms of DES exempli-
fy. For the WARLOCK paradigm, one of the required private keys
consists of a large, non-singular nxn matrix used to disguise the
rectangular mxn public key. In the implementation provided here,
a smaller nonsingular nxn private key matrix is also required.
In the paragraphs that follow, the term "matrix" always refers to
a binary matrix and all forms of the term "addition" indicated
by the + symbol designate addition modulo-two (XOR operation).
Supporting figures for the WARLOCK paradigm and the particular
implementation are all found at the end of the paper.
4. THE WARLOCK PARADIGM
Overview
WARLOCK is a paradigm for a family of advanced, high-speed, full-
bandwidth, matrix-based PK cryptosystems with full digital signa-
ture. These systems can be operated in ordinary encryption/de-
cryption mode or in superencrypted mode, (achieving encryption
and authentication simultaneously) as necessary with key and
block sizes incrementally selectable according to security needs.
All implementations of the WARLOCK paradigm share certain common-
alities:
- use of a single public key K consisting of a rectangular
mxn binary matrix where m>n and where n is the system
block size of plaintext and ciphertext
- achievement of nonlinear plaintext to ciphertext mappings
such that for plaintexts A and B under key K, the follow
ing is true: MAP(A,K) + MAP(B,K) <> MAP(A+B).
- incorporation of secret "row identifiers" in rows
of the public key (which are injected in disguised form
into the ciphertext by the encryption process) allowing
a private key holder to identify public key rows
selected by the encryption process.
- use of entropy increasing "noise bits" for selected
bit positions of the public key not occupied by row
identifiers
- use of a secret, nonsingular nxn matrix M to disguise the
public key and to serve (in inverse form) as a private key
- user-selectable key and system block sizes to accommodate
varying levels of security requirements
- system key generation from user-supplied "key-seeds" or
pass phrases of 1 to 85 bytes
As the example below shows, the public key for the implementation
provided here is initially constructed of two parts -- an A-part
and a B-part. The A-part consists of a key-seed generated and
triplicated nxn nonsingular matrix whose n dimension is exactly
1/3 the row dimension of the public key.
Construction of the B-part begins with a template matrix (T-
matrix) containing a diagonal of submatrices each comprised of
"row identifiers" whose value and row positions uniquely identify
each matrix row. In the first hardening step, the area above the
diagonal is filled with key-seed generated "noise bits" and the
area below the diagonal is filled with "replacement bits" con-
sisting of key-seed generated but replicated row values. The A-
part and the B-part are concatenated to form an mxn matrix where
m<n. This matrix is then disguised by being multiplied by a
secret invertible nxn matrix_M whose inverse later serves as a
private key. The result is then jumbled by row groups and
(optionally) rows within row groups to create a single mxn public
key K where m>n and where n is the block size of both the input
plaintext and the resulting ciphertext. The purpose of row group
jumbling is to disguise the original A-part and B-part row group
sequence.
WARLOCK encryption is accomplished by expanding an n-bit plain-
text block in a nonlinear manner to form an m-bit vector which is
multiplied by the public key to create an n-bit ciphertext. This
multiplication is greatly hastened (as are all binary matrix
multiplications) by the simple expedient of associating each bit
position of the expanded vector with a row of K allowing 1-bits
in the expanded plaintext vector to select corresponding rows of
K which are added modulo two to produce the plaintext.
In the first step of the decryption process, the ciphertext is
multiplied by private key M_inverse to create the same value as
if the plaintext had been multiplied by the completed T-matrix.
Rows selected by the encryption process (whose row identifiers
are encoded in the ciphertext) are then retrieved by a deconvolu-
tion process which removes the effects of the noise bits identi-
fied in the private key T-matrix. Accomplishing the inverse of
the row selection process employed during encryption serves to
identify the original plaintext.
Like most computer-based cryptosystems, WARLOCK consists of three
basic modules: a key generation module, an encryption module, and
a decryption module. Digital signatures (as well as superencryp-
tion) are accomplished conventionally by concatenating decryption
and encryption functions employing appropriate public and private
keys.
WARLOCK Key Generation
The WARLOCK T matrix is comprised of two major parts: an A-part
and a B-part. The A-part consists of a triplicated and expanded
nonsingular A matrix as shown in Figures 1. through 3. and the B-
part consists of a set of rows each containing a unique 3-bit row
identifiers as shown in Figure 5. Note that the triplicated rows
of the A part when selected always produce a "fat bit" consisting
of 000 or 111. These "fat bits" when combined with the row
identifiers of the B-part in the encryption process either pre-
serve the row identifier value or complement it with the result
that identifiers are recovered in original or complemented form.
For example, a row identifier 100 in a given ciphertext row
position will be recovered either as 100 or as its complement 011
-- both identifying a particular B-part row selected in the
encryption process. Row identifier values for the B-Part are
chosen as shown below such that their values and their comple-
ments form a unique set of unduplicated values allowing unambigu-
ous row identification.
4-let Row Identifier
Row Identifier Complement
1 100 011
2 010 101
3 001 110
4 111 000
In the encryption process, an information containing fat bit from
the A-part consisting of 000 or 111 is always added to each 3-bit
identifier value selected in the B-part. This technique not only
preserves identification of the B-part row selected, but permits
identification of the value of the information carrying fat bit
as well. In other words, if a row identifier is recovered un-
changed, its fat bit is known to be 000 otherwise its fat bit is
known to be 111. Since the selection of fat bits is also deter-
mined by plaintext values, fat bits are also information carry-
ing.
|----------|
| |
| B-part |
| |
|__________|
| A-Part |
|__________|
WARLOCK T-matrix
The A-part of the WARLOCK T-matrix is created as follows. A key-
seed generated, nonsingular nxn matrix A (whose n dimension is
exactly 1/3 the width of the T-matrix) and its inverse A_inverse
is initially created as shown in Figures 1. and 2. The A-matrix
is then triplicated to create the matrix shown in Fig. 3. As al-
ready noted, triplication of the columns of matrix A produces the
fat bits required by the encryption process. In the next step,
shown in Fig. 4., the matrix row dimension is increased by adding
each row pair of the matrix in Fig. 3. to create a third row. A
fourth all-zero row is then created completing the row expansion.
This last step is necessary to create A-part row groups (4-lets)
that allow the row selection process (governed by plaintext
values) to be identical for both the A-part and the B-part.
Construction of the B-part of the T-matrix begins with an initial
template containing row identifiers as shown in Figure 5. In the
first hardening step, key-seed generated noise bits are added
above the submatrix diagonal to produce the intermediate version
shown in Figure 6. In the next step, the A-part and the B-part
are joined to form a single T-matrix shown in Figure 7. To
eliminate the "sea of zeroes" under the diagonal of the B-part
(and to further disguise the T-matrix), a special "replacement
bit or R-bit" matrix shown in Figure 8. is created with row
values identical for each row 4-let. This matrix is added to the
matrix in Figure 7. to produce the final T-matrix shown in Fig.
9. Not only does this step eliminate the "sea of zeroes" under
the diagonal, but it also displaces and further disguises all
other bits in the T-matrix. If the set of unique replacement row
values in the R-matrix has been initially selected to sum to
zero, the replacement row values vanish in the encryption proc-
ess; otherwise their sum must be removed from the ciphertext as a
special step in the decryption process.
In the penultimate step of key generation, the T-matrix is multi-
plied by the M-matrix in Figure 10. to produce the public key K-
matrix shown in Figure 12. In the final step, this key is then
key-seed jumbled in two ways: in four row groups (4-lets) and
(optionally) by rows within groups. In the example below 4-lets
are jumbled as follows:
From To
4-let 4-let
6 1
4 2
1 3
2 4
3 5
5 6
WARLOCK Encryption Process
The first encryption step consists of expanding the input plain-
text block of n-bits (K-matrix column dimension) to a bit vector
of m-bits (K-matrix row dimension) in accordance with the trans-
lation table below. In the second and final step, this vector is
then multiplied as a column vector by public key K to produce the
ciphertext. Alternatively, the plaintext bit values could simply
select the applicable rows of K directly as mentioned above and
add them together.
Expanded
Plaintext Plaintext
2-bit Seg- Vector
ment Segment
00 0001
01 1000
10 0100
11 0010
WARLOCK Decryption Process
Decryption is a multi-step process. In the first step, the
ciphertext is multiplied by private key M_inverse to produce an
"unmasked version" having the same value as if the expanded
plaintext had been multiplied by the T-matrix.
In the second step, row identifiers of the B-part are recovered
beginning with the leftmost row identifier which is always recov-
ered in undisguised or complementary form (since it has not been
altered by noise bits). The noise bits associated with this
identifier row can now be identified using T-matrix private key
information and removed from the ciphertext revealing the next
leftmost row identifier in the same manner. This process is
repeated iteratively until all row identifiers have been identi-
fied -- in their original or complemented form. Each identifier
value, thus recovered, unequivocally identifies an applicable 4-
bit sector of the invoking expanded plaintext vector which, in
turn, identifies a 2-bit sector of the plaintext. In addition,
each recovered row identifier identifies its associated fat bit
value as 000 or 111.
When all row identifiers have been recovered, 2/3 of the plain-
text has been decrypted. The remaining 1/3 can now be decrypted
by examining fat bit values derived from the recovered identifier
values themselves, i.e. for unchanged row identifiers, the ap-
plicable fat bit = 000; otherwise the applicable fat bit = 111.
When all fat bits have been identified, they are reduced from 3
bits to 1 bit and concatenated to form a value which is multi-
plied by private key A_inverse (in Fig. 2.) to recover the re-
maining 1/3 of the plaintext.
In the final step of decryption, the full set of 2-bit plaintext
segments are unjumbled to reverse the effects of the row 4-let
jumbling of the public key.
7. WARLOCK 4.0 MANUAL EXAMPLE
As an example of WARLOCK 4.0 operation, the WARLOCK 4.0 crypto-
graphic keys shown in Figures 6., 11., and 12. may be used to
manually encrypt and decrypt 12-bit inputs and to create and
verify 12-bit digital signatures as desired.
For example, to encrypt plain_text P = 001110000110 using pub-
lic_key_K shown in Figure 12., accomplish the following steps:
Expand plain_text P to expanded_text 000100100100000110000100.
Select and add rows of public_key_K under control of 1-bits in
expanded_text to produce encrypted_text as follows:
bit 4 selects row 4 of K = 101000100001
bit 7 selects row 7 of K = 011110010011
bit 10 selects row 10 of K = 110011110001
bit 16 selects row 16 of K = 011000001000
bit 17 selects row 17 of K = 000010100101
bit 22 selects row 22 of K = 001001110001
encrypted_text = 010110011111
To facilitate understanding of the more complex decryption proce-
dure detailed below, the following reference table is provided
which relates row identifier values (as recovered) to the follow-
ing necessary information: (1) row position selected within each
row 4-let (2) selecting 2-bit plaintext values and (3) applicable
fat bit values.
Row
Row Identi- Selected Selecting Associated
fier Value within Plaintext Fat Bit
(as recovered 4-let Value Value
100 1 01 000
011 1 01 111
010 2 10 000
101 2 10 111
001 3 11 000
110 3 11 111
000 4 00 000
111 4 00 111
The following steps detail the decryption process:
A. Multiply encrypted_text 010110011111 by private key
key_M_inverse shown in Figure 11. to create the initial value of
reverted_text 100101101111. Note that the leftmost row identifier
in bit positions 1, 5, and 9 is unaffected by noise bits and is
seen to have the value 101 indicating that row 2 of the applica-
ble 4-let of the public key was chosen. Accordingly,
1. Initialize the value of resultant_text with the first 2
recovered plaintext bit values, e.g. resultant_text 10.
2. Create the first iteration of intermediate_text by remov-
ing from reverted_text the noise bits associated with row 2 of
private key key_T_with_noise by XORing subject row 2 with the
reverted_text to produce the first intermediate_text value as
follows:
100101101111 (reverted_text)
011010010000 (row 2 template and noise bit values)
111111111111 (intermediate_text)
This step also records the fat bits in positions 1, 5, and 9. of
the intermediate_text and the reduced fat bit in position 1.
B. Note that the value of the row identifier in bits 2, 6, and 10
"uncovered" by the previous step is seen to be 111 indicating
that row position 4 of its respective 4-let was selected and
further indicating an invoking plaintext value of 00 and an
associated fat bit value of 000. Accordingly,
1. Append recovered plaintext bits 00 to the current result-
ant_text value giving new resultant_text 1000.
2. Remove from the current intermediate_text value the noise
bits associated with applicable row 4 of key_T_with_noise_bits by
XORing subject row 4 with intermediate_text to produce a new
intermediate_text value as follows:
111111111111 (current intermediate_text)
010101110110 (row 4 template and noise bit values)
101010001001 (new intermediate_text)
This step also records the reduced fat bits in positions 1 and 2
of the new intermediate_text.
C. The value of the third row identifier (bits 3, 7, and 11)
uncovered by the previous step is seen to be 100 indicating that
row 1 of its respective 4-let was invoked by a plaintext value of
01 and that its associated fat bit value is 000. Accordingly,
1. Append the recovered plaintext bits 01 to the current re-
sultant_text value giving 10000.
2. Remove from the intermediate_text the noise bits associ-
ated with row position 1 of private key key_T_with_noise_bits by
XORing subject row 1 with the current intermediate_text to pro-
duce a new intermediate_text value as follows:
101010001001 (current intermediate_text)
001000000000 (row 1 template and noise bit values)
100010001001 (new intermediate_text)
This step also records the reduced fat bits in positions 1, 2,
and 3 of the new intermediate_text.
D. The fourth and final row identifier (bit positions 4, 8, and
12) uncovered by the previous step is seen to be 001 indicating
that row 3 was selected by a plaintext value of 11 and that its
associated fat bit value is 000. Accordingly,
1. Append recovered plaintext bits 11 to current
resultant_text value giving 10000111.
2. Remove from the current intermediate_text value the noise
bits associated with row position 3 of the subject 4-let of
key_T_with_noise_bits by XORing row 3 with the current intermedi-
ate_text to produce a new intermediate_text_value as follows:
100010001001 (current intermediate_text)
000000000001 (row 3 template value)
100010001000 (new intermediate_text)
This step also records the final reduced fat bit in position 4 of
the new intermediate_text whose current value is now seen to be
1000.
D. This completed intermediate_text value 1000 will be multiplied
by private key A_inverse to recover the final plaintext values
(originally encoded by the A-part of the public key) as follows:
1000 x A_inverse = 1000
The recovered plaintext value 1000 is then appended to the cur-
rent value of resultant_text to produce resultant_text =
100001111000.
J. The completed resultant_text value 100001111000 (now seen to
be a 2-bit permutation of the original plaintext) must now be
unjumbled in the final decryption step by reversing the row
jumbling accomplished in the last step of the key generation
process (described on page 7.) as follows:
Source Bit Desti- Destination
Source Pair Position nation Bit Pair Position
Bit Pair (resultant_ Bit Pair (decrypted_
Number text)/(value) Number text)/(value)
6 11-12 (00) 1 1-2 (00)
4 7-8 (11) 2 3-4 (11)
1 1-2 (10) 3 5-6 (10)
3 3-4 (00) 4 7-8 (00)
2 5-6 (01) 5 9-10 (01)
5 9-10 (10) 6 11-12 (10)
This final permutation step produces the sought plaintext value
001110000110 completing the decryption process.
Source Authentication and Superencryption
To create a source authentication value S (for source authentica-
tion purposes) represented by any selected 12-bit value, S must
first be "decrypted" by the decryption module by the steps noted
in the foregoing paragraphs to create signature value S*. When
submitted to the encryption module for validation, S* produces
the sought value S thereby proving unequivocally that S emanated
from the private key holder.
Because of the relatively high encryption and decryption speeds
of WARLOCK 4.0, Alice and Bob may choose for purposes of enhanced
security to exchange messages that are simultaneously encrypted
and authenticated. To accomplish this, Alice and Bob first obtain
each others public keys. In encrypting messages for Bob, Alice
accomplishes the following:
1. Alice first "decrypts" each plaintext block using her
private key to create an "authenticated version"
of the plaintext. She then encrypts this version
by Bob's public key to create a final ciphertext block
which she transmits to Bob.
2. Bob first decrypts the ciphertext block by his private
key recovering the "authenticated version". He then
transforms this version to Alice's original plaintext
by "encrypting" it with Alice's public key thus proving
Alice to be the originator of the plaintext since she
is the only holder of the private key.
In encrypting messages for Alice, Bob follows the same procedure
with the appropriate public and private keys.
8. SEEDING THE WARLOCK KEY GENERATION FUNCTION
A basic desideratum of classic private key cryptosystems was
easily generated and memorized keys to avoid a possibly compro-
mising (or incriminating) recording of the key. This desideratum
has all but vanished with DES and the advent of PK systems. Who,
for example, can remember a thousand-bit RSA modulus or its
constituent primes. Nevertheless, there are many occasions where
one would not wish to transport private keys to a new operating
locations, but regenerate them at their new location, use them,
and destroy them. Such a capability is available through the
unique WARLOCK key seeding feature which allows users to seed the
key generation process with a user secret key-seed (or pass
phrase) of 1 to 85 bytes (8 to 680 bits). Such a feature is
typically absent from number theoretic cryptosystems such as RSA
and the NIST DSS. With the WARLOCK key seeding feature, users
can establish simple mnemonic seeding tokens or create elaborate-
ly structured key-seeds as needed.
Key seeding also facilitates the use of WARLOCK as a stream
cipher where Bob and Alice at different locations independently
generate a common private key based on a secret shared key-seed.
Such a procedure allows then to generate and synchronize a common
pseudorandom bit stream beginning with an agreed-on starting
value v which is "decrypted" by the private key and the result
XORed with plaintext to encrypt and decrypt in the manner of one-
time pads or Vernam ciphers. The starting value v would then be
incremented by +1 each iteration yielding a nonrepeating cycle of
2**n iterations where n is the system block size in bits.
Key seeding also facilitates opportunistic encryption using
devices such as PC's and workstations that are generally avail-
able but not portable. For example, Bob could freely transport
the encryption/decryption program on a 3 1/2" floppy in his shirt
pocket without fear of compromising his secret key-seed. Alice
could encrypt from any available PC initialized with an installed
WARLOCK program. Both would enter their secret key-seed at the
time of message exchange.
As yet another example of the potential of key seeding, consider
an environment where Bob and Alice are deployed as secret agents
who must unequivocally authenticate each other's identity prior
to commencing their mission. Each has memorized a key-seed given
them by their faceless directors and each carries an unknown
ciphertext segment as well. When they finally rendezvous in
Vienna, Bob and Alice XOR the ASCII representation of their key-
seeds to produce a new key-seed value which they use to generate
cryptographic keys. Each then decrypts his ciphertext segment
with the newly-generated keys. Bob hands his decrypted message
to Alice who reads, "Of course, you know my name isn't Bob at
all, it's Travis and I am pleased to meet you at last, Tatiana
AKA Alice."
9. WARLOCK CRYPTOGRAPHIC STRENGTH
It would be presumptuous at this point to assert that WARLOCK is
categorically unassailable -- particularly in light of the vast
resources of linear algebraic techniques (most of which are
unknown to the authors) that might be mustered for its cryptanal-
ysis. The rise and fall of numerous PK cryptosystems proposed
during the last decade certainly recommend caution as well.
However, based on our experience to date in making and breaking
scores of matrix-based PK cryptosystems, it is our feeling that
the only potentially effective assault possible against WARLOCK
is the derivation of private keys (or workable alternatives) from
the public key (assuming that the keys are sufficiently large to
preclude other attacks). Clearly, the keys themselves cannot be
exhaustively enumerated owing to their size. Simmons generalized
PK system attack (11.) can be precluded in several ways. Users
may choose to operate in superencrypted mode which accomplishes
encryption and source authentication simultaneously or they may
choose a suitably large system block size. Various kinds of pre-
encryption scrambling (to increase input entropy) and post-de-
cryption unscrambling may also be employed.
Thus far we have been unable to cryptanalyze WARLOCK 4.0 with
techniques successful against ancestors of WARLOCK. Under all
the attacks that we have been able to muster, the work factor
required to cryptanalyze WARLOCK 4.0 is an exponential function
of block size which can be made arbitrarily large. What we are
seeking from the user community is an assessment of the viability
of the WARLOCK paradigm as well as a more precise quantification
of the work factor required to cryptanalyze WARLOCK 4.0.
10. CONCLUSION
Apart from the undecided issue of security, the WARLOCK paradigm
meets our objective of providing users with single high-speed
general purpose PK cryptosystems (exemplified by WARLOCK 4.0) as
alternatives to number theoretic systems. We feel that WARLOCK
cryptosystems can serve the security needs of private users to
whom we grant free use subject to the restrictions noted in the
source code and in the introduction to this paper. The WARLOCK
paradigm also suggests a new direction for the development of PK
systems free of the computational burden of number theoretic
systems. Finally, the WARLOCK paradigm suggests a potentially
fruitful direction for achieving a viable cryptographic embodi-
ment of the NP-hard coding problem cited by Berlekamp et
al.(12.).
11. WARLOCK 4.0 NUMBERED FIGURES
Note: To facilitate de-
1000 1000 101010101010 cryption, Row 1. is row 2
1010 0110 100010001000 of Matrix A triplica-
1110 1100 001000100010 ted. Row 2 is row 1
0011 1101 000000000000 triplicated; row 3 is
001100110011 the XOR of rows 1 and
Figure 1. Figure 2. 111011101110 2 and row 4 is the
A-Part Private Key 110111011101 XOR of rows 1, 2, and
Matrix A Matrix A_ 000000000000 3. The same process
inverse using remaining row
Figure 3. pairs of Matrix A is re-
A-expanded peated to create A_expan-
ded.
100000000000 100010101101 101101000011
010000000000 010100100010 011010010000
001000000000 001011001000 000001001110
111000000000 111111001001 110011001111
000100000000 000100101011 011000010011
000010000000 000010111111 001101110011
000001000000 000001111100 001100100110
000111000000 000111011110 010101110110
000000100000 000000100000 001000000000
000000010000 000000010001 000000100001
000000001000 000000001001 000000000011
000000111000 000000111000 001000100010
000000000100 000000000100 000100000000
000000000011 000000000010 000000010000
000000000001 000000000001 000000000001
000000000111 000000000111 000100010001
Figure 4. Figure 5. Figure 6.
B-Part B-Part B-Part
Initial key_T_temp- Columnar re-
key_T_temp- late with arrangement
late noise bits = key_T_with_
noise_bits
110000001000 101001010100
000110100011 100100111100
100000100001 010001110011
110101011011 000001101100
111010111100 001111001000
110101000010 110010110100
001000111100 110110001110
100100010001 111111110010
011000000100 101101101000
100001111010 110101000111
000000010010 111111110000
010111011110 010111011010
.OJ OFF
Figure 7. Figure 8.
key_M Private Key
key_M_inverse
101101000011 110100100010 011001100001
011010010000 110100100010 101110110010
000001001110 110100100010 110101101100
110011001111 110100100010 000111101101
011000010011 001101010001 010101000010
001101110011 001101010001 000000100010
001100100110 001101010001 000001110111
010101110110 001101010001 011000100111
001000000000 010011011011 011011011011
000000100001 010011011011 010011111010
000000000011 010011011011 010011011000
001000100010 010011011011 011011111001
000100000000 101100110010 101000110010
000000010000 101100110010 101100100010
000000000001 101100110010 101100110011
000100010001 101100110010 101000100011
101010101010 011111101001 110101000011
100010001000 011111101001 111101100001
001000100010 011111101001 010111001011
000000000000 011111101001 011111101001
001100110011 011001110011 010101000000
111011101110 011001110011 100010011101
110111011101 011001110011 101110101110
000000000000 011001110011 011001110011
Figure 9. Figure 10. Figure 11.
key_T_with_ replacement_ key_T_replaced
noise (A rows (Figure 9.
and B-Part XOR'd with Fi-
joined) gure 10.)
11. BIOGRAPHICAL DATA
William J. Wilson is an early-retiree of the Sperry half of the
current UNISYS corporation. During his 23 years there, he spe-
cialized in database design, information storage and retrieval,
and system security. He is a member of ACM occasionally consult-
ing in his areas of expertise and is also identified in the
current Directory of American Fiction Writers and Poets as both a
writer (science fiction and horror) and a poet. His light and
satirical verse appeared frequently in DATAMATION (Churl's Garden
of Verses, Solid-state Jabberwocky, Ode to the Indomitable GOTO,
etc.) and other magazines.
C. Larry Craig (co-inventor of WARLOCK and author of the C++
WARLOCK program) currently works as a private consultant and
software designer in the fields of digital communication, commu-
nication networks, and cellular and telephony applications.
12. REFERENCES
1. Hill, L. "Cryptography in an Algebraic Alphabet," Amer.
Math. Monthly. 36: 306-312, 1929.
2. Diffie, W., and Hellman, M.E. "New Directions in Cryptog-
raphy," IEEE Trans. Inform. Theory IT-22, 644-654, Nov. 1976.
3. Rivest, R. et al., A Method for Obtaining Digital Signa-
tures and Public-key Cryptosystems, Communications of the ACM 21,
pp. 120-126, Feb 1978.
4. McEleice, R.J. "A Public-key cryptosystem based on Alge-
braic Coding Theory," DSN Progress Rep. 42-44, Jet Propulsion
Laboratory, pp. 114-116, 1978.
5. Korzhik, V.L. and Turkin, A.I., "Cryptanalysis of McE-
liece's Public-key Cryptosystem," Advances in Cryptology - Euro-
crypt '91 Proceedings.
6. Cooper, R. "Linear Transformations in Galois Fields and
Their Application to Cryptography," Cryptologia, Vol 4., No. 3,
pp. 184-188, 1992.
7. Patti, T. "The SUMMIT Cryptosystem," Cryptosystems Jour-
na, Vol 2., No. 2, 1992.
8. Merkle, C. and Hellman, M.E. "Hiding Information and
Signatures in Trapdoor Knapsacks," IEEE Trans. Inform. Theory.IT-
24: pp. 525-530, 1978.
9. Payne, W.H. and McMillan, K.L., Orderly Enumeration of
Nonsingular Binary Matrices Applied to Text Encryption, Communi-
cations of the ACM, pp. 259-265, April 1978.
10. Chaitin, G. J. ""Randomness and Mathematical Proof,"
Scientific American pp. 47-52, May 1975.
11. Simmons, G.J., Forward Search as a Cryptanalytic Tool
Against a Public Key Privacy Channel, Proceedings of the IEEE
Symposium on Security and Privacy, April 1982.
12. Berlecamp, E.R., McEleice, R.J., and van Tilborg, H.C.A.,
On the Inherent Intractability of Certain Coding Problems, IEEE
Trans. Inform. Theory, IT-24, pp. 384-386, May 1978.
Thread
Return to January 1994
Return to “charliemerritt@BIX.com”
1994-01-20 (Wed, 19 Jan 94 20:24:37 PST) - New PKS (Warlock) - charliemerritt@BIX.com