Automata Under Effective Observation Alexandr Babash [0000-0001-7578-6923] Plekhanov Russian University of Economics, 36 Stremyanny lane, Moscow, 115998, Russia babash@yandex.ru Abstract. A trapdoor cipher is a cipher whose algorithm contains some hidden structure (a trapdoor) providing the existence of a subliminal information channel. In cryptographic practice, there could be situations when a constructed cipher may contain some critical defect (a trapdoor) whose identification can significantly weaken the cryptographic strength of this cipher. In this paper, we propose and analyze one of such defects in terms of automata-theoretic approach. An operation of the cipher with this defect is modeled by a finite automaton under the so-called effective observation. The existence of effective observation for a finite automaton qualitatively reflects the presence of a trapdoor which allows one to determine the information on automaton input words by observations over the corresponding output words. We prove the criterion of finding an automaton under effective observation and specify the classes of automata under effective observation and the classes of automata for which there is no effective observation. Possible applications of the results for protecting ciphers from side channel attacks are formulated. Keywords: Cryptography, Automata theory, Cipher models, Automata under effective observation. 1 Introduction The analysis of ciphers in terms of automata theory is now becoming quite common. This approach allows one to formulate and solve cryptographic problems for different cipher classes. In cryptographic practice related to the synthesis (construction) of ciphers, there could be situations when one consciously builds a trapdoor cipher, i.e., a cipher whose algorithm contains some hidden structure (a trapdoor) providing the existence of a subliminal information channel. Except for this case, ciphers are usually built without such forethought defects. However, a constructed cipher may Proceedings of the 10th International Scientific and Practical Conference named after A. I. Kitov "Information Technologies and Mathematical Methods in Economics and Management (IT&MM-2020)", October 15-16, 2020, Moscow, Russia © 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) contain some critical defect (a trapdoor) whose identification can significantly weaken the cryptographic strength of this cipher. One of such defects is proposed and analyzed in this paper in terms of automata-theoretic approach. This defect presents in a cipher whose operation is modeled by a finite automaton under the so-called effective observation. Let A=(X,S,Y,h,f) be a finite automaton with an input alphabet X, a set of states S, an output alphabet Y, a transition function h:SХS, and an output function f:SХY. Denote by A(s,P) an output word of the automaton A resulting from the initial state s when the input word is P=x1x2…xk. The problem. It is required to find functions Uk, Фk such that Uk(P)=Фk(A(s,P)) for any pair (s,P)∈SХk, Uk≠const, Фk≠const. An automaton that satisfies this condition for some k is called an automaton under effective observation. This paper is organized as follows. In section 2, we justify the need for the setting of the presented problem and list possible areas of cryptographic information security where this problem and the results of its solution are of interest. In Section 3, we introduce the basic notions and notations by which automata-theoretic model of the problem is formulated. In this model, the examples of possible problem formulations are presented. Then we prove the criterion of finding an automaton under effective observation, i.e., the criterion of possible determining the information on key elements of a cipher or the information on a plaintext by the given observable information. This section also contains some previous results on the subject obtained by the author. The main results are in Section 5. It is devoted to finding the classes of automata for which, within the given mathematical model, it is impossible to determine the information on an automaton input word by the corresponding output word. We also consider the question whether this problem is algorithmically solvable in the class of all automata. The paper is concluded in Section 6. 2 Relevance of the problem Let us clarify in which areas of IT technologies it is useful to apply the description of automata under effective observation and the automata for which there is no effective observation. First of all, we are talking about devices and programs that are modeled by finite automata. 2.1 Computer bugs An information channel is called covert if it is not specifically designed and was not originally supposed to transfer information in electronic data processing system. A covert channel is called subliminal if it can be used only by the holder of the corresponding secret information. The idea of subliminal information channels was first introduced in the works of Simmons [1-3], by the example of a covert channel in the digital signature system with a public key. In [4], there is the description of the covert channel performance for the digital signature algorithm (DSA) [3], and the papers [5], [6] describe the covert channel performance for the digital signature algorithm Ong-Schnorr-Shamir. The device embedded in a computer and modeled by a finite automaton under effective observation provides you with an automatic retrieval of the input device information. 2.2 Trapdoor cipher A trapdoor cipher is a cipher whose algorithm contains some hidden structure (trapdoor) providing the existence of a subliminal information channel; knowledge of this structure allows one to obtain sensitive information (such as secret keys). Without the trapdoor knowledge, the cipher seems to be secure. One of the most important types of trapdoors that can be embedded in cryptographic algorithms is the so-called SETUP (Secretly Embedded Trapdoor with Universal Protection) mechanism [5], [6]. The SETUP mechanism modifies the given cryptographic algorithm in a way that allows the developer of the cryptosystem to obtain sensitive user information (often about their secret keys). At the same time, for any observer different from the developer, the performance of the modified algorithm is indistinguishable from the performance of the original algorithm. Such modified cryptosystems are sometimes referred as infected cryptosystems. In [5-7], it is shown that a number of well-established cryptographic primitives can be modified by including the SETUP mechanism in the body of the relevant program. For example, in [7], there is the description of the scheme for constructing a covert information channel in a block cipher. An embedded SETUP mechanism completely compromises the corresponding cryptosystems in relation to its developer (and only in relation to him). These attacks require a single tampering with a cryptosystem. A particular danger is posed by SETUP mechanisms for smart-cards because its key generation always takes place without user intervention. In the case of block ciphers, one can also employ the leakage channels running during the generation and transmission of the so-called Initial Vectors used in OFB, CFB, and CBC modes. The main known results for embedding trapdoors in ciphers are obtained for public-key cryptosystems, in particular, for the little-known public-key encryption algorithm based on finite automata and called FAPKC (Finite Automaton Public Key Cryptosystem). Our proposed method for constructing a trapdoor cipher is different from the known ones. It is based on the choice of the automata-theoretic model for the cipher under effective observation. Its principal features are described in the section 5 «On reconstruction of information on an automaton input word by the corresponding output word». 2.3 Side-Channel Attacks Side-channel attacks (SCA) are a type of cryptographic attacks which exploit information leaked from side channels [8-17]. Let us list some methods to prevent side-channel attacks: masking; blinding; carrying out the computations whose performance time does not depend on data; refusing procedures that use secret intermediate values or keys for conditional transfers; preventing timing attacks by the alignment of performance time for various operations; balancing power consumption; adding a noise (one of the solutions proposed in [18] against Differential Power Analysis (DPA) with the use of a noise is to add random computations which increase the noise level so that it becomes impossible to determine the shift of DPA spikes); shielding; performing double encryption [19]. The approach proposed in the section 5 allows one to put forward an idea of protecting a given automaton from cryptographic attacks using information leaked from side channels. The idea is to construct a new automaton with a large number of states that has the given automaton as a homomorphic image. In the said section, the homomorphic image of the new automaton is an automaton with one state. 2.4 Ciphers In the works of Claude Shannon [20], there is the description of the so-called "perfect ciphers". In the modern terminology, they are sometimes referred as theoretically unbreakable ciphers. An example of such a cipher is the random gamma cipher. The input alphabet of such a cipher is the set of indexes I={0,1,...,N-1} which label the letters of the ordered alphabet used for plaintexts. Then the set IL is the set of all possible plaintexts of length L. At the same time, IL is the set of keys and the set of ciphertexts. The encryption process of the plaintext i=i1i2…iL by the randomly and equiprobably selected key γ=γ1γ2…γL is described by the equations ij+γj=zj mod N, j∈{0,1,…,N-1}, where z=z1z2…zL is a ciphertext. It is obvious that any plaintext i can be encrypted into the ciphertext z under the appropriate choice of the key γ. Thus the plaintext reconstruction based on the knowledge of a ciphertext is impossible. But if the cipher is not theoretically unbreakable, the known ciphertext sometimes allows one to reconstruct a subset Ii,z of the set IL that contains the desired plaintext. In this case, it is convenient to talk about the information on the plaintext i extracted from its corresponding ciphertext z. The smaller cardinality of this subset, the more extracted information on the desired plaintext. The subset Ii,z can be defined by its characteristic function F1. In cryptographic practice, there could be situations when the ciphertext z is fully unknown. In the introduced notation, this means we know a subset Zz of the ciphertext set Z that contains the given z, or equivalently the value of the characteristic function F2 of this subset. The cipher for which the desired plaintext can be uniquely determined by its ciphertext is obviously the worst cipher. Not the best cipher would be the cipher for which information on the desired plaintext can be extracted from the observed data of the ciphertext. The above gives rise to the following novel setting of a cryptographic problem. Is it possible, for a given cipher with a plaintext set W, a ciphertext set Z, a set of keys K, and an encryption equation f(w,k)=z, to find nonconstant functions F1 and F2 that satisfy the condition F1(w)=F2(f(w,k)) for any wϵW, kϵK. The conditions under which such functions do not exist are of value for the synthesis of ciphers. This problem will be solved below using the automata-theoretic approach. It should be noted that by now the automata-theoretic approach to the analysis and synthesis of ciphers has become the natural and traditional direction of cryptanalysis. This is because many encryption systems are mathematically modeled by finite automata. For example, one can imagine that a plaintext is supplied to an input of an encryption device, while the corresponding ciphertext is generated as an output, and the encryption device sequentially changes its state. Note that for a number of classical ciphers, one often imposes the requirement of reversibility which, in the case of decryption error detection, allows one to return to the previous decrypted text and correct the error. In terms of the automata-theoretic approach, the latter is achieved by the use of the so-called permutation automata. Block ciphers are usually also represented by permutation automata, for which reason it is interesting to solve the problem of extracting information on round keys (on an input automaton sequence) from the pairs of input and the corresponding output units (from the pairs of initial and final automaton states). 3 Basic notions and notations 3.1 The notion of an automaton under observation We will use the following notation: A=(X,S,Y,h,f) is a finite automaton with an input alphabet X, a set of states S, an output alphabet Y, a transition function h:SХS, and an output function f:SХY; hx:SS is a partial transition function corresponding to the input symbol xX, hxs=h(s,x); hP s  hxk ...hx2 hx1 s is a final state of the automaton A resulting from the initial state s when the input word is P=x1x2…xk; A(s,P) is an output word of the automaton A resulting from the initial state s when the input word is P. The cardinality of a set M is denoted by |M|. For a finite automaton A=(X,S,Y,h,f) and a natural number k, denote by Rk, Тk some finite sets. Consider the surjective mappings Нk:SХkТk, Пk:SХkRk. Suppose that the automaton A with initial states s from S receives the input words РХk. The pairs (s,Р)SХk for which the automaton operates are unknown. However, for each pair (s,Р)SХk, we know the element t=Нk(s,P) called an observation element. The problem. Identify the information on the element r=Пk(s,P), where r is the value of the desired operation parameter of the automaton A with initial state s and input word P. By the information on the unknown element r, we mean the identification of a proper subset R` of the set Rk that contains r. Conventionally speaking, we suppose that some function Uk on Rk is given and its value Uk(r)=j defines the subset R`={r`: r`Rk, Uk(r`)=j} (lumped state). It is also supposed that j (or the subset R`) can be defined by the known observation element t=Нk(s,P). Formally, we mean that there is a function Фk whose value Фk(t) defines j. Thus we have (Fig.1): k is a natural number indicating the length of automaton input words; Пk:SХkRk is an objective function; r=Пk(s,Р) is the value of the parameter under study for the triple (k,А,(s,Р)), (s,Р)SХk; Нk:SХkТk is an observation function; t=Нk(s,P) is an observation element for the triple (k,А,(s,Р)), (s,Р)SХk; Фk is an observation information function; Uk is an objective information function. The family of introduced objects (k,Тk,Rk,Нk,Пk) is called the observation over the automaton A. P s A(s,P) Find Пk(s,Р) Observation Нk(s,P) Fig.1. The automaton under effective observation Uk(Пk(s,P))=Фk(Hk(s,P)). Definition 1. An automaton A=(X,S,Y,h,f) is said to be under the effective observation (k,Тk,Rk,Нk,Пk) if there exist nonconstant functions Фk on Тk and Uk on Rk such that Uk(Пk(s,P))=Фk(Hk(s,P)) (1) for any pair (s,P)SXk. The property of effective observation can be interpreted as the ability of automatic extraction of the information on the desired parameter r=Пk(s,Р) from the observation parameter t=Нk(s,P) during the automaton operation process. Note that if the functions Фk, Uk are constant, equation (1) does not provide any useful information on the value of the parameter r for the observation t. Definition 2. For the sequence of observations (k,Тk,Rk,Нk,Пk), k∈{1,2,…} over an automaton A, denote by D(A) the minimum k for which the automaton A is under effective observation. We call D(A) the depth of the automaton observation. If there is no such k, we set D(А)=. Definition 3. An automaton A is said to be under effective observation if the depth of its sequence of observations is finite. Definition 4. The functions Фk and Uk for k=D(А) are called the main functions for the automaton A under the observation (k,Тk,Rk,Нk,Пk). 3.2 Examples of basic notions Example 1. Diagnostic experiment with the automaton A [21]. Consider the following observation (k,Тk,Rk,Нk,Пk), where Нk(s,P)=(P,A(s,P)), Тk is the image of the set SXk under the mapping Нk, Пk(s,P)=s, and Rk=S. The fulfillment of the condition Uk(Пk(s,P))=Фk(Hk(s,P)) for any pair (s,P)∈SXk can be written in the form Uk(s)=Фk(P,A(s,P)). In this case, the function value Uk(s) is determined by the input and the corresponding output automaton sequences. Suppose further that Uk(s)=s for any s∈S. Then the equalities s=Фk(P,A(s,P)), (s,P)∈SXk mean that each input word РХk is diagnostic for the automaton A [21]. If, instead of all the pairs (s,P)∈SXk, we consider only the pairs (s,P)∈S{Р}, where {P} is a singleton, then the condition s=Фk(P,A(s,P)), (s,P)∈S{Р} will imply that the word P is a diagnostic sequence for the automaton A. Homing experiment with the automaton A [21]. The homing experiment formulation in the introduced terms is analogous to that one of the diagnostic experiment. In [22-24], authors studied the problem of partial definition of an automaton input word by its initial state and the corresponding output word as well as the problem of partial definition of an automaton input word by its final state and the corresponding output word. A more systematic study of these issues was conducted by Sh. Iwen [25], A. A. Kurmit continued this study in his monograph [26]. 4 Effective observation over an automaton 4.1 The criterion of finding an automaton A under the effective observation (k,Тk,Rk,Нk,Пk) For brevity, we introduce the following notation:  means “if and only if”;  means “then”;  means “exists”;  means “for all”; PQ is a concatenation of words P and Q (in particular, (P)k is a concatenation of k copies of the word P). Let M be a finite set, σ a reflexive (mσm mM) symmetric binary relation on M, σ* the transitive closure of σ, and rang σ* the number of equivalence classes under the binary relation σ*. The binary relation σ is said to be transitive if rang σ*=1. The functions Нk, Пk induce the partitions of the set SXk defined by the binary equivalence relations Н*=Н*k, П*=П*k on SXk. Namely, (s,P)Н*(s`,P`)  Нk(s,P)=Нk(s`,P`), (s,P)П*(s`,P`)  Пk(s,P)=Пk(s`,P`). The classes under the equivalence relations Н*k, П*k will be denoted by the letters t and r of the corresponding sets Тk, Rk, i.e, the letter t can also denote Нk-1(t), the preimage of t, and similarly for the letter r. The context will make it clear whether t and r stand for elements or classes. In particular, Тk, Rk will refer, if necessary, to the sets of the classes under the equivalence relations Н*k, П*k, respectively. Denote by t[s,P] the class comprising (s,P) under the equivalence relation Н*k and by r[s,P] the class comprising (s,P) under the equivalence relation П*k. Let us introduce the binary equivalence relations Тk/П*k on Тk and Rk/Н*k on Rk. For this purpose, we use the auxiliary binary relations ~ on Тk and ~ on Rk. The same symbol ~ is used for simplicity. The elements t, r of the sets Тk, Rk are simultaneously considered as the classes t[s,P], r[s,P], t~t`  (s,P)t, (s`,P`)t`, rRk: (s,P)r, (s`,P`)r. The equivalence relation Тk/П*k is the transitive closure of the binary relation ~, i.e., t1 Тk/П*k tL  t2,…,tL-1Tk: t1~t2~…~tL-1~tL. Similarly, r~r`  (s,P)r, (s`,P`)r`, tTk: (s,P)t, (s`,P`)t, and Rk/Н*k is the transitive closure of the binary relation ~ on R k. Note that tTk, rRk: t~t, r~r, t Тk/П*k t, r Rk/Н*k r. Define the binary equivalence relation Н*kП*k on SXk by the auxiliary binary relation  on SXk, (s,P)  (s`,P`)  tTk, rRk: (s,P), (s`,P`)tr, i.e., (s,P), (s`,P`)t or (s,P), (s`,P`)r. To specify the relation (s,P)  (s`,P`), (s,P), (s`,P`)tr, we write (s,P) Н*k (s`,P`)  tTk: (s,P), (s`,P`)t and (s,P) П*k (s`,P`)  rRk: (s,P), (s`,P`)r. Denote by Н*kП*k the transitive closure of the binary relation . The equivalence relations Тk/П*k on Тk and Rk/Н*k on Rk induce the equivalence relations (Тk/Пk)*, (Rk/Нk)* on SXk, (s,P) (Тk/Пk)* (s`,P`)  t[s,P] Тk/П*k t[s`,P`], (s,P) (Rk/Нk)* (s`,P`)  r[s,P] Rk/Н*k r[s`,P`]. Denote by Н*kП*k[s,P], (Тk/Пk)*[s,P], (Rk/Нk)*[s,P] the classes comprising (s,P) under the equivalence relations Н*kП*k, (Тk/Пk)*, (Rk/Нk)* on SXk, respectively. Theorem 1. For the binary equivalence relations on SXk there holds the equality Н*kП*k=(Тk/Пk)*=(Rk/Нk)*. Proof. Let us show that (Тk/Пk)*=Н*kП*k. The equality (Rk/Нk)*=Н*kП*k can be proved similarly. Suppose (s,P) (Тk/Пk)* (s`,P`). Then (s,P) (Тk/Пk)* (s`,P`)  t1[s,P] Тk/П*k tL[s`,P`]  t2,…,tL-1Tk: t1[s,P]~t2~…~tL-1~tL[s`,P`]  tj~tj+1, j{1,2,…,L-1}  (sj,Pj)tj, (s`j,P`j)tj+1, rjRk: (sj,Pj), (s`j,P`j)rj  (s,P)Н*k(s1,P1)П*k(s`1,P`1)Н*k(s2, P2)П*k(s`2,P`2)…(s`,P`)  (s,P) Н*kП*k (s`,P`). Conversely, suppose (s1,P1)Н*kП*k(sL,PL). Then (s1,P1) Н*kП*k (sL,PL)  (s2,P2),…,(sL-1,PL-1), (1),(2),…,(L-1){Н*k, П*k}: (s1,P1)(1)(s2,P2)(2),…, (sL-1,PL-1)(L-1)(sL,PL). In the above chain of binary relations, choose the chain of minimum length L. In this case, (j)(j+1) for any j{1,2,…,L-2} and we have t[sj,Pj]=t[sj+1,Pj+1] if (j)=Н*k, t[sj,Pj]~t[sj+1,Pj+1] if (j)=П*k. Hence, t2,…,tL`: t[s1,P1]~t2,~…~tL`~t[sL,PL]  t[s1,P1] Тk/П*k t[sL,PL]  (s1,P1) (Тk/Пk)* (sL,PL). □ Corollary 1. For the number of classes under the equivalence relations Н*kП*k on SXk, Тk/П*k on Тk, and Rk/Н*k on Rk, it follows that rang Н*kП*k=rang Тk/П*k =rang Rk/Н*k. Proof. In view of Theorem 1, it suffices to show that rang Тk/П*k=rang (Тk/Пk)*. By definition, (s,P) (Тk/Пk)* (s`,P`)  t[s,P] Тk/П*k t[s`,P`], from whence it follows that (Тk/Пk)*[s,P]=tj[sj,Pj] for any (s,P)SXk, where the union is taken over all the classes tjТk/П*k[t[s,P]]. The required statement follows directly from the above equation. □ Theorem 2. The automaton А=(Х,S,Y,h,f) is under the effective observation (k,Тk,Rk,Нk,Пk) if and only if rang Н*kП*k2. Moreover, the values of the functions ФkHk, UkПk on SXk are the same and constant on the classes Н*kП*k, while the values of the functions Фk, Uk are constant on the classes Тk/П*k and Rk/Н*k, respectively. Proof. Suppose that some functions Фk, Uk satisfy the following: Фk(Hk(s,P))=Uk(Пk(s,P)) for any (s,P)SXk. Consider two elements (s1,P1), (sL,PL) from the same class under the equivalence relation Н*kП*k. Then (1), (2), …, (L-1){Н*k, П*k}, (s2,P2),…,(sL-1,PL-1)SXk: (s1,P1)(1)(s2,P2)(2)… (L-1)(sL,PL). For (j)=Н*k, we obtain Фk(Hk(sj,Pj))=Фk(Hk(sj+1,Pj+1)) and hence Uk(Пk(sj,Pj))=Uk(Пk(sj+1,Pj+1)). For (j)=П*k, we obtain Uk(Пk(sj,Pj))=Uk(Пk(sj+1,Pj+1)) and hence Фk(Hk(sj,Pj))=Фk(Hk(sj+1,Pj+1)). Thus the functions ФkHk, UkПk on SXk take the same and constant values on the classes Н*kП*k. By Theorem 1, Н*kП*k=(Тk/Пk)*=(Rk/Нk)*, and hence the functions ФkHk, UkПk are constant on the classes under the equivalence relations (Тk/Пk)*, (Rk/Нk)*. For any pair (s,P)SXk, (Тk/Пk)*[s,P]= t j [s j , Pj ] , tj where the union is taken over all tjTk/П*k[t[s,P]]. Similarly, (Rk/Hk)*[s,P]= rj [s j , Pj ] , rj where the union is taken over all rjRk/Н*k[r[s,P]]. Therefore, Фk and Uk are constant on the classes Тk/П*k and Rk/H*k, respectively. It is clear that Фk and Uk are nonconstant if and only if rang Н*kП*k=rang Тk/П*k= rang Rk/Н*k≥2. □ Corollary 2. The depth D(A) of the observation over the automaton А for the sequence of observations (k,Тk,Rk,Нk,Пk), k∈{1,2,…} coincides with the minimum k for which rang Н*kП*k=rang Тk/П*k=rang Rk/Н*k≥2. If there is no such k, then D(А)=. 4.2 Previous results Reconstruction of information on the first input symbol of an automaton input word by the corresponding initial state and output sequence [27]: Rk=Х, Тk=(SYk), k{1,2,…}; Пk(s,x1x2…xk)=x1, Нk(s,x1,x2,…,xk)=(s,А(s,x1,x2,…,xk)). Reconstruction of information on an input word in a permutation automaton by the corresponding initial state and output sequence [27]:. Rк=Хк, Пк:ХкSХк, Пк(х1,х2,…,хк,s)=х1,х2,…,хк, Тк=SYк, Нк:ХкSSYк, Нк(х1,х2,…,хк,s)=(s,A(s,х1,х2,…,хк)). Reconstruction of information on an automaton input word by the corresponding final state and output sequence [27]: Rк=Хк, Пк:ХкSХк, Пк(х(1)х(2)…х(к),s)=(х(1)х(2)…х(к)), Тк=SYк, Нк:XкSSYк, Нк(х(1)х(2)…х(к),s)=(h(s,х(1)х(2)…х(к)), A(s,х(1)х(2)…х(к))). Reconstruction of information on an input word in a permutation automaton given initial and final states [28]. For a word Р=х(1)х(2)…х(k) in Хk, set hР=hх(k)hх(k-1)…hх(1). Denote by hРs the image of s under hР and by S(L) the set of all subsets of S with cardinality L, L≥1. Define the function Hk,L on Xk×S(L) as follows. For s(L)={sj(1),sj(2),…,sj(L)} in S(L) and P=x(1)x(2)…x(k) in Xk, set Hk,L(P,s(L))=(s(L);hPs(L))= {(sj(1),hРsj(1)),(sj(2),hРsj(2)),…,(sj(L),hРsj(L))}. This expression can be considered as a partial permutation on S (L transitions are defined for the permutation hР). Denote by Hk,L(Xk×S(L)) the image of Hk,L. We say that k-length input words of an automaton A can be approximately reconstructed given L initial and final states if there exist nonconstant functions Φk,L and Uk,L, defined on Hk,L(Xk×S(L)) and Xk, respectively, such that for any PXk and s(L)S(L) we have Uk,L(P)=Φk,L(s(L),hPs(L)). In what follows, we refer to this fact by saying that the automaton A possesses the (Хk,s,hPs,L)-reconstruction property. The problem of describing automata with the (Xk,s,hPs,L)-reconstruction property is close to the following problems: experimental designs for automata (see [24], [30]), where an unknown input word is used for testing, with initial and final states being observed as experimental results; local reconstruction of information on an input word (see [29], [30]) given initial and final states; description of information-lossless automata [24]. A number of results concerning the problem under consideration are presented by the author in [31-35]. 5 On reconstruction of information on an automaton input word by the corresponding output word 5.1 Setting of the problem In what follows, Тk is the set of all k-length output words A(s,Р) of the automaton A corresponding to the input word PXk and the initial state sS, Rk=Xk, Нk(s,Р)=A(s,Р), Пk(s,Р)=Р. Such an observation depends on the parameter k. From a cryptographic point of view, this naturally gives rise to the question whether there exists a natural k for which the given automaton А=(Х,S,Y,h,f) is under the observation (k,Т k,Rk,Нk,Пk). In the case of positive answer to this question, one naturally comes to the further problem of the upper estimate for such a minimum k. If there is no such k, then the cipher that is modeled by such an automaton is particularly valuable. In order to describe the classes of automata under the effective observation (k,Тk,Rk,Нk,Пk)=(Rk=Xk,Пk(s,Р)=Р, Нk(s,Р)=A(s,Р)) and the automata for which there is no effective observation, we introduce the following notions and notation. Denote by X* the set of all finite-length words over the alphabet X and by X∞ the set of all infinite words over the alphabet X. For the concatenation of words PXn, P”Xm, we write РP”, where Р is an initial subword of РP”. If n=0, then any word from Xn is considered to be empty and РP”=P”. For the subwords of P=x 1,x2,..., we use the notation: P1=P; Pn=xnxn+1... P]m=x1x2...xm Pn]m=xnxn+1...,xm n≤m; (P)k=PP…P k times. Define a number of binary relations on the sets X∞ and XL, L{1,2,…}. The relation σL on XL PσLP”  s,s”S: A(s,P)=A(s”,P”). The relation σ∞ on X∞ Pσ∞P”  s,s”S: A(s,P)=A(s”,P”). The relation σ∞]L on XL induced by the binary relation σ∞ P1σ∞]LP2  P,P”X∞: Pσ∞P”, P]L=P1, P”]L=P2. Denote by (σ∞)*, (σ∞]L)*, (σL)* the transitive closures of the binary relations σ∞, σ∞]L, σL. For the binary relation τ{(σ∞), (σ∞]L), (σL)}, denote by rang τ the number of equivalence classes under the binary equivalence relation τ*and by t(τ) the minimum L for which rang(σL)*>1 (rang(σ∞]L)*>1). Otherwise, set t((σL)*)=∞ (t((σ∞]L)*)=∞). The introduced parameters are called the degrees of the transitive binary relations σL, σ∞]L, respectively. The next proposition follows from Theorem 2. Proposition 1. The automaton A is under the effective observation (k, R k=Xk, Пk(s,Р)=Р, Нk(s,Р)=A(s,Р)) if and only if rang(σk)>1. 5.2 The class of automata without effective observation The class of automata with the loss of information (B1 type) and without effective observation. Now let us turn to the description of the automaton classes for which the observation (k, Rk=Xk, Пk(s,Р)=Р, Нk(s,Р)=A(s,Р)) is not effective for any k. Definition 5. An automaton А=(Х,S,Y,h,f) is said to be an automaton with the | S | (| S | 1) loss of information B1 if for L   1 there exists a binary 2 relation ε on the set X with the following properties: 1) For each pair (x,x”) from ε there exist P,P” from X L and sS such that A(s,xP)=A(s,x”P”); 2) The binary relation ε is transitive on the set X. Theorem 3. If a permutation automaton A is an automaton with the loss of information (B1 type), then its observation (k, R k=Xk, Пk(s,Р)=Р, Нk(s,Р)=A(s,Р)) is not effective for any k. Proof. Suppose the conditions of the theorem are satisfied. Let us first prove that the theorem conditions imply the following: for any pair (x,x”)ε and any word PX* there exist Q, Q”X∞ such that PxQσ∞Px”Q”. Indeed, suppose there is a pair (x,x”)ε. Then there exist automaton input words P=p 1p2…pL, P”=p”1p”2…p”L and an initial state sS such that A(s,xP)=A(s,x”P”). In the transition graph of the automaton, the words P, P” are represented as the paths from the initial state sS passing through the states s, hp1 s, hp2 hp1 s,..., hpL ...hp2 hp1 s and s, hp "1 s, hp "2 hp "1 s,..., hp "L ...hp "2 hp "1 s , respectively. The two following cases are possible: 1) there exists a pair of states (hp j ...hp2 hp1 s, hp " j ...hp "2 hp "1 s) such that hp j ...hp2 hp1 s  hp " j ...hp "2 hp "1 s , 2) the states in each pair of states (hp j ...hp2 hp1 s, hp " j ...hp "2 hp "1 s) , j{1,2,…L} are different. By standard methods of graph theory, it can be shown that in each of the cases 1), 2) Pxσ∞]k+1Px” for any k{0,1,…}, PXk, and (x,x”)ε. In particular, xσ∞]1x”. Hence, rang(σ∞]1)*=1. Thus we obtain rang (σ1)*=1 on X1. Assume that for some K, rang(σ∞]K)*=1. Then let us prove that rang(σ∞]K+1)*=1. By the assumption, it follows that there exists a chain of binary relations P1σ∞]KP2σ∞]KP3…σ∞]KPN, N≥|X|K that contains all the words from XK. From the definition of the binary relation σ∞]K on XK it follows that ∃αj,βjX: Pjαj σ∞]K+1 Pj+1βj, j{1,2,…,N}. To complete the proof of transitivity of the binary relation σ ∞]K on XK for any K, we introduce the binary relation ε(Q) on the set of words {Qx: xX}, where Q is an arbitrary finite word of length K over the alphabet X. Let ε(Q) be a subset of the set (XK)2 that consists of all the pairs (Qx,Qx”), where (x,x”)ε. Lemma 1. The binary relation ε(Q) on the set of words {Qx: x X}, where QXK, is transitive. Proof. For the automaton A, fix all the triples (s,x,x”) with the property: for each pair (x,x”) from ε there exist P, P” from X∞ and sS such that A(s,xP)=A(s,x”P”). Since the automaton A is a permutation automaton, it follows that for any triple (s,x,x”) and any automaton input word Q there exists a state s Q such that hQsQ=s. It is obvious that A(sQ,Qx)=A(sQ,Qx”). For this reason, and by virtue of transitivity of the binary relation ε, the binary relation ε(Q) is transitive. Thus Lemma 1 is proved. □ Since the set of words XK+1 is divided into disjoint subsets ε(Q), QXK, on each of which the binary relation ε is transitive, and the subsets are related by (2), the induction step is carried out. We now note that the transitivity of the binary relation σ∞]K+1 on XK+1 implies the transitivity of the binary relation σK+1 on XK+1. □ The class of automata with the loss of information (B2 type) and without effective observation. Definition 6. An automaton А=(Х,S,Y,h,f) is said to be an automaton with the | S | (| S | 1) loss of information (B2 type) if for L  | S | there exists a 2 binary relation ε on the set X with the following properties: 1) For each pair (x’,x”) from ε there exist P’,P” from XL and s, s”S such that A(s,P’x)=A(s”,P”x”), hP ' x ' s  hP " x "s " . 2) The binary relation ε is transitive on the set X. Theorem 4. If an automaton А=(Х,S,Y,h,f) is an automaton with the loss of information (B2 type), then its observation (k, R k=Xk, Пk(s,Р)=Р, Нk(s,Р)=A(s,Р)) is not effective for any k. Proof. Suppose that for L=0, XL consists of an empty word. We will use the previously introduced notation σL of the binary relation on XL. Denote by  ( L) the new binary relation on XL, P’  ( L) P”   words P1’, P1” X N1 N2 , P2’, P2” X , where N1=N1(P’,P”)≥1, N2=N2(P’,P”)≥0: k≥1 it follows that (P1’)kP2’P’  kN  N  L 1 2 (P1”)kP2”P”. Lemma 2. If А=(Х,S,Y,h,f) is an automaton with the loss of information (B2 type), then  x’,x”ε, PXL, L{0,1,2,…}: x’P  ( L  1) x”P. A(s,P’x)=A(s”,P”x”), hP ' x ' s  hP " x "s " . 2) The binary relation ε is transitive on the set X. 6 Discussion We note the universality of the approach to the study of useful (key) information of a finite automaton based on its possible observation. In this connection, the range of topical problems of finding information about the automaton of interest to the researcher can be significantly expanded. The question of existence of an algorithm recognizing the effective observation (k, Rk=Xk, Пk(s,Р)=Р, Нk(s,Р)=A(s,Р)) in the class of all automata remains opened. 7 Conclusion In this paper, we have introduced some novel notions of the automata-theoretic approach: observation over an automaton and an automaton under effective observation. The latter qualitatively reflects the presence of an automaton trapdoor for determining the information on an automaton input word by the observable information. For a given observation, we have proved the criterion of finding an automaton under effective observation. Also we have specified the classes of automata under effective observation and the classes of automata for which there is no effective observation. References 1. Simmons G J. The subliminal channel and digital signatures. EUROCRYPT’84, Lect. Notes Comput. Sci., 1985, v.209: 51-57. 2. Simmons G J. A secure subliminal channel (?). CRYPTO’85, Lect. Notes Comput. Sci., 1986, v.218: 33-41. 3. Simmons G J. Subliminal communication is easy using the DSA. EUROCRYPT’93, Lect. Notes Comput. Sci., 1994, v.765: 218-232. 4. Digital Signature Standard (DSS). Federal Information Processing Standard (FIPS) Publication 186, National Institute of Standards and Technology (NIST), US Department of Commerce, Washington D.C., December, 1998. 5. Young A, Yung M. The Dark Side of Black-Box Cryptography. CRYPTO’96, Lect. Notes Comput. Sci., 1997, v.1109: 89-103. 6. Young A, Yung M. Kleptography: using Cryptography against Cryptography. EUROCRYPT’97, Lect. Notes Comput. Sci., 1998, v.1233: 62-74. 7. Young A, Yung M. Monkey. Black-Box Symmetric Ciphers Designed for monopolizing keys. FSE’98, Lect. Notes Comput. Sci., 1998, v.1372: 122-133. 8. YongBin Zhou, DengGuo Feng. Side-Channel Attacks: Ten Years After Its Publication and the Impacts on Cryptographic Module Security Testing. 9. P. Kocher. Timing attacks on implementations of Diffie-Hellmann, RSA, DSS, and other systems. CRYPTO’96, LNCS, 1996, v.1109: 104-113. 10. J. Black, H. Urtubia. Side-channel attacks on symmetric encryption schemes: the case for authenticated encryption. In Proc of 11th USENIX Security Symposium, 2002, pp.327-338. 11. D. Boneh, R.A. DeMillo, R.J. Lipton. On the importance of checking cryptographic protocols for faults. EUROCRYPT'97, LNCS, 1997, v.1233: 37-51. 12. K. Gandolfi, C. Mourte, F. Olivier. Electromagnetic Analysis: Concrete Results. CHES 2001, LNCS, v.2162: 251-261. 13. J. J. Quisquater, D. Samyde. Electromagnetic analysis (EMA): measures and counter-measures for smart cards. E-smart 2001, LNCS, v.2140: 200–210. 14. M. G. Kuhn, R. J. Anderson. Soft tempest: hidden data transmission using electromagnetic emanations. Information Hiding 1998, LNCS, v.1525: 124-142. 15. M. Kuhn. Optical Time-Domain Eavesdropping Risks of CRT Displays. Proc of the 2002 Symposium on Security and Privacy, pp.3-18. 16. A. Shamir, E.Tramer. Acoustic cryptanalysis: on nosy people and noisy machines. In Eurocrypt 2004 rump session. 17. Y. Tsunoo, T. Saito, T. Suzaki, M. Shigeri, H. Miyauchi.Cryptanalysis of DES Implemented on Computers with Cache. CHES 2003, LNCS, v.2779: 62–76. 18. T. S. Messerges, E. A. Dabbish, R. H. Sloan, Examining smart-card security under the threat of power analysis attacks. IEEE Trans. Computers, 2002, 51(5): 541-552. 19. E. Biham, A. Shamir. Differential fault analysis of secret key cryptosystems. CRYPTO’97, LNCS, 1997, v.1294: 513-525. 20. C. Shannon. Raboti po teorii informacii i kibernetike (Works on information theory and cybernetics). Inostran. Lit., Moscow, 1963. 21. A. Gill. Introduction to the Theory of Finite-State Machines, McGraw-Hill Book Co., New York, 1962. 22. Huffman D A. Canonical forms for information-lossless finite-state logical machines. IRE Trans. Circuit Theory, 6, Spec. Suppl., 1959, 41-59. 23. Huffman D A. Notes on information-lossless finite-state automata. Nuovo cimento, 13, Suppl. 2, 1959, 397-405. 24. Even Sh. On information-lossless automata of finite order. IEEE Trans. Electronic Comput., 14, 1965, 4, 561-569. 25. Even Sh. Ob avtomatah konechnogo poryadka bez poteri informacii. Trudi mejdunarodnogo simpoziuma po teorii releinih ustroistv i konechnih avtomatov (On information-lossless automata of finite order. Proceedings of the International Symposium on the theory of relay devices and finite automata.). Moscow: Nauka, 1965, 269-279. 26. Kurmit A. A. Avtomati bez poteri informacii konechnogo poryadka (On information-lossless automata of finite order). Riga: Zinatne, 1972, 264. 27. Babash A. V. Ob eksperimentah po raspoznavaniyu informacii o vhodnom slove avtomata (On experiments on recognition of information on an automaton input word). Proceeding on Discrete Mathematics, v.8., Moscow: FIZMATLIT, 2004, pp.7-24. 28. Babash A. V. On Reconstruction of Information on an Input Word in a Medvedev Permutation Automaton Given Initial and Final States. Problems of Information Transmission, 2007, Vol. 43, No. 2, pp.132–142. 29. Bogomolov A.M., Barashko A.S., and Grunskii I.S., Eksperimenty s avtomatami (Experiments with Automata), Kiev: Naukova Dumka, 1973. 30. Tverdokhlebov V.A., Logicheskie eksperimenty s avtomatami (Logical Experiments with Automata), Saratov: Izd. Sarat. Univ., 1988. 31. Babash A. V. Neotlichimost sostoyanii konechnogo avtomata otnositelno funkcii, zadannoi na ego vhodnih i vihodnih slovah (Indistinguishability of finite automaton states for the function defined on its input and output words). Obozr. Prikl. Prom. Mat., 2001, vol. 8, no. 1, pp.94–95. 32. Babash A. V. On Some Invariants of a Finite Automaton. Obozr. Prikl. Prom. Mat., 2000, vol. 7, no. 1, pp.86–87. 33. Babash A. V., Local Reconstruction of Input Words of Automata Given the Initial and Final States. In Proc. 2nd All-Russian Symp. on Applied and Industrial Mathematics, Samara, 2001, pp.93–94. 34. Glukhov M. M., On Numerical Parameters Associated with the Definition of Finite Groups by Systems of Generating Elements. In Trudy po diskretnoi matematike (Proceedings in Discrete Mathematics), vol. 1, Moscow: TVP, 1997, pp.43–66. 35. Krapeˇz A., On a Generalization of Fermat’s Theorem in the Theory of Groups, Publ. Inst. Math.(Beograd) (N.S.), 1974, vol. 17(31): 77–81.