To develop countermeasures against fault attacks, it is important to model an attacker's ability. The instruction skip model is a well-studied practical model for fault attacks on software. Contrastingly, few studies have investigated the instruction replacement model, which is a generalization of the instruction skip model, because replacing an instruction with a desired one is considered difficult. Some previous studies have reported successful instruction replacements; however, those studies concluded that such instruction replacements are not practical attacks because the outcomes of the replacements are uncontrollable. This paper proposes the concept of a controllable instruction replacement technique that uses the laser irradiation of flash memory. The feasibility of the proposed technique is demonstrated experimentally using a smartcard-type ARM SC100 microcontroller. Then, practical cryptosystem attacks that exploit the proposed technique are investigated. The targeted cryptosystems employ the AES with software-based anti-fault countermeasures. We demonstrate that an existing anti-instruction-skip countermeasure can be circumvented by replacing a critical instruction, e.g., a branch instruction to detect fault occurrence.

A function can be represented in many ways. A representation O of a function f is called 'obscure' if O is different from the representation D used as the definition of f and if it is (or, seems to be) computationally infeasible to get D from O. Such an obscure representation is useful for cryptographic techniques so that it is important to estimate its descriptive and executive complexity. We present a complexity-estimation method for certain functions used to constructing asymmetric cryptosystems. Let m be a positive integer and let K, Km, and L denote the field {0, 1}, the set of all m-tuples over K, and an extention field or order m over K, respectively. The objective function is a composit g:Km Km of three functions s, e, and t, where s:Km L and t:L Km are affine and e:L L is defined by a univariate polynomial e over L. The obscure representation of g is an m-tuple g of m-variate polynomials over K. The complexity respect to g is well measured by its degree. So we give a theorem for estimating the degree of g in terms of a characteristic quantity of the polynomial e.

To utilize the common-key encryption foe the message protection in a communication network, it is desired to settle the problem of how to distribute the common keys. This paper discusses a sort of schemes (the direct schemes, we call) that smartly provide different keys in different communications. Such a property has not attained via the basic scheme for the public key distribution systems proposed by Diffie and Hellman. This paper shows that the recently introduced five direct schemes are classified into three sets (called sequences) of infinite schemes, and points out that there are some tight relations among the sequences. And it is clarified which is the best in the three sequences by a systematic evaluation of the complexities for the normal update and for the deliberate forgery of the shared common keys.

Let γ and n be positive integers. An integer z with gcd(z, n)1 is called a γth-residue mod n if there exists an integer x such that zxγ (mode n), or a γth-nonresidue mod n if there doesn't exist such an x. Denote by Z*n the set of integers relatively prime to n between 0 and n. The problem of determining whether or not a randomly selected element zZ*n is a γth-residue mod n is called the γth-Residuosity Problem (γth-RP), and appears to be intractable when n is a composite integer whose factorization is unknown. In this paper, we explore some important properties of γth-RP for the case where γ is an odd integer greater than 2, and discuss its applications to cryptography. Based on the difficulty or γth-RP, we generalize the Goldwasser-Micali bit-by-bit probabilistic encryption to a block-by-block probabilistic one, and propose a direct protocol for the dice casting problem over a network. This problem is a general one which includes the well-studied coin flipping problem.

The time-memory trade-off cryptanalysis for block ciphers with a search space of size 2N (N: key length) cannot achieve a success probability excceding 63%. This is caused by some unavoidable overlapping of keys in the space. For elavating the success probability of finding the correct key, a larger search space is necessary. That is, the increase of time complexity for precomputation would be inevitable. This paper theoretically shows, however, no further price is required for the size of look-up tables for the number of encryptions for searching for the key that matches the given ciphertext - plaintext pairs. This theory is confirmed by some empilical results.

Fingerprinting is a technique to add identifying marks to each copy of digital contents in order to enhance traceability to a distribution system. Collusion attacks, in which the attackers collect two or more fingerprinted copies and try to generate an untraceable copy, are considered to be a threat for the fingerprinting system. With the aim of enhancing collusion security to the fingerprinting system, several collusion secure codes, such as c-frameproof code, c-secure frameproof code and c-identifiable parent property code, have been proposed. Here, c indicates the maximum number of colluding users. However, a practical construction of the above codes is still an issue because of the tight restrictions originated from their combinatorial properties. In this paper, we introduce an evaluation of frameproof, secure frameproof, and identifiable parent property by the probability that a code has the required property. Then, we focus on random codes. For frameproof and secure frameproof properties, we estimate the average probability that random codes have the required property where the probability is taken over the random construction of codes and random construction of coalitions. For the estimation, we assume the uniform distribution of symbols of random codes and the symbols that the coalitions hold. Therefore, we clarify the adequacy of the assumptions by comparison with numerical results. The estimates and numerical results resemble, which implies the adequacy of the assumption at least in the range of the experiment.

This paper describes a modular exponentiation processing method and circuit architecture that can exhibit the maximum performance of FPGA resources. The modular exponentiation architecture proposed by us comprises three main techniques. The first one is to improve the Montgomery multiplication algorithm in order to maximize the performance of the multiplication unit in an FPGA. The second one is to balance and improve the circuit delay. The third one is to ensure scalability of the circuit. Our architecture can perform fast operations using small-scale resources; in particular, it can complete a 512-bit modular exponentiation as fast as in 0.26 ms with the smallest Virtex-4 FPGA, XC4VF12-10SF363. In fact the number of SLICEs used is approx. 4200, which proves the compactness of our design. Moreover, the scalability of our design also allows 1024-, 1536-, and 2048-bit modular exponentiations to be processed in the same circuit.

S(ubstitution)-boxes are quite important components of modern symmetric cryptosystems. S-boxes bring nonlinearity to cryptosystems and strengthen their cryptographic security. An S-box satisfies the strict avalanche criterion (SAC), if and only if for any single input bit of the S-box, the inversion of it changes each output bit with probability one half. This paper presents some interesting properties of S-boxes and proposes an efficient and systematic means of generating arbitrary input size bijective S-boxes satisfying SAC.

In this paper we first demonstrate that effective selection functions in power analysis attacks change depending on circuit architectures of a block cipher. We then conclude that the most resistant architecture on its own, in the case of the loop architecture, has two data registers have separate roles: one for storing the plaintext and ciphertext, and the other for storing intermediate values. There, the pre-whitening operation is placed at the output of the former register. The architecture allows the narrowest range of selection functions and thereby has resistance against ordinary CPA. Thus, we can easily defend against attacks by ordinary CPA at the architectural level, whereas we cannot against DPA. Secondly, we propose a new technique called "self-templates" in order to raise the accuracy of evaluation of DPA-based attacks. Self-templates enable to differentiate meaningful selection functions for DPA-based attacks without any strong assumption as in the template attack. We also present the results of attacks to an AES co-processor on an ASIC and demonstrate the effectiveness of the proposed technique.

PUF (Physically Unclonable Function) technologies attract attention as a candidate to prevent counterfeit chips. A latch PUF is known as a high performance PUF among various types of proposed PUFs. In this paper we describe an experiment on a invasive attack to a latch PUF consisting of RS latches, such as measuring the latch output by a probe contact after a FIB (Focused Ion Beam) processing. As a result, we confirmed that the latch PUF has a tolerance for the dynamic analysis, because the RS latch output was influenced and changed after the FIB processing in our experiments.

This paper presents two methods for securely realizing caller-authenticated and callee-specified calls over telecommunication networks with terminals that accept IC cards having KPS-based cryptographic functions. In the proposed protocols, users can verify that the partner is the proper owner of a certain ID or a certain pen name. Users' privacy is protected even if they do the caller-authenticated and callee-specified calls and do not pay their telephone charge in advance.

Steganography is a technique that conceals the very existence of communication by means of hiding secret messages in innocuous cover objects. We previously developed a steganographic method that uses standard MIDI files (SMFs) as cover objects. Our method could conceal the secret messages in SMFs without changing their sound. We also investigated the effectiveness of our method against steganalysis. This steganalytic research revealed that files embedded using our method are vulnerable to detection, because stego SMFs lose the imprints borne by sequencers. In this study, we describe two improved methods of steganography that enable even stego SMFs to keep the sequencer's imprint. As a result, we improved the resistance of SMFs against steganalysis but there was a slight reduction in the embedding rate.

Password checking schemes are human identification methods commonly adopted in many information systems. One of their disadvantages is that an attacker who correctly observed an input password can impersonate the corresponding user freely. To overcome it there have been proposed interactive human identification schemes. Namely, a human prover who has a secret key is asked a question by a machine verifier, who then checks if an answer from the prover matches the question with respect to the key. This letter examines such a scheme that requires relatively less efforts to human provers. By computer experiments this letter evaluates its resistance against a type of attack; after observing several pairs of questions and correct answers how successfully can an attacker answer the next question?

A challenge-and-response type identification protocol consists of three moves of messages between a prover and a verifier: Move-1--The prover claims to the verifier that his/her identity is ID. Move-2--The verifier challenges the prover with a question related to the ID. Move-3--The prover responds with the answer of the question. The verifier accepts the prover if the answer is correct. The main contribution of this paper is to show that the folklore can be made provably secure under the sole assumption of the existence of one-way functions.

An extension of the notion of cryptographically strong pseudo-random generator to a distributed setting is proposed in this paper. Instead of a deterministic function to generate a pseudo-random bit string from a truly random shorter string, we have a deterministic secure protocol for a group of separate entities to compute a secretly shared pseudo-random string from a secretly shared and truly random shorter string. We propose a precise definition of this notion in terms of Yao's computational entropy and describe a concrete construction using Shamir's pseudo-random number generator. Several practical applications are also discussed.

A design methodology of Random Switching Logic (RSL) using CMOS standard cell libraries is proposed to counter power analysis attacks against cryptographic hardware modules. The original RSL proposed in 2004 requires a unique RSL-gate for random data masking and glitch suppression to prevent secret information leakage through power traces. In contrast, our new methodology enables to use general logic gates supported by standard cell libraries. In order to evaluate its practical performance in hardware size and speed as well as resistance against power analysis attacks, an AES circuit with the RSL technique was implemented as a cryptographic LSI using 130-nm and 90-nm CMOS standard cell library. From the results of attack experiments that used a million traces, we confirmed that the RSL-AES circuit has very high DPA and CPA resistance thanks to the contributions of both the masking function and the glitch suppressing function.

Anonymous communication essentially involves two difficulties; 1) How does the sender send a message anonymously? 2) How does the receiver send a reply to the anonymous sender? In this paper, we propose an anonymous communication method named Rivulet that overcomes both of the difficulties by using group communication. Moreover, anonymous communication holds two dilemmas; 1) Strong anonymity or good performance? 2) Protect the privacy or promote the crime? Rivulet provides a solution for the former dilemma. The latter one is hard and important problem for all privacy protection schemes, therefore, we have to keep discussing this dilemma.

We describe a scheme of secret communication over the Internet utilizing the potentiality of the TCP/IP protocol suite in a non-standard way. Except for the sender and the receiver of the secret communication it does not need any entities installed with special software. Moreover it does not require them to share any key beforehand. Such features of the scheme stem from the use of IP datagrams with spoofed source addresses and their related error messages for the Internet Control Message Protocol (ICMP) induced by artificial faults. Countermeasures against IP spoofing are deployed in various places since it is often used together with attacks such as distributed denial of service (DDoS) and SPAM mailing. Thus we examine the environment where the scheme works as an intention and also clarify the conditions to obsolete the scheme. Furthermore we estimate the amount of secretly communicated data by the scheme and storage requirements for the receivers and those for the observers who monitor the traffic to detect the very existence of such a secret communication. We also discuss various issues including the sender anonymity achieved by the scheme.

In this paper, we formally define and analyze the security notions of authenticated encryption in unconditional security setting. For confidentiality, we define the notions, APS (almost perfect secrecy) and NM (non-malleability), in terms of an information-theoretic viewpoint along with our model where multiple senders and receivers exist. For authenticity, we define the notions, IntC (integrity of ciphertexts) and IntP (integrity of plaintexts), from a view point of information theory. And then we combine the above notions to define the security notions of unconditionally secure authenticated encryption. Then, we analyze relations among the security notions. In particular, it is shown that the strongest security notion is the combined notion of APS and IntC. Finally, we formally define and analyze the following generic composition methods in the unconditional security setting along with our model: Encrypt-and-Sign, Sign-then-Encrypt and Encrypt-then-Sign. Consequently, it is shown that: the Encrypt-and-Sign composition method is not always secure; the Sign-then-Encrypt composition method is not always secure; and the Encrypt-then-Sign composition method is always secure, if a given encryption meets APS and a given signature is secure.

Recently, criminals frequently utilize logical attacks to Automated Teller Machines (ATMs) and financial institutes' (FIs') networks to steal cash. We proposed a security measure utilizing peripheral devices in an ATM for smart card transactions to prevent “unauthorized cash withdrawals” of logical attacks, and the fundamental framework as a generalized model of the measure in other paper. As the measure can prevent those logical attacks with tamper-proof hardware, it is quite difficult for criminals to compromise the measure. However, criminals can still carry out different types of logical attacks to ATMs, such as “unauthorized deposit”, to steal cash. In this paper, we propose a security measure utilizing peripheral devices to prevent unauthorized deposits with a smart card. The measure needs to protect multiple transaction sub-processes in a deposit transaction from multiple types of logical attacks and to be harmonized with existing ATM system/operations. A suitable implementation of the fundamental framework is required for the measure and such implementation design is confusing due to many items to be considered. Thus, the measure also provides an implementation model analysis of the fundamental framework to derive suitable implementation for each defense point in a deposit transaction. Two types of measure implementation are derived as the result of the analysis.