In this paper, we present a specific type of irreducible polynomial which is an irreducible m-term polynomial of degree m. Designing the parallel multiplier over GF(2m) by the quadrinomial obtained from this irreducible polynomial, its critical delay path is smaller than that of conventional multipliers for some degree m.

Cyber attacks targeting specific victims use multiple intrusion routes and various attack methods. In order to combat such diversified cyber attacks, Threat Intelligence is attracting attention. Attack activities, vulnerability information and other threat information are gathered, analyzed and organized in threat intelligence and it enables organizations to understand their risks. Integrated analysis of the threat information is needed to compose the threat intelligence. Threat information can be found in incident reports published by security vendors. However, it is difficult to analyze and compare their reports because they are described in various formats defined by each vendor. Therefore, in this paper, we apply a modeling framework for analyzing and deriving the relevance of the reports from the views of similarity and relation between the models. This paper presents the procedures of modeling incident information described in the reports. Moreover, as case studies, we apply the modeling method to some actual incident reports and compare their models.

A nonlinear combiner random number generator is a general keystream generator for certain stream ciphers. The generator is composed of several linear feedback shift registers and a nonlinear function; the output is used as a keystream. A fast correlation attack is a typical attack for such keystream generators. Mihaljevi, Fossorier, and Imai have proposed an improved fast correlation attack. The attack is based on error correction of information bits only in the corresponding binary linear block code; APP threshold decoding is employed for the error correction procedure. In this letter, we propose a method which improves the success rate of their attacks with similar complexity. The method adds some intentional error to original parity check equations. Those equations are then used in APP threshold decoding.

Spritz is a stream cipher proposed by Rivest and Schuldt at the rump session of CRYPTO 2014. It is intended to be a replacement of the popular RC4 stream cipher. In this paper we propose distinguishing attacks on the full Spritz, based on a short-term bias in the first two bytes of a keystream and a long-term bias in the first two bytes of every cycle of N keystream bytes, where N is the size of the internal permutation. Our attacks are able to distinguish a keystream of the full Spritz from a random sequence with samples of first two bytes produced by 244.8 multiple key-IV pairs or 260.8 keystream bytes produced by a single key-IV pair. These biases are also useful in the event of plaintext recovery in a broadcast attack. In the second part of the paper, we look at a state recovery attack on Spritz, in a special situation when the cipher enters a class of weak states. We determine the probability of encountering such a state, and demonstrate a state recovery algorithm that betters the 21400 step algorithm of Ankele et al. at Latincrypt 2015. Finally we propose a simple fix that removes the bias in the first two keystream bytes. The countermeasure requires only one additional memory access and hence does not diminish software performance substantially, and in fact the loss in software speed is only around 1.5%.

TPM-embedded devices can be used as authentication tokens by issuing certificates to signing keys generated by TPM. TPM generates Attestation Identity Key (AIK) and Binding Key (BK) that are RSA keys. AIK is used to identify TPM. BK is used to encrypt data so that specific TPM can decrypt it. TPM can use for device authentication by linking a SSL client certificate to TPM. This paper proposes a method of an AIK certificate issuance with OpenID and a method of the SSL client certificate issuance to specific TPM using AIK and BK. In addition, the paper shows how to implement device authentication system using the SSL client certificate related to TPM.

The network load is increasing due to the spread of content distribution services. Caching is known as a technique to reduce a peak network load by prefetching popular contents into memories of users. Coded caching is a new caching approach based on a carefully designed content placement in order to create coded multicasting opportunities. Recent works have discussed single-layer caching systems, but many networks consist of multiple layers of cache. In this paper, we discuss a coded caching problem for a hierarchical network that has a different number of layers of cache. The network has users who connect to an origin server via a mirror server and users who directly connect to the origin server. We provide lower bounds of the rates for this problem setting based on the cut-set bound. In addition, we propose three basic coded caching schemes and characterize these schemes. Also, we propose a new coded caching scheme by combining two basic schemes and provide achievable rates of the combination coded caching scheme. Finally, we show that the proposed combination scheme demonstrates a good performance by a numerical result.

It is important that efficient squaring algorithm is improved since inversion and exponentiation in GF(2m) can be generally decomposed into squaring and multiplying algorithm. In this letter we give a bit-serial squarer in GF(2m) when using polynomial basis representation for the elements.

In this paper, we propose two new falsification attacks against Wi-Fi Protected Access Temporal Key Integrity Protocol (WPA-TKIP). A previous realistic attack succeeds only for a network that supports IEEE 802.11e QoS features by both an access point (AP) and a client, and it has an execution time of 12–15 min, in which it recovers a message integrity code (MIC) key from an ARP packet. Our first attack reduces the execution time for recovering a MIC key. It can recover the MIC key within 7–8 min. Our second attack expands its targets that can be attacked. This attack focuses on a new vulnerability of QoS packet processing, and this vulnerability can remove the condition that the AP supports IEEE 802.11e. In addition, we discovered another vulnerability by which our attack succeeds under the condition that the chipset of the client supports IEEE 802.11e even if the client disables this standard through the OS. We demonstrate that chipsets developed by several kinds of vendors have the same vulnerability.

After the disclosure of the RC4 algorithm in 1994, a number of keystream biases of RC4 were reported, e.g., Mantin and Shamir showed that the second byte of the keystream is biased to 0, Sepehrdad et al. found that the l-th byte of the keystream is biased to -l, and Maitra et al. showed that 3rd to 255th bytes of the keystream are also biased to 0, where l is the keylength in byte. However, it is unknown that which bias is strongest in each byte of initial bytes. This paper comprehensively analyzes initial keystream biases of RC4. In particular, we introduce several new biases in the initial (1st to 257th) bytes of the RC4 keystream, which are substantially stronger than known biases. Combining the new biases with the known ones, a complete list of strongest single-byte biases in the first 257bytes of the RC4 keystream is constructed for the first time. Then, we show that our set of these biases are applicable to plaintext recovery attacks, key recovery attacks and distinguishing attacks.

Malicious software (malware) poses various significant challenges. One is the need to retrieve plain-text messages transmitted between malware and herders through an encrypted network channel. Those messages (e.g., commands for malware) can be a useful hint to reveal their malicious activities. However, the retrieving is challenging even if the malware is executed on an analysis computer. To assist analysts in retrieving the plain-text from the memory, this paper presents FCReducer(Function Candidate Reducer), which provides a small candidate set of cryptographic functions called by malware. Given this set, an analyst checks candidates to locate cryptographic functions. If the decryption function is found, she then obtains its output as the plain-text. Although existing systems such as CipherXRay have been proposed to locate cryptographic functions, they heavily rely on fine-grained dynamic taint analysis (DTA). This makes them weak against under-tainting, which means failure of tracking data propagation. To overcome under-tainting, FCReducer conducts coarse-grained DTA and generates a typical data dependency graph of functions in which the root function accesses an encrypted message. This does not require fine-grained DTA. FCReducer then applies a community detection method such as InfoMap to the graph for detecting a community of functions that plays a role in decryption or encryption. The functions in this community are provided as candidates. With experiments using 12 samples including four malware specimens, we confirmed that FCReducer reduced, for example, 4830 functions called by Zeus malware to 0.87% as candidates. We also propose a heuristic to reduce candidates more greatly.

Conventional class of weak keys on RC4 stream cipher is defined as a specific case that combinations of the first three bytes of secret key satisfy two relational equations. This paper expands and generalizes the classes of weak keys using generalized relational equations and special classes of the internal state (called predictive state). We derive the probability that generalized classes of weak keys leak the information of bytes of the secret key. Furthermore, we enumerate the generalized classes of weak keys and show that most of them leak more information of the secret key than Roos' one.

We focus on the construction of the digital signature scheme for local broadcast, which allows the devices with limited resources to securely transmit broadcast message. A multi-group authentication scheme that enables a node to authenticate its membership in multi verifiers by the sum of the secret keys has been proposed for limited resources. This paper presents a transformation which converts a multi-group authentication into a multi-group signature scheme. We show that the multi-group signature scheme converted by our transformation is existentially unforgeable against chosen message attacks (EUF-CMA secure) in the random oracle model if the multi-group authentication scheme is secure against impersonation under passive attacks (IMP-PA secure). In the multi-group signature scheme, a sender can sign a message by the secret keys which multiple certification authorities issue and the signature can validate the authenticity and integrity of the message to multiple verifiers. As a specific configuration example, we show the example in which the multi-group signature scheme by converting an error correcting code-based multi-group authentication scheme.

In this paper, we propose an algorithm to calculate the higher moments of the busy period length of a discrete-time M/G/1 type queue with finite buffer. The queueing model has a level-dependent transition probability matrix. Our algorithm is given as a set of recursive formulas which are derived from the relationship among the generating function matrices of the fundamental period. As an example of our algorithm, we provide an approximate analysis of a HOL (Head Of Line) priority control queue.

In this letter we present an efficient root finding technique for a polynomial over GF(2m) when m is even number. The solutions that we have ever known are made to accelerate by our technique.

Quick Response (QR) code is a two dimensional barcode widely used in many applications. A standard QR code consists of black and white square modules, and it appears randomized patterns. By modifying the modules using certain rule, it is possible to display a logo image on the QR code. Such a QR code is called an aesthetic QR code. In this paper, we change the encoding method of the Reed-Solomon (RS) code to produce an aesthetic QR code without sacrificing its error correcting capability. The proposed method randomly produces candidates of RS blocks and finds the best one during encoding. Considering an image to be displayed, we also introduce a weighting function during random selection that classifies the visually important regions in the image. We further investigate the shape of modules which represents the image and consider the trade-off between the visual quality and its readability. As a result, we can produce a beautiful aesthetic QR code, which still can be decoded by standard QR code reader.

In a key scheduling algorithm (KSA) of stream ciphers, a secret key is expanded into a large initial state. An internal state reconstruction method is known as a general attack against stream ciphers; it recovers the initial state from a given pair of plaintext and ciphertext more efficiently than exhaustive key search. If the method succeeds, then it is desirable that the inverse of KSA is infeasible in order to avoid the leakage of the secret key information. This paper shows that it is easy to compute a secret key from an initial state of RC4. We propose a method to recover an -bit secret key from only the first bits of the initial state of RC4 using linear equations with the time complexity less than that of one execution of KSA. It can recover the secret keys of which number is 2103.6 when the size of the secret key is 128 bits. That is, the 128-bit secret key can be recovered with a high probability when the first 128 bits of the initial state are determined using the internal state reconstruction method.

Cassuto and Blaum presented a new coding framework for channels whose outputs are overlapping pairs of symbols in storage applications. Such channels are called symbol-pair read channels. Pair distance and pair error are used in symbol-pair read channels. Yaakobi et al. proved a lower bound on the minimum pair distance of cyclic codes. Furthermore, they provided a decoding algorithm for correcting pair errors using a decoder for cyclic codes, and showed the number of pair errors that can be corrected by their algorithm. However, their algorithm cannot correct all pair error vectors within half of the minimum pair distance. In this paper, we propose an efficient decoding algorithm for cyclic codes over symbol-pair read channels. It is based on the relationship between pair errors and syndromes. In addition, we show that the proposed algorithm can correct more pair errors than Yaakobi's algorithm.

Lee and Kwon proposed an anonymous authentication scheme based on Zhu et al.'s scheme. However, Lee et al.'s scheme has two disadvantages. Firstly, their scheme is vulnerable to off-line dictionary attacks. An adversary can guess a user password from the user's login messages eavesdropped by the adversary. Secondly, an authentication server called a home agent requires a verification table, which violates the original advantage of Zhu et al.'s scheme. That is, it increases the key management costs of the home agent. In this letter, we show the weaknesses of Lee et al.'s scheme and another three existing schemes. Then, we propose a new secure scheme without the verification table, while providing security for off-line dictionary attacks and other attacks except for a certain type of combined attacks.

This paper describes an efficient and simple coding algorithm of universally optimal codes for stationary (ergodic) sources and noiseless channel with unequal symbol costs. The symbol cost indicates the required time (or space) for the transmission (or storage) of that symbol, and the cost of any code symbol depends only on that symbol. The proposed coding algorithm mainly consists of two parts. The first part is based on the well-known Ziv-Lempel coding algorighm proposed in 1978 (sometimes called LZ78), and the second part is based on the Varn coding algorithm. The coding algorithm asymptotically achieves an optimal average cost of codes for stationary sources, and also achieves an optimal cost of codes for stationary ergodic sources with probability one. Furthermore, the computational complexity of the proposed coding algorithm is linear with respect to the length of source sequence and coded sequence.

Digital fingerprinting is used to trace back illegal users, where unique ID known as digital fingerprints is embedded into a content before distribution. On the generation of such fingerprints, one of the important properties is collusion-resistance. Binary codes for fingerprinting with a code length of theoretically minimum order were proposed by Tardos, and the related works mainly focused on the reduction of the code length were presented. In this paper, we present a concrete and systematic construction of the Tardos's fingerprinting code using a chaotic map. Using a statistical model for correlation scores, the actual number of true-positive and false-positive detection is measured. The collusion-resistance of the generated fingerprinting codes is evaluated by a computer simulation.