Title of Invention

A CELLULAR AUTOMATA BASED AUTHENTICATION DEVICE FOR MESSAGE COMMUNICATION SYSTEMS

Abstract A cellular automate (CA) based authentication device for message communication system. The communication system comprises - a programmable cellular automata PCA (1) rule vector of which can be modified dynamically; a rule register (2) for holding individual message words and for forming rules for driving the PCA; a two predecessors single attractor TPSA register (3) for holding the rule for the PCA; a complement vector register (4) for holding the complement vector for running the PCA; start and final address register (5,6) for providing authentication signature as PCA content; and a controller (7) for generating timing and control signals for authentication.
Full Text 1
The present invention relates to a cellular automata based authentication device for message communication systems.
Message authentication schemes have their applications in electronic payment systems and other transactions in e-commerce. They can be used for validation of identity of system users and for verification of transactions in the distributed environment of large organisations or corporate houses.
Many message authentication schemes are available these days. Some of the more popular and important schemes are described b e1ow.
One of the most widely used message authentication scheme is MD—5 function developed by Ronald Rivest. It is based on MD-4 which is again an improvement of MD-2. All the three functions produce an 128-bit output signature for the input message padded to a fixed block length. Since MD—5 is; by the most commonly used scheme a comparison of i ts performance has been done with that of the present invention.
HAVAL is an extension of MD-5 proposed by Zheng, Pieprzyfc and Seberry. It can produce variable length output from 92-bits to 256-bits. Haval can be run on different number of 'rounds' of

internal algorithm, so that it can be made faster than MD-5, or alternately produces longer hash code output which is potentially more secure.
SHA was prepared by NIST in collaboration with MSA. It is similar to MD-4 but rectified i ts cryptographic drawbacks and produces 160-bit output instead of 128-bit- This algorithm is designed to be securedc such that to find two different messages to produce same digest or to recover the message from the digest requires infeasible computational cost.
In message authentication code (MAC) from the sender side, data
Dsent in plaintext or ciphertext is created and another k-bit
message authentication code MACsent is generated which is a
function of Dsent and a secret key. The message transmitted
(Msent) is Dsent with MACsent appended at the end. The receiver
uses the same procedure to calculate message authentication code
MACcal from the data received Dree; if MACcal is identical to the
MACrec then the data received is authenticated-.
Checksums are calculated as simple 1inear or polynomial functions of the message input, and produces a small value (16 or 32 bits).

- 4 -
They are easy to calculate and that is why very unreliable. A file can be easily altered so that its checksum value remains same before and after alteration, and hence prone to tampering.
Ralph Merkle designed SNEFRU,which is essentially a one-way hash
function for one-time signature as well as authentication of
public files, also can run on various rounds of internal
algorithm. But cryptographic analysis confirms that one can find
arbitrary messages that hash to a given 128-bit string if 4 round
SNEFRU is used. There were several attacks on MD—4 citing flaws
in its efficacy; if round 1 (of total 3) is omitted from the
compression function of MD—4, it was shown that collisions for
different, set of inputs do take place; it was further confirmed
that col1ision could take place even within milliseconds (if run
even on a PC) for inputs differing only on 3—bits if round 3 of
the compression function is omitted. These criticisms actually
motivated Rivest to propose the MD—5 version.
All these and other authentication functions that can be found in the 1 iterature in the past decade suffer from enormous time and resource requirements, as a result their hardware implementation become costly as well as complicated.

- 5 -
The problem of message authentication can be described in simple terms as follows:
Given : A received message (Mrec).
Decide : Whether the received message should be accepted as identical to the message originated by the sender (Msent).
Basically message authentication is a msny-to-one function. The
input to the function is the message block to be transmitted and
the output is the digital signature which is appended at the end
of transmission.
The present invention relates to a cellular automata (CA) based authentication device for message communication system, comprising
a programmable cellular automata PCA (l) rule vector of which can be modified dynamically;
a rule register (2) for holding individual message words and for forming rules for driving the PCA;
— a two predecessors single attractor TPSA register (3)
for holding the rule for the PCA;
— a complement vector- register (4) for holding the
complement vector for tunning the PCA;

- 6 -
- start and final address register " for providing
authentication signature as PCA content; and
- a controller (7) for generating timing and control
signals for authentication.
The invention can now be described in detail with the help of tables X and 2 and the accompanying drawings where:
Table 1: describes the set of 90-150 TPSA CA of length n
Table 2: gives the comparative performance of the proposed, method
vis -a-vis MD-5
Fig.1 : describes the structure and state transition behaviour of TPSA CA machine


Fig.2 : describes the structure and behaviour of complemented
TPSA CA machine. Fig.3 : describes the logic diagram of a cell of 90-150
programmable CA.
Fig.4 : describes a complete n-bi t 90-150 PCA structure. Fig.5 : describes the complete architecture of the proposed CA based authentication device for message communication systems.
A cellular automata (CA) consists of a number of interconnected cells arranged spatially in a regular manner. In the most general case, each such cell can exist in m different states and the next state of any particular cell depends on the present status of k of its neighbours. Such a general CA is called an m-state, k-neighbourhood CA. The present invention uses a simple 2-state,3-neighbourhood CA with the cells arranged linearly in one dimension. Each of the cells essential comprises of a memory built with a D flip-flop and a combinational logic that generates the next-state of the cell from the present states of neighbouring cells.
If the next state -function of a cell is expressed in the form of a truth table, then the decimal equivalent of the output column

8
in the truth table is conventionally called the CA rule number for the cell.
Here,investigation is carried out with a particular class of nongroup CA called two predecessors single attractor (TPSA) CA that can be employed for generating an efficient authentication function. As the name suggests, TPSA CA are characterized by the fact that every Reachable state in the transition graph has got only two predecessors. The only cye1ic state is the1 all-zero state, which is an attractor. The state transition graph of such a CA is an inverted tree as shown in Figure 1.
If some (or all) of the XOR gates of a linear CA are converted to XNOR logic, the state-transition diagram of the resulting CA can be analyzed with the characteristic matrix T of the corresponding 1inear CA. and the complement vector F. For an n-cell CA, the complement vector F is an n—bit vector with F[i] = 1 if the logic for the i-th cell is changed to XNOR, otherwise it is zero. If T is the next state function of this complemented CA, then corresponding to any state x, the next state is given by, Tx = Tx • F.
Figure 2 displays the state transition behaviour of a complemented TPSA CA machine.

9
In the following, we detail an algorithm for constructing an n-bit TPSA CA using rule 90 and 150 only. This particular CA and
its complemented one will be utilized in authentication device of present invention to a great extent.
Algorithm 1 Construct-CA(n)
Input : n, the size of the CA
Output : AIT n-bit CA with requisite set of rules r[i],i=l to n,
where r[i] denotes the rule for i—th cell,
begin


10
else if (n = 2k ) then/* n even; split into two equal parts of length k * /
C
for each part
recursively call Construct-CA(k);
Change the rules of cells k
and k + 1 fromrule '90' to rule '150'
or vice—versa;


- 11 -
Any CA generated by the Construct-CA algorithm is TPSA. Some examples of 90-150 TPSA CA constructed by this algorithm have been noted in Table 1.

It may be noted that in CA based data authentication scheme a cell configured with rule 90 depends only on its left and right neighbours, whereas, a cell controlled with rule 150 depends upon itself, left and right neighbours. The CA is initially loaded with the authenticationkey value agreed upon by both the parties. For n-bit key, length of the CA is n, and n-bit stream of message data is used to control the rule configuration of the individual CA cells. If the i-th bit of a stream is '0' , then i-th cel1 is configured to run under rule 90 else under rule 150. After applying an n-bit stream to configure the rule, the CA is run for one cycle Next,the CA is again configured for the rule using the next n-bit stream of the message, and is run for another cycle, and so on.

12
To make the cracking complexity of the scheme high, the 90-150 TPSA CA and is complemented form between every two n-bit mesage streams have been used. That is, after running the CA with rule configured by a message stream, the CA is configured as a 90-150 TPSA CA, constructed as per Construct-CA algorithm and run for one cycle, and as a complemented one of the above and run for one clock cycle.
Since the characteristic: matrix of a TPSA CA is singular, its inverse does not exist.This iancreases the cracking complexity by a factor of two for every run. Complemented CA contributes to the cracking complexity in identical fashion, moreover, it ensures that signature is never all zero, and run of the CA stops only when all of message data array is exhausted.
In the foilowing a step—by-step enumeration of the authentication scheme is given.
Step is Generate an n-bit TPSA CA, executing the algorithm
Construct-CA. Step 2: Generate the corresponding complemented CA, usings
Theorem 10 to get the complement vector F,

13
Step 3: Let K be the key of length n, known to both the parties (we gave randomly generated key). Let M be the message length- Add pad (each a string of single one followed by all zeros) so that total length of key-code, message and pad is multiple of n. The first element of the message data array is now the key-Step 4: Load- the CA with the seed - which is the first element of the data array, i.e. key.
Step 5: (i) Take the next stream of n—bits from the message data array, configure rule of the n-bit CA with the stream and run for one clock cycle.
(ii) run the CA for next clock cycle in TPSA mode with rule formed in Step 1.
(i i i) run the CA for another cycle in complemented mode with rule and complement vector F in Step 2.
Step 6: If all the message data elements are exhausted then stop - CA contains now the authentication signature; else go to Step 5.

14
Table 2 shows the result of the experiments performed in a HP — 9000 machine. Message length varies from 116 KBytes to 11.6 MBytes; the string length (number of bits) of the array is around 31 bits. The authentication signature length is 12S. Comparitive results for MD-5 for CPU time is shown along with - Message data and key are generated randomly.
Since TPSA C. A. and its complement is used whose state transition generates inverted tree, at every stage of the run with n—bit
message stream, the probability of tracint back to the original
content is 2 . If total message data array forms such k
-2k elements, then cracking probability is is 2 ; for large k this
is less than 2 and it is well nigh impossible to get back the
original key from the signature, except by brute force random
n trial, which ensures probability not greater than one in 2 -
It can be seen that even for software implementation, the proposed method is nearly 1.6 times faster than MD-5. The hardware analysis of parallel implementation of MD—5 based on basic step data flow diagram is detailed in Joseph's paper tiles "Performance analysis of md5" in ACM'Bigcomm.1955.
It shows that such a hardware can run at most at 300 MHz clock, and given 5 basic steps per 32-bit word of input, and considering

15
the critical path through the basic step, the maximum speed of performance achievable for any MD—5 based hardware (even for parallel implementation) is 256 Mbps.
Now, if we run the CA at compatible clock speed of 300 MHz, we will require altogether 4 clock cycles (one to load the input
word, and another 3 from step-5) to process one 32-bit input
word. This gives a performance limit of 300 x 106 X 32 4
or 2400 Mbps. This is nearly 10 times faster than MD-5 .
Even for technology independent realization, the proposed method
takes 6 cycles (apart from much more complicated and costly
hardware), thus proposed device is atleast 6 times faster at the
technological limit.
The hardware implementation of the CA structure, as reported earlier, suits ideally for VLSI implementation for its simple, modular, and regular structure with local interconnections- A CA whose rule vector can be modified dynamically is referred to as Programmable CA (PCA). Such a PCA can be used for hardwired data authenticator. Because of its local interconnections, the CA can be made to run at a very high clock rate, in the region of 300 MHz or more.

- 16 -
To retain the flexibility of applying different set of rules for
different n (CA-length) PCA structure has been employed. An
individual cell of PCA is shown in Fig. 3. To load an initial bit
into the cell,Auto is set to '0'; in the next clock edge, Seed
gets loaded into D flip-flop. For free run of the CA, Auto is set
to one, and clock pulses are applled. Rule configuration is
controlled by S.C. (self control) lines. Depending on the rules
90 or 150 these lines will be either zero or one respectively.
L.D. and R.D. (left and right data) lines are output coming from
left and right neighbours.

The complete n-bit 90-150 PCA structure is shown in Fig.4. Left and right boundaries are set to zero. Seed will be loaded into

- 17 -
PCA with Auto=O; for Auto=l, CA will have transition to its next state on every clock edge.
Register transfer level (RTL) description of the complete hardware scheme is shown in Fig.5. Individual components are
described' as follows :
I. N-bit PCA(1): this is an N-bit 90-150 PCA, first loaded with
seed (key). It is run in three different configurations control led by message stream, TPEA uncomplemented and TPSA
complemented, depending on S.Cv and XOR values.
II. Rule Reg(2): It holds individual message words which gives
S.C. input to form rule for driving the PCA.
III. TPSA Regi(3): Holds the rule for n-bit 90-150 PCA as per
Construct— CA procedure
IV. Complement Vector Reg-: This holds the complement vector to

run the PCA with XNOR logic. Apart from introducing non-linearity, this ensures PCA does not halt even if its content
become zero.
V. Address Registers(5,6): Start Address Reg(5). is initialised to
zero and incremented every time to bring message word from memory

to Rule Reg.; Final Address Reg.(6)contains the address of the last
location of the message data array. When these two become equal

18
Comparator(8) generates 'match' signal to the controller which now stops the running of the PCA. Authentication signature is now
available as PCA content.
VI. Controller(7) It generates timing and control signalls for the
micro-operations as described below :
FOR micro—operations for authentication,
1. Clear the Start Address Reg. with c = 1.

2. Load Final Address Reg. with last location address, with c =1
3. Load complement vector F into Compl. Vector Reg.; TPSA rule
for n-bit 150-90 CA (as generated by Construct-CA algorithm) into
TPSA Reg., with c =1.
5
4. Load PCA with seed which is key and first element of the
data array with c = 1, and c =1.
9 7
5. Run the PCA for one clock cycle with c = 1 ; as per rule
9 governed by the message word.
6. Run the PCA for the next clock cycle with TPSA rule from
TPSA REG.with c = I and c = 1. This ensures that now the
o 9
-1 probability of getting back to the parent state (of PCA) is 2
7. Run the PCA for next clock cycle with complement vector
1 9
for XNOR logic, with C = 1 and c = 1.
Increment the Start Address Reg with c = 1 .
2

19

B. Load Rule Reg. by the next message data from memory with
c = 1 .
6 9. Go to step no. 5.
So, for one data we require about 4 clock cycles (Step 5—8) . Hence, for 300 MHzm clock of the CPU for 1.2 MByte data with 32-bit PCA (32-bit memory word), the time required for signature generation is nearly equal to 4 x 1-2 x 106 (32 x 300 x 10 sec; comparing with result ir. Table-2, this is nearly 2600 or 3-order faster.
The design has been specified in Verilog, simulated for
functional correctness, and synthesized using the Cadence tool
2 Synergy. It requires an area of 324982.25 urn using the Cellslib
1ibrary.
Software version of the scheme is nearty two times faster than the standard MD-5 method with the same level of performance. The hardware version is about 3-order of magnitude faster- The ASIC for the device has been implemented using Cadence tool Synergy. The detail design including circuit diagram, routing, and placement of the functional device will be given with the complete specification.

20
WE CLAIM :
1. A cellular automata (CA) based authentication device for message
communication system, comprising
- a programmable cellular automata PCA (1) rule vector of which
can be modified dynamically;
- a rule register (2) for holding individual message words and for
forming rules for driving the PCA;
- a two predecessors single attractor TPSA register (3) for holding
the rule for the PCA;
- a complement vector register (4) for holding the complement
vector for running the PCA;
- start and final address register (5,6) for providing authentication
signature as PCA content; and
- a controller (7) for generating timing and control signals for
- authentication.

2. The device as claimed in claim 1, wherein said PCA (1) is an N-bit
90-150 programmable CA.
3. The device as claimed in claims 1 or 2 wherein, said PCA (1) is
capable of being run in three different configurations controlled by
message stream, TPSA uncomplemented and TPSA complemented.
4. The device as claimed in the preceding claims wherein, said rule is for
N-bit 90-150 PCA as per construct - CA procedure.
5. The device as claimed in the preceding claims wherein said
complement vector register (A) is provided with XNOR logic for

-21-


introducing nonlinearity and for ensuring that the PCA does not halt when its content becomes zero.
6. The device as claimed in the preceding claims wherein a comparator
(8) is provided for generating 'match' signal and providing the signal
to said controller (7) when said start and final address become equal.
7. The device as claimed in the preceding claims wherein said controller
(7) is a micropressor for micro-operation of said authentication
device.
8. A cellular automata based authentication device substantially as herein described and illustrated in the accompanying drawings.
A cellular automate (CA) based authentication device for message communication system. The communication system comprises -
a programmable cellular automata PCA (1) rule vector of which can be modified dynamically;
a rule register (2) for holding individual message words and for forming rules for driving the PCA;
a two predecessors single attractor TPSA register (3) for holding the rule for the PCA;
a complement vector register (4) for holding the complement vector for running the PCA;
start and final address register (5,6) for providing authentication signature as PCA content; and
a controller (7) for generating timing and control signals for authentication.

Documents:

00699-cal-2001 abstract.pdf

00699-cal-2001 claims.pdf

00699-cal-2001 correspondence.pdf

00699-cal-2001 description (complete).pdf

00699-cal-2001 description (provisonal).pdf

00699-cal-2001 drawings.pdf

00699-cal-2001 form-1.pdf

00699-cal-2001 form-18.pdf

00699-cal-2001 form-2.pdf

00699-cal-2001 form-3.pdf

00699-cal-2001 form-5.pdf

00699-cal-2001 g.p.a.pdf

00699-cal-2001 letters patent.pdf

699-cal-2001-granted-abstract.pdf

699-cal-2001-granted-claims.pdf

699-cal-2001-granted-description (complete).pdf

699-cal-2001-granted-drawings.pdf

699-cal-2001-granted-form 2.pdf

699-cal-2001-granted-specification.pdf


Patent Number 201416
Indian Patent Application Number 699/CAL/2001
PG Journal Number 08/2007
Publication Date 23-Feb-2007
Grant Date 23-Feb-2007
Date of Filing 20-Dec-2001
Name of Patentee INDIAN INSTITUTE OF TECHNOLOGY
Applicant Address AN INDIAN INSTITUTE OF KHARAGPUR
Inventors:
# Inventor's Name Inventor's Address
1 DASGUPTA PRABIR C/O INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR, 721302
2 CHATTOPADHYAY SANTANU C/O INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR, 721302
3 SENGUPTA INDRANIL C/O INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR, 721302
PCT International Classification Number G 06 F 7/00
PCT International Application Number N/A
PCT International Filing date
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 NA