1993-06-30 - WARLOCK 4.0 Info

Header Data

From: “Kent Hastings” <kent_hastings@qmail2.aero.org>
To: cypherpunks@toad.com
Message Hash: 878122e6c367f67f5e30ca8c39487a5f16c2f524fccc78d14fcb601b0a8c0a9a
Message ID: <199306301621.AA23444@aerospace.aero.org>
Reply To: N/A
UTC Datetime: 1993-06-30 16:24:29 UTC
Raw Date: Wed, 30 Jun 93 09:24:29 PDT

Raw message

From: "Kent Hastings" <kent_hastings@qmail2.aero.org>
Date: Wed, 30 Jun 93 09:24:29 PDT
To: cypherpunks@toad.com
Subject: WARLOCK 4.0 Info
Message-ID: <199306301621.AA23444@aerospace.aero.org>
MIME-Version: 1.0
Content-Type: x-text


                      WARLOCK 4.0 Info
The enclosed file is the documentation for WARLOCK 4.0, 
"A New Matrix-based Paradigm for Public Key Cryptography."

The source code and executeable MS-DOS program are included
in the shareware version, but my internet gateway complains
"permission denied" if I try to send out the ZIP file.

Hmm. The text file is about 43k and the ZIP is only 78k.

Oh well. This is the first I've heard of WARLOCK. "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'."

"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, etc ..." For more info, contact WARLOCK@ACM.org.

Kent - kent_hastings@qmail2.aero.org. 



<<<<<< Attached TEXT file follows >>>>>>
.OJ OFF

.UL ON



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.



#000#





Thread