JADE-S, a block cipher with authentication (integrity check) based on use of permutation polynomials mod 2**n

JADE-S is a successor of JADE. It employs the same PRN generation scheme as JADE but implements a novel idea of block encryption processing which is inspired by the iterative solution of systems of linear equations and is presented by me recently in a few Internet forums. For comments and critiques I should be very grateful.

M. K. Shen

----------------------------------------------------------------------- # JADE-S, a block cipher with authentication (integrity check) based on the use # of permutation polynomials mod 2**n

# JADE-S is a block encryption scheme for securing the privacy of communications # of the common people via encrypting text messages (with automatically # performed authentication (integrity check)) sent over the Internet. Its novel # design includes as a major component a sophistically designed pseudo-random # number (PRN) generation scheme, involving a pool of constituent PRN generators # (PRNGs) based on permutation polynomials mod 2**n that are pseudo-randomly # activated (by themselves) with runtime dynamic renewal. Block lengths ranging # from 128 to 1024 bits can be chosen by the user. Blocks of n bits are treated # as n-bit integers with certain arithmetic operations being directly performed # upon them. The PRNGs in the pool serve further the purpose of pseudo-random # substitution (in the crypto sense) operations, since permutation polynomials # can be employed for bijective mappings. Particular attention is paid to very # thoroughly mixing together the entire set of blocks that constitute the # user-given messages during encryption processing, thus resulting in superior # avalanche effects. The very good readability of its open-source code enables # the user to easily ensure the correctness of the code and that there can be no # backdoors as could otherwise potentially be the case where commercial # proprietary (blackbox) encryption software are employed. Speed competition # with commercial software in processing huge volumes of materials, e.g. # graphics files, is intentionally excluded from the design goals of JADE-S. On # the other hand, extreme prudence is taken to ensure that the code is # practically absolutely immune to all known attacks against block ciphers # owing to the fact that their underlying assumptions simply don't hold for # JADE-S from the very beginning. (JADE-S presumably will be secure as well in # the forthcoming so-called post-quantum era.) Despite the trade-offs hereby # forcefully being taken, JADE-S's processing efficiency, as benchmarking # clearly shows, is nonetheless entirely acceptable for its targeted users (see # result of running Ex. 2 in Sec.2, and Sec.3).

# JADE-S is a successor of JADE (latest Version 2.0.3 available from #

It employs the same PRN # generation scheme as JADE but implements a novel idea of block encryption # processing which is taken from the iterative method of solutions of systems of # equations in linear algegra and which is recently posted to a number of Usenet # groups by the present author. A breif description of the major design features # of JADE-S is as follows: # # 1. With the user-given key we build up in a bootstrap way from a PRNG based on # permutaton polynomial mod 2**n through an intermediate pool, i.e. a large # number, of PRNGs of the same kind to a final pool of such PRNGs. The # outputs of the final pool of PRNGs (which are pseudo-randomly chosen to be # activated by their own outputs) are post-processed through appropriate # summation and buffering such that the statistical qualities of the PRNs # ultimately being delivered are greatly improved and any attacks of the # analysts are rendered infeasible in practice. # # 2. Denoting the blocks of plainatext by x1, x2, ... xk, we perform the # following assignments sequentially for encryption processing: # x1 := f1(x1 + x2 ... + xk ^ r1) # x2 := f2(x1 + x2 ... + xk ^ r2) # ................ # xk := fk(x1 + x2 ... + xk ^ rk) # where the f's are the permutation polynomials pseudo-randomly chosen from # those available in the final PRNG pool and the r's are PRNs generated by # the PRNG pool (see 1. above). Note that the f's are non-linear and that, # in obtaining the individual ciphertext blocks (the x's on the leftside of # the assignments) all blocks of the given message (some already processed, # some not yet) are directly involved, which clearly leads to a superior # avalanche effect. Compare however block-chaining that is commonly used in # running the other known block ciphers. (Note that sequential processing # means that e.g. in the 2nd assignment above x1 on the right-hand side has # already its new value obtained from the 1st assignment.) # # 3. For the purpose of authentication, we append a pseudo-random block to the # beginning of the given plaintext blocks such that it now takes the position # of x1 in the processing scheme sketched above. It is easily seen that x1 # has strong influences on the results of all the other assignments. This # implies, conversely, that any manipulation of the ciphertext blocks will # with very high probability be reflected in the changed value of x1 (with # respect to the one on encryption) obtained on decryption, which means that # x1 can serve well as a MAC for authentication. (JADE-S actually employs, # as an enhancement, also an additional pseudo-random block at the end of the # given plaintext blocks for authentication and the user may further specify # that more than one such authentication blocks be used.)

# Contents of this document:

# Section 1: Python

Python 3.x) code of JADE-S with # comments explaining the functionality of each function as well as the # structuring of the entire program. Permissible values of system parameters # and key materials are listed at the beginning of this section. Users with some # programming experience and basic knowledge of Python should be able to read # this section and understand how JADE-S exactly works without difficulties.

# Section 2: Some examples demonstrating how JADE-S can be actually used for # encryption/decryption as well as how Maurer's Universal Test can be done for # getting informations on the statistical quality of the results obtained.

# Section 3: Miscellaneous notes.

# Version 1.0, released on 24.06.2013. Comment lines last updated on

29.06.2013.

# Code lines of documents with the same version number are always identical. # The most recent document of JADE-S can be obtained from #

# This software may be freely used:

# 1. for all personal purposes unconditionally and

# 2. for all other purposes under the condition that its name, version number # and authorship are explicitly mentioned and that the author is informed of # all eventual code modifications done.

# The author is indebted to TPS for review and suggestions throughout JADE-S's # development phase. Any remaining deficiencies of the software are however the # sole responsibilty of the author.

# Concrete comments and constructive critiques are sincerely solicited either # via the above thread or directly via email.

# Email address of the author: snipped-for-privacy@t-online.de

################################################################################ ################################################################################

######### Section 1. Python Code of JADE-S.

##### This section lists all functions defined in JADE-S. For each run of JADE-S ##### the user has to provide the appropriate system parameters and key ##### materials and invoke initjades(). See Sec.2 for examples.

# Permissible values of system parameters and key materials (limits chosen # based on practical considerations) are as follows (the first 5 parameters # of the list and ciphertextfilemode are essential, the rest could be more # or less arbitrarily chosen, their variability has albeit the beneficial side # effect of enhancing the the complexity facing the analyst):

# logn: log base 2 of the number of bits (n) in a block. # 7 =maxprngusecount: renewal() prngusecount[index]=1 else: prngusecount[index]+=1 prn=prngseed[index]\ =evalpermpoly(prngpool[index],prngm,prngseed[index]) prngsum=(prngsum+prn)&tpwnm1 bf1=buffer1[buf1pt] buffer1[buf1pt]=prngsum buf1sum=(buf1sum+bf1)&tpwnm1 bf2=buffer2[buf2pt] buffer2[buf2pt]=buf1sum random+=[bf2] return(random)

##### The user has to initialize the system with initjades() for each run of ##### JADE-S.

# Check the user-given system parameters for conformance to constraints given # further above and compute the corresponding values of all system variables # required for running JADE-S.

def initjades(): global logn,n,np1,nm1,nh,chnum global tpwn,tpwnm1,shfnrot,tpwnh,tpwnhm1,shfnhrot global baseprngm,logbasepoolsize,basepoolsize,baseprngpool,baseprngseed global baseprn,baseindex,baseprngsum,shfbaseindex,shfbasebegin global initialrandompriming,baserandompriming,randompriming global prngm,logpoolsize,poolsize,maskpool global prngpool,prngseed,prngusecount,maxprngusecount global prn,index,shfindex,shfbegin,prngfeedback global initvecblocknum,finalvecblocknum,initvector,finalvector global ciphertextfilemode,formatstr,digitnum,hexnum,base,fileext global shfchoice if logn10 or baseprngm0: authen2=nplist[-finalvecblocknum:] nplist=nplist[initvecblocknum:-finalvecblocknum] else: authen2=[] nplist=nplist[initvecblocknum:] if authen1!=initvector or authen2!=finalvector: print("######### Authentication (intgegrity check) failed #########") exit(5) plaintextrecovered="" for i in range(len(nplist)): plaintextrecovered+=unpack(nplist[i],chnum) print("Plaintext has been recoverd from",ciphertextfile) print("Authentication (integrity check) ok") print() return(plaintextrecovered)

################################################################################ ################################################################################

######### Section 2. Examples of Applications of JADE-S.

##### The following code does not belong to JADE-S in the proper sense but serves ##### only to illustrate with examples further below how the user may apply ##### JADE-S.

# Maurer's Universal Test, see [3]. # [3] J-S. Coron, D. Naccache, An Accurate Evaluation of Maurer's Universal Test. #

qq=2560 qqp1=qq+1 kk=256000 qqkkp1=qq+kk+1

def maurertest(bb): global qq,qqp1,kk,qqkkp1 eftu=7.1836656 # y1 and y2 are for rho=0.01 and rho=0.001 respectively. y1=2.5758 y2=3.2905 t=[0 for i in range(256)] for i in range(1,qqp1,1): t[bb[i]]=i sum=0.0 for i in range(qqp1,qqkkp1,1): sum+=math.log10(i-t[bb[i]]) t[bb[i]]=i tu=(sum/kk)/math.log10(2.0) c=math.sqrt(0.3732189+(0.3730195*256)/kk) sigma=c*math.sqrt(3.2386622/kk) t11=eftu-y1*sigma t12=eftu+y1*sigma t21=eftu-y2*sigma t22=eftu+y2*sigma return(tu,t11,t12,t21,t22)

def maurertestresult(h,gg): global logn,n,np1,nm1,nh,chnum global qq,qqp1,kk,qqkkp1 if h*chnum>=8 u+=1 k1+=chnum k2+=chnum tu,t11,t12,t21,t22 = maurertest(bb) print("Maurer's Universal Test for L=8, rho=0.01 (Middle value is the "\ "test statistic\nand should lie between the other two values):") print(t11,tu,t12)

################################################################################

# User specified system parameters and key materials are assumed to be the # following for the examples below:

logn=8 baseprngm=4 logbasepoolsize=7 prngm=3 logpoolsize=8 maxprngusecount=50 initialrandompriming=10 baserandompriming=20 randompriming=50 initvecblocknum=1 finalvecblocknum=1 ciphertextfilemode=0

# keydata is a list of 2 elements of n/2 bits (n/8 hexs) each, seeddata 1 # element of n/2 bits (here they are arbitrary apparently 'non-random' # values chosen for the convenience of illustration only).

keydata=[ 0x11111111111111111111111111111111,\ 0x22222222222222222222222222222222 ] seeddata= 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

###################################################################################

# Example 1. Normal encryption and decryption.

print() print("Example 1:") print()

print("Normal encryption and decryption") print()

# We assume the sender has the following character string pt as plaintext:

pt="Was sich ueberhaupt sagen laesst, laesst sich klar sagen; und "\ "wovon man\nnicht reden kann, darueber muss man schweigen."

print("Original plaintext:") print(pt) print()

# The sender intializes the system,

initjades()

# encrypts pt, obtaining a ciphertext file ciphermessage.bin (ciphertextfilemode # is chosen above to be 0, thus the file cannot be printed and has to be sent as # such to the recipient.)

encrypt(pt,"ciphermessage")

# and sends it to the recipient.

# The recipient initializes the system,

initjades()

# decrypts the received ciphertextfile ciphermessage.bin (ciphertextfilemode is # 0 as chosen by the sender), assigns the result to pt1 and prints it out. # Result of authentication check will be automatically reported.

pt1=decrypt("ciphermessage")

print("Plaintext recovered:") print(pt1)

# If the plaintext message to be encrypted is in an external file (last line # preferably without 'return'), it can be read into pt with: # f=open("messagetobesent.txt","r")) # pt=f.read() # f.close() # Similarly the received plaintext message (after decryption is performed) can # be stored into an external file from pt1 with: # f=open("messagereceived.txt","w") # f.write(pt1) # f.close()

# Example 2: Measuring time of encryption/decryption.

print() print("Example 2:") print()

nnumb=10000 pt="" for i in range(nnumb): pt+="a"

print("Measuring time of encryption/decryption of a message of",nnumb,\ "characters") print()

start=time.clock() initjades() encrypt(pt,"ciphertext") print("encrypt time:",time.clock()-start,"sec") start=time.clock() initjades() pt1=decrypt("ciphertext") print("decrypt time:",time.clock()-start,"sec")

# Example 3. Perform Maurer's Universal Test on genrandom().

# User may like to employ JADE-S's function genrandom() for other usages, e.g. # for common numerical computations or obtaining PRNs (eventually in combination # with other sources) to generate key streams for other encryption schemes, and # may want to know their statistical properties. Hence the present example.

print() print("Example 3:") print()

# Note that theoretically there is a 0.01 chance for the test statistic tu to go # outside of the interval [t11, t12] (under the assumption that the sequence # being tested is random).

print("Testing pseudo-radnom numbers generated by genrandom()") print()

# Initialize the system.

initjades()

# Determine number of PRNs (words) needed for the test.

h=qqkkp1//chnum if h*chnum