JP7700960B2 - Information processing device, method and program - Google Patents

Description

The present disclosure relates to an information processing device, method, and program.

Generally, cryptographic technologies are designed to ensure security against black-box attacks. A black-box attack is one in which the attacker is able to learn the input/output pairs of encryption and decryption functions. On the other hand, a white-box attack is one in which the attacker is able to see not only the input/output pairs but also the contents of the software that implements the encryption and decryption functions. Security against black-box attacks is also called "black-box security," and security (to a certain extent) against white-box attacks is also called "white-box security."

Cryptography is primarily a technique for obtaining confidentiality, but in recent years, techniques for obtaining authenticity as well as confidentiality have also become important. A known technique for obtaining authenticity is the Message Authentication Code (MAC). Also known as a technique for obtaining both confidentiality and authenticity at the same time is Authenticated Encryption with Associated Data (AEAD) (see, for example, Non-Patent Document 1, etc.). AEAD is often constructed by combining a common key cipher, such as CTR or CBC, with a message authentication code.

Phillip Rogaway and Thomas Shrimpton. A provable-security treatment of the key-wrap problem. In Serge Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings, Vol. 4004 of Lecture Notes in Computer Science, pp. 373-390. Springer, 2006.

However, no white-box secure AEAD has existed to date. On the other hand, many AEADs can be constructed by combining a symmetric key cipher and a message authentication code. Therefore, if a white-box secure message authentication code can be realized, it can be combined with a white-box secure symmetric key cipher to construct a white-box secure AEAD.

This disclosure has been made in consideration of the above points and provides a technology for realizing white-box secure message authentication codes.

An information processing device according to one aspect of the present disclosure has a tag generation unit configured to generate a tag T = _MAC1K (X) for verifying the authenticity of data X by using a tag generation function _MAC1K (where K is a key) of a message authentication code that is secure against white-box attacks, and the tag generation function _MAC1K is configured using an encryption function _EK of a block cipher that is secure against white-box attacks and has an input/output length of n bits, a predetermined hash function H whose output length is m ≥ 2n bits, and predetermined functions f1, f2: {0,1} ^m → {0,1} ⁿ and f3: {0,1} ⁿ × {0,1} ⁿ → {0,1} ⁿ .

A technique is provided for realizing white-box secure message authentication codes.

FIG. 13 is a diagram illustrating an example of an algorithm of a verification function. FIG. 1 is a diagram showing an example of an algorithm of an SIV encryption function. FIG. 13 is a diagram illustrating an example of the configuration of an encryption function of SIV. FIG. 13 is a diagram illustrating an example of an algorithm of a decoding function of SIV. FIG. 1 is a diagram illustrating an example of an algorithm for a tag generation function of a white-box secure message authentication code. FIG. 1 is a diagram illustrating an example of a white-box secure message authentication code. FIG. 1 is a diagram illustrating an example of the configuration of a communication system according to a first embodiment. FIG. 11 is a diagram illustrating an example of the configuration of a communication system according to a second embodiment. FIG. 2 illustrates an example of a hardware configuration of a computer.

Below, a first embodiment and a second embodiment of the present invention are described. In the first embodiment, a communication system 1 is described in which a white-box secure message authentication code is constructed, and then this message authentication code is used to enable data communication that satisfies authenticity. In the second embodiment, a communication system 1 is described in which an AEAD is constructed from the message authentication code constructed in the first embodiment, and this AEAD is used to enable data communication that satisfies confidentiality and authenticity.

The communication system 1 according to the first embodiment is applicable to various systems in which data communication occurs and authenticity needs to be guaranteed. Similarly, the communication system 1 according to the second embodiment is applicable to various systems in which data communication occurs and confidentiality and authenticity needs to be guaranteed.

[Preparation]
The terms, techniques, etc. used in the first and second embodiments will be described below.

Confidentiality and Authenticity
Important concepts in information security are confidentiality and authenticity. Confidentiality refers to a state in which a malicious attacker cannot illegally obtain information about data to be protected. Technologies to achieve confidentiality include symmetric key cryptography and public key cryptography. Authenticity refers to a state in which the data to be protected has not been illegally tampered with by an attacker, or a state in which an attacker cannot illegally fabricate data. Technologies to achieve authenticity include message authentication codes and digital signatures.

<Common key encryption technology>
A common key cryptography is an encryption technology in which users use a common secret key. For example, when a person encrypts data using the common key cryptography and sends it to another person, the same secret key must be used for encryption and decryption. Unlike public key cryptography such as RSA cryptography, common key cryptography cannot disclose (part of) the key. On the other hand, it has the advantage that it does not require algebraic problems such as prime factorization problems and is fast in processing. Many data protection technologies, including SSL/TLS, are realized by skillfully combining the advantages of both public key cryptography, which can disclose (part of) the key, and high-speed common key cryptography. Both public key cryptography and common key cryptography are indispensable as fundamental technologies for security. The first and second embodiments described below relate to common key cryptography.

In the following, the term "symmetric key cipher" refers to a symmetric key cipher in the narrow sense, whose main purpose is to protect confidentiality by encrypting data of various lengths. Examples of symmetric key ciphers in the narrow sense include confidentiality modes such as CTR mode and CBC mode, and stream ciphers such as KCipher-2. Note that block ciphers such as AES (Advanced Encryption Standard), Camellia, SPACE (Reference 1), and SPNBox (Reference 2) could also be classified as symmetric key ciphers in the narrow sense, but for the sake of explanation in this specification, "symmetric key cipher (in the narrow sense)" does not include block ciphers.

In recent years, symmetric key cryptography, which aims to provide not only confidentiality but also authenticity when encrypting data, has been widely used. Such cryptography is called authenticated cryptography or AEAD. Representative examples of AEAD include GCM, CCM, SIV (Synthetic Initialization Vector) (Non-Patent Document 1), etc. AEAD is often configured by combining a narrowly defined symmetric key cryptography with a message authentication code (MAC). Here, the message authentication code is a symmetric key cryptography technology that aims to provide only authenticity without considering confidentiality. The first embodiment described below relates to the message authentication code, and the second embodiment relates to the AEAD.

Below, we will explain in more detail about block ciphers, narrow symmetric key ciphers, message authentication codes, and AEADs. We will also explain cryptographic hash functions. Note that in this specification, all data and inputs and outputs of functions are represented as bit strings.

Block cipher A block cipher is a cipher E that takes a fixed-length (e.g., 256 bits) key K and a fixed-length (e.g., 128 bits) plaintext M as input, and outputs a ciphertext C of the same length as the plaintext. C = _EK (M) indicates that C is the ciphertext corresponding to M and K. _EK is also called an encryption function. A block cipher is required to be decryptable. In other words, there exists a decryption function _DK that restores the ciphertext to its original state, and _DK ( _EK (M)) = M holds for any plaintext M. Also, _DK ( _EK (C)) = C holds for any ciphertext C. Typical examples of block ciphers include AES and Camellia.

Note that even if there is a good block cipher that can securely encrypt short, fixed-length data, it is not obvious how to securely encrypt arbitrary-length data (especially long data).

Narrowly symmetric key encryption In this specification, the narrowly symmetric key encryption refers to an encryption E that takes a fixed-length key K, a fixed-length initial vector IV, and an arbitrary-length plaintext M as input, and outputs a ciphertext C. Here, the IV is a value that changes every time an encryption process is performed, in principle. The IV may be selected randomly for each encryption process. There are also methods that allow a single IV to be used repeatedly. In block encryption, M is a fixed length (e.g., 128 bits), but in narrowly symmetric key encryption, M is an arbitrary length, and for example, M may be 1 bit or 1 gigabyte. C = Enc _K (IV, M) is written to indicate that C is a ciphertext corresponding to (K, IV, M). Enc _K is also called an encryption function. As with block encryption, narrowly symmetric key encryption can also be decrypted. That is, there exists a decryption function Dec _K that restores the ciphertext to its original state, and Dec _K (IV, Enc _K (IV, M))=M holds for any plaintext M.

Common key encryption for encrypting plaintext of any length is often created using a block cipher. Configurations such as narrow common key encryption, message authentication code, and AEAD that use a block cipher are called block cipher usage modes, or simply modes. In modes, common key encryption techniques other than block ciphers may be used as necessary. In this specification, modes for creating narrow common key encryption are particularly called confidential modes. Typical examples of confidential modes include CTR mode and CBC mode.

Message Authentication Code (MAC)
A message authentication code is a function (tag generation function) MAC _K (M) that takes a fixed-length key K and a message M of any length as input and outputs a fixed-length output T called a tag. The function MAC K (M) takes (K, M, T) as input and generates the symbol

を出力する検証関数ＶＥＲ_Ｋ（Ｍ，Ｔ）とで構成される。ここで、

and a verification function VER _K (M, T) that outputs

は「ＴがＭとＫから生成された正当なタグである」ということを意味し、ＶＥＲ_Ｋ（Ｍ，Ｔ）＝⊥は「Ｔは不正に生成されたタグである」ということを意味する。安全なメッセージ認証符号は大雑把にいえば「秘密鍵Ｋを知っている者しか正当なＴの値を計算することはできない」、「異なるメッセージに対応するタグの値は異なる」という性質を満たし、不正な改ざんの検知（つまり、真正性の獲得）に用いることができる。

means that T is a valid tag generated from M and K, and VER _K (M, T) = ⊥ means that T is an illegally generated tag. Roughly speaking, a secure message authentication code satisfies the properties that only someone who knows the secret key K can calculate the valid value of T and that the tag values corresponding to different messages are different, and can be used to detect illegal tampering (i.e., to obtain authenticity).

In this specification, we consider only message authentication codes in which the verification function VER _K is calculated as shown in Algorithm 1 in Fig. 1. That is, the verification function VER _K takes a message M and a tag T as input, calculates T'←MAC _K (M) (line 1), and then outputs a symbol indicating that T is a valid tag if T'=T (lines 2-3), and otherwise outputs a symbol indicating that T is an invalid tag (lines 4-5).

As with symmetric key cryptography in the narrow sense, the tag generation function of a message authentication code may also be implemented using a block cipher (i.e., as a block cipher mode of operation). A typical example of a message authentication code in which the tag generation function is implemented as a block cipher mode of operation is CMAC.

・Authenticated Encryption (AEAD)
The encryption function E of the AEAD takes as input associated data A of any length in addition to (K, IV, M) that the narrow common key encryption takes as input. This encryption function E also outputs a tag T in addition to the ciphertext C. We write (T, C) = EK (IV, A, M) to indicate that (T, C) is the tag and ciphertext corresponding to ( _K , IV, A, M). As with the narrow common key encryption, there exists a decryption function _DK that returns the ciphertext to its original state, and _DK (IV, A, _EK (IV, A, M)) = M holds for any plaintext M.

The decryption function _DK of the AEAD has the function of detecting tampering, just like the verification function of the message authentication code. In other words, if the ciphertext C and the tag T are values that have been generated illegally, _DK outputs the symbol ⊥, which indicates that the verification has failed (i.e., _DK (IV, A, (T, C)) = ⊥). If T and C are values that have been calculated legitimately using the encryption function, the original message M is output as described above.

A secure AEAD protects confidentiality by converting a message M into a ciphertext C, and also protects against tampering and guarantees authenticity. An attacker cannot tell what the value of M is just by looking at C. On the other hand, confidentiality is not guaranteed for related data A. That is, roughly speaking, it is assumed that the value of A is not encrypted and is visible to an attacker. However, the authenticity of A is also guaranteed and it is protected against tampering. In other words, if A is tampered with to another value A' along the way, the decryption function fails to verify and D _K (IV, A', (T, C)) = ⊥. For this reason, A is data that does not need to be confidential but whose authenticity should be guaranteed (for example, the header of an IP packet).

AEAD is often constructed by combining a narrow common key cipher and a message authentication code. Representative examples of such a construction include GCM, CCM, SIV (Non-Patent Document 1), etc. For example, assume that a narrow common key cipher (Enc _K' , Dec _K' ) and a tag generation function MAC _K of the message authentication code are given. In this case, the encryption function E _{(K, K')} of SIV is defined, for example, by Algorithm 2 shown in FIG. 2. That is, the encryption function E _{(K, K')} of SIV takes (IV, A, M) as input, calculates T←MAC _K (pad(IV, A, M)) and C←Enc _K' (adj(T), M) (lines 1 and 2), and then outputs (T, C) (line 3). The encryption function E _{(K, K')} constructed in this way is shown in FIG. 3 as a schematic representation. Here, pad is a function that takes a triplet of bit strings (IV, A, M) as input and outputs a single bit string IV∥A∥M∥len(M). Note that x∥y represents the bit combination of two bit strings x and y, and len(M) represents the bit length of M as some bit string. Also, adj is a function that takes T, which is the output of MAC _K , as input, and adjusts the length to ν bits by truncating some bits of T or adding extra bits to T when the length of T (hereinafter, this length is referred to as τ bits) is different from the length of the IV used in Enc K _' and Dec _K' (hereinafter, this length is referred to as ν bits. Note that this IV is different from the IV that SIV takes as input). Specifically, when τ=ν, adj(T) outputs the input T as is. On the other hand, if τ>ν, then adj(T) outputs the lowest ν bits of the input T. Also, if τ<ν, then adj(T) outputs 0 ^ν-τ ∥T, where 0 ^ν-τ is a (ν-τ)-bit string in which all bits are 0.

Moreover, the SIV decryption function D _(K,K') is defined, for example, by Algorithm 3 shown in Fig. 4. That is, the SIV decryption function D _(K,K') takes (IV,A,T,C) as input, calculates M←Dec _K' (adj(T),C) and T'←MAC _K (pad(IV,A,M)) (lines 1 and 2), and then outputs M if T=T' (lines 3 and 4), and outputs ⊥ otherwise (lines 5 and 6).

Note that in Algorithm 2 shown in Figure 2 and Algorithm 3 shown in Figure 4, different independent keys (K and K') are used for MAC, Enc, and Dec, but K and K' may not be independent (i.e., K = K').

For convenience of explanation, there are some changes in Algorithm 2 shown in FIG. 2 and Algorithm 3 shown in FIG. 4 from the original paper (Non-Patent Document 1) in which the configuration of SIV was proposed. First, in the original paper, the IV is not taken as an input (it is considered as a part of A), but in Algorithm 2 shown in FIG. 2 and Algorithm 3 shown in FIG. 4, the IV is also taken as an input. Also, in the original paper, instead of combining MAC _K and pad, a pseudorandom function that can take a set of bit strings as input is used. For convenience of explanation, adj is also introduced in Algorithm 2 shown in FIG. 2 and Algorithm 3 shown in FIG. 4. The essence of SIV is "inputting (IV and) A and M to a keyed function, and using the output T instead of the IV of Enc _K' ", so the above changes do not change its essence.

・Cryptographic hash function A cryptographic hash function (hereafter simply called a hash function) H takes data M of any length as input, and outputs a bit string H(M) of a fixed length (e.g. 256 bits). Hash functions are basically fixed functions whose specifications are publicly available and anyone can calculate them. In particular, hash functions do not take a key as input. A secure hash function is required to be resistant to preimage attacks and collision attacks. Examples of secure and widely used hash functions include SHA-2 and SHA-3. Although hash functions do not take a key as input, they are conventionally classified as symmetric key cryptography.

<White-box cryptography>
In general, cryptographic techniques are designed to ensure security against black-box attacks. A black-box attack is an attack in which an attacker can know input/output pairs for encryption and decryption functions. For example, when the target of attack is a block cipher, the attacker is allowed to choose an arbitrary plaintext M and know the corresponding ciphertext C:=E _K (M) (or the attacker is allowed to know the plaintext M:=D _K (C) for an arbitrary ciphertext C). After learning ciphertexts corresponding to multiple plaintexts, the attacker aims to uncover the secret key K or to discover some bias in the ciphertexts that should essentially appear completely random.

The important thing here is that an attacker in a black-box attack cannot know how the encryption algorithm is implemented. All that the attacker is allowed to do is learn the input/output pairs of the encryption function _EK or the decryption function _DK .

On the other hand, an attack in which an attacker can see not only the input/output pairs of _EK and _DK , but also the contents of the software that implements _EK and _DK (including information about the private key) is called a white-box attack. An example of a white-box attack would be malware sneaking into a PC that uses software that implements cryptographic technology and sending the data of that software to the outside. Cryptographic technology that can guarantee a certain degree of security against white-box attacks is called white-box cryptography.

Naturally, an implementation in which a short private key of tens to thousands of bits is simply embedded in the software cannot guarantee any security against white-box attacks. This is because if an attacker sees and copies the short private key, they will be able to freely decrypt all ciphertexts. Furthermore, no security can be guaranteed in a situation where an attacker can freely execute software in which cryptographic technology is implemented. For example, if an attacker can freely execute software in which a decryption function is implemented at any time, he or she can freely decrypt any ciphertext and see the original plaintext.

Therefore, when discussing security against white-box attacks, we assume settings like 1 and 2 below.

1. The private key is somehow scaled up to a very large amount of data (e.g., tens of gigabytes).

2. There are certain limitations on the capabilities of attackers. For example, there may be a limit on the amount of data implemented in the software that can be sent externally, or there may be a limit on the amount of time that the contents of the software can be viewed.

In the above setting, there are block ciphers such as SPACE (Reference 1) and SPNBox (Reference 2) that are white-box secure. There are currently no known white-box attacks that can break the security claimed by these block ciphers.

White-box attacks are obviously more powerful than black-box attacks and give the attacker greater freedom. Therefore, it should be noted that any cryptographic technique that is white-box secure is also black-box secure.

[First embodiment]
The first embodiment will be described below.

Because authenticity is as important as confidentiality, the main trend in recent symmetric key cryptography design is to use an AEAD to ensure both confidentiality and authenticity simultaneously when encrypting with symmetric key cryptography. However, no white-box secure AEAD has existed to date. Existing AEADs such as GCM and CCM do not take white-box attacks into consideration. In particular, GCM and CCM are block cipher operating modes, but even if the block cipher used is white-box secure, GCM and CCM as AEADs are not necessarily white-box secure.

On the other hand, as mentioned above, an AEAD is often constructed by combining a narrowly defined symmetric key cryptography and a message authentication code. Therefore, if a white-box secure message authentication code can be realized, a white-box secure AEAD can be constructed by combining this message authentication code with a white-box secure narrowly defined symmetric key cryptography.

Therefore, in the first embodiment, we describe a communication system 1 that constructs a white-box secure message authentication code and enables data communication that satisfies authenticity using this message authentication code.

<Outline of ideas for constructing white-box secure message authentication codes>
Message authentication codes and AEADs need to generate a short, fixed-length tag T from an input of any length. In particular, when the input is very long, the long data must be compressed into a short data by some method. Existing methods such as GCM and CCM (which do not take white-box attacks into consideration) perform compression using a method that depends on a secret key K. GCM and CCM are secure against black-box attacks because a black-box attacker cannot see the compression process, but a white-box attacker can see the contents of the software, and therefore can see the compression process. This "ability to see the compression process" could lead to a breach of the security of message authentication codes and AEADs.

Therefore, we consider performing most of the compression in the message authentication code (and tag generation for AEAD) using a cryptographic hash function H that does not depend on the secret key K. Since hash functions are originally designed on the assumptions that "long bit strings are compressed into short bit strings" and "the compression process is visible to an attacker," a tag generation function that performs compression using a cryptographic hash function H can be expected to be secure against white-box attacks.

On the other hand, to ensure authenticity, the value of the tag T must depend on the private key. Since a hash function does not take a private key as input, security cannot be guaranteed by H alone. Therefore, we aim to ensure authenticity by compressing with a hash function and then calling a (white-box secure) block cipher multiple times.

<Example of a white-box secure message authentication code>
Notation: Let E _K be an encryption function of a block cipher with an input/output length of n bits, and H be a cryptographic hash function with an output length of m≧2n bits. Let (Enc _K' , Dec _K' ) be a common key cipher in the narrow sense. In addition, let f1, f2: {0,1} ^m →{0,1} ⁿ and f3: {0,1} ⁿ ×{0,1} ⁿ →{0,1} ⁿ be functions determined by either Setting Example 1 or Setting Example 2 below.

<<Setting example 1 for f1 to f3>>
f1: Output the most significant n bits of the m-bit input x.

f2: First, take the most significant 2n bits of the m-bit input x and call it d. Then output the least significant n bits of d. Note that if m = 2n, then f2 simply outputs the least significant n bits of the input, and x = f1(x) || f2(x) holds.

f3: Given an input (x, y) ∈ {0, 1} ⁿ × {0, 1} ⁿ , the exclusive OR of x and y, that is,

を出力する。

Output.

<<Setting example 2 for f1 to f3>>
f1: Of the m-bit input x, first let the most significant n bits be d _1. Of this d ₁ , let the least significant (n-2) bits be d ₁ ', and output 01∥d ₁ '.

f2: First, take the most significant 2n bits of the m-bit input x and set this as d. Take the least significant (n-2) bits of this d as d ₂ ', and output 10∥d ₂ '.

f3: When an input (x, y) ∈ {0, 1} ⁿ × {0, 1} ⁿ is given, the lowest (n-2) bits of the exclusive OR of x and y are set as s ₃ , and 11∥s ₃ is output.

Tag generation function of white-box secure message authentication code With the above notation and settings, and based on the above idea, consider a tag generation function that takes data X of any length as input, and calculates and outputs a tag T = _MAC1K (X) as shown in Algorithm 4 in Fig. 5. That is, consider a tag generation function MAC1K that takes data X of any length as input, calculates h←H(X) (line 1), calculates _s1 ← _EK (f1(h)) and _s2 ← _EK (f2(h)) (line ₂ ), and then calculates and outputs T← _EK (f3( _s1 , s2) ₎ (lines 3-4). In this case, if the hash function H is secure and _EK is white-box secure, it is expected that _MAC1K is also white-box secure. The tag generation function _MAC1K configured in this way is represented diagrammatically as shown in Fig. 6.

In addition, when setting example 2 of f1 to f3 is used, the input of the encryption function _EK of the block cipher that is called three times does not overlap. Therefore, it is expected to be more secure than setting example 1 of f1 to f3.

White-box secure verification function for message authentication code In Algorithm 1 shown in FIG. 1, if the input “message M and tag T” is changed to “data X and tag T” and “T′←MAC _K (M)” in the first line is changed to “T′←MAC1 _K (X)”, a white-box secure verification function for message authentication code (denoted as VER1 _K (X, T)) can be constructed.

<Configuration example of communication system 1>
A configuration example of a communication system 1 according to the first embodiment is shown in Fig. 7. As shown in Fig. 7, in the communication system 1 according to the first embodiment, a communication terminal 10 which is a transmitting terminal and a communication terminal 20 which is a receiving terminal are communicably connected via a communication network 30 such as the Internet. Note that examples of the communication terminal 10 and the communication terminal 20 include various information processing devices capable of communication, such as PCs, smartphones, tablet terminals, wearable devices, in-vehicle devices, and electrical appliances.

The communication terminal 10 has an authentication unit 101 and a transmission unit 102. The authentication unit 101 and the transmission unit 102 are realized, for example, by a process in which one or more programs installed in the communication terminal 10 are executed by a processor such as a CPU (Central Processing Unit).

The authentication unit 101 generates a tag T for a message X=M to be transmitted using a tag generation function _MAC1K (X). The transmission unit 102 transmits (X, T) to the communication terminal 20. This allows the communication terminal 10 to generate a tag T= _MAC1K (X) for a message X to be transmitted using the authentication unit 101, and then transmit (X, T) to the communication terminal 20 using the transmission unit 102.

The communication terminal 20 has a receiving unit 201 and a verification unit 202. The receiving unit 201 and the verification unit 202 are realized, for example, by a process in which one or more programs installed in the communication terminal 20 are executed by a processor such as a CPU.

Receiving unit 201 receives (X, T) from communication terminal 10. Verification unit 202 verifies the received (X, T) using VER1 _K (X, T). This allows communication terminal 20 to receive (X, T) from communication terminal 10 via receiving unit 201 and verify the authenticity of (X, T) via verification unit 202.

<Modification>
A modified example of the algorithm of the tag generation function _MAC1K (Algorithm 4 shown in FIG. 5) will be described below.

Modification 1-1
Change "h←H(X)" to "h←H(E _K (0 ⁿ )∥X)" in the first line of Algorithm 4 shown in Fig. 5. By additionally combining E _K (0 ⁿ ), a value that depends on the private key, it is expected that security will be improved.

Modification 1-2
In the third line of Algorithm 4 shown in FIG. 5, “T←E _K (f3(s ₁ , s ₂ ))” is

に変更する。ブロック暗号の暗号化関数Ｅ_Ｋを呼び出す回数が削減されるため、処理効率の向上が期待できる。

Since the number of times that the encryption function _EK of the block cipher is called is reduced, an improvement in processing efficiency can be expected.

Modification 1-3
Modification 1-1 and Modification 1-2 are combined. That is, "h←H(X)" on the first line of Algorithm 4 shown in Fig. 5 is changed to "h←H( _EK ( ⁰ⁿ )∥X)," and "T← _EK (f3( _s1 , _s2 ))" on the third line is changed to "T←(exclusive OR of _s1 and _s2 )." This is expected to improve processing efficiency without significantly compromising security.

[Second embodiment]
A second embodiment will be described below. In the second embodiment, an AEAD is configured from the message authentication code configured in the first embodiment, and a communication system 1 is described that enables data communication that satisfies confidentiality and authenticity by using the AEAD.

<Example of a white-box safe AEAD configuration>
If there is a white-box secure common key cipher (Enc _K' , Dec _K' ) in the narrow sense that is white-box secure in addition to the secure hash function H and the encryption function E _K of the white-box secure block cipher, then it is possible to configure a white-box secure AEAD by configuring an SIV from MAC1 _K and (Enc _K' , Dec _K' ) described in the first embodiment.

That is, (Enc _K' , Dec _K' ) is white-box secure narrow common key encryption. In this case, "T←MAC _K (pad(IV, A, M))" in the first line of Algorithm 2 shown in FIG. 2 is changed to "T←MAC1 _K (pad(IV, A, M))" to configure an encryption function E _{(K, K')} of SIV. Also, "T'←MAC _K (pad(IV, A, M))" in the second line of Algorithm 3 shown in FIG. 4 is changed to "T'←MAC1 _K (pad(IV, A, M))" to configure a decryption function D _{(K, K')} of SIV. This makes it possible to realize data communication that guarantees both authenticity and confidentiality even against a very powerful white-box attack.

Note that there are other configurations besides SIV for deriving an AEAD from a message authentication code and a narrow symmetric key cryptography, but since SIV satisfies a very strong security definition called DAE (deterministic authenticated-encryption), it is preferable to use SIV to ensure security against powerful white-box attacks.

<Configuration example of communication system 1>
A configuration example of a communication system 1 according to the second embodiment is shown in Fig. 8. As shown in Fig. 8, in the communication system 1 according to the second embodiment, a communication terminal 10 which is a transmitting terminal and a communication terminal 20 which is a receiving terminal are communicably connected via a communication network 30 such as the Internet. Note that examples of the communication terminal 10 and the communication terminal 20 include various information processing devices capable of communication, such as PCs, smartphones, tablet terminals, wearable devices, in-vehicle devices, and electrical appliances.

The communication terminal 10 has an encryption unit 103 and a transmission unit 102. The encryption unit 103 and the transmission unit 102 are realized, for example, by a process in which one or more programs installed in the communication terminal 10 are executed by a calculation device such as a CPU.

The encryption unit 103 generates a ciphertext C of a message X=M to be transmitted and a tag T for the message X by the above-mentioned white-box secure AEAD encryption function E _{(K, K')} (IV, A, M). The encryption unit 103 includes an authentication unit 101, and when generating a tag T for the message X, the authentication unit 101 generates the tag T by MAC1 _K (for example, the first line of Algorithm 2 shown in FIG. 2 ) in the same manner as in the first embodiment. The transmission unit 102 transmits (T, C) to the communication terminal 20. As a result, the communication terminal 10 can generate a ciphertext C of the message X to be transmitted and a tag T for the message X by the encryption unit 103, and then transmit (T, C) to the communication terminal 20 by the transmission unit 102.

The communication terminal 20 has a receiving unit 201 and a decoding unit 203. The receiving unit 201 and the decoding unit 203 are realized, for example, by a process in which one or more programs installed in the communication terminal 20 are executed by a calculation device such as a CPU.

The receiver 201 receives (T, C) from the communication terminal 10. The decryptor 203 verifies the tag T by the decryption function D _{(K, K')} (IV, A, T, C) of the white-box secure AEAD, and decrypts the ciphertext C if the verification is successful. The decryptor 203 includes a verification unit 202, and when verifying the tag T, the verification unit 202 generates a tag T' by MAC1 _K and verifies whether the tag T' matches the tag T (for example, lines 2-3 of Algorithm 4 shown in FIG. 4). This allows the communication terminal 20 to receive (T, C) from the communication terminal 10 by the receiver 201, and to verify the authenticity of (T, C) and decrypt it by the decryptor 203.

<Modification>
In the following, modified algorithms of the white-box secure SIV encryption function E _(K,K') and decryption function D _(K,K') will be described. Note that the algorithm of the SIV encryption function E _(K,K') is obtained by changing "T←MAC _K (pad(IV,A,M))" on the first line of Algorithm 2 shown in Fig. 2 to "T←MAC1 _K (pad(IV,A,M))". Also, the algorithm of the SIV decryption function D _(K,K') is obtained by changing "T'←MAC _K (pad(IV,A,M))" on the second line of Algorithm 3 shown in Fig. 4 to "T'←MAC1 _K (pad(IV,A,M))".

Modification 2-1
MAC1 _K realized by any one of the algorithms according to Modification 1-1 to Modification 1-3 of the first embodiment is used.

Modification 2-2
Let K' = K. This reduces the length of the private key to be stored, and is expected to improve processing efficiency.

Modification 2-3
Modification 2-1 and Modification 2-2 are combined, that is, MAC1 _K realized by any one of the algorithms of Modifications 1-1 to 1-3 of the first embodiment is used, and K'=K is set.

[Hardware configuration example]
The communication terminal 10 and the communication terminal 20 according to the first and second embodiments can be realized, for example, by the hardware configuration of a computer 500 shown in Fig. 9. The computer 500 shown in Fig. 9 has an input device 501, a display device 502, an external I/F 503, a communication I/F 504, a RAM (Random Access Memory) 505, a ROM (Read Only Memory) 506, an auxiliary storage device 507, and a processor 508. Each of these pieces of hardware is connected to each other via a bus 509 so as to be able to communicate with each other.

The input device 501 is, for example, a keyboard, a mouse, a touch panel, a physical button, etc. The display device 502 is, for example, a display, a display panel, etc. Note that the computer 500 may not have at least one of the input device 501 and the display device 502, for example.

The external I/F 503 is an interface with an external device such as a recording medium 503a. The computer 500 can read and write data from and to the recording medium 503a via the external I/F 503. Examples of the recording medium 503a include a flexible disk, a CD (Compact Disc), a DVD (Digital Versatile Disk), a SD memory card (Secure Digital memory card), and a USB (Universal Serial Bus) memory card.

The communication I/F 504 is an interface for connecting to a communication network. The RAM 505 is a volatile semiconductor memory (storage device) that temporarily stores programs and data. The ROM 506 is a non-volatile semiconductor memory (storage device) that can store programs and data even when the power is turned off. The auxiliary storage device 507 is, for example, a storage device (storage device) such as a hard disk drive (HDD), a solid state drive (SSD), or a flash memory. The processor 508 is, for example, a calculation device such as a CPU.

The communication terminal 10 and the communication terminal 20 according to the first and second embodiments can realize the various processes described above by having the hardware configuration of the computer 500 shown in FIG. 9. Note that the hardware configuration of the computer 500 shown in FIG. 9 is an example and is not limited to this. For example, the computer 500 shown in FIG. 9 may have multiple auxiliary storage devices 507 and multiple processors 508, or may have various hardware other than the hardware shown in the figure.

The present invention is not limited to the specifically disclosed embodiments above, and various modifications, variations, and combinations with known technologies are possible without departing from the scope of the claims.

[References]
Reference 1: Andrey Bogdanov and Takanori Isobe. White-box cryptography revisited: Space-hard ciphers. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-16, 2015, pp. 1058-1069. ACM, 2015.
Reference 2: Andrey Bogdanov, Takanori Isobe, and Elmar Tischhauser. Towards practical whitebox cryptography: Optimizing efficiency and space hardness. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, Vol. 10031 of Lecture Notes in Computer Science,
pp. 126-158, 2016.

REFERENCE SIGNS LIST 1 Communication system 10 Communication terminal 20 Communication terminal 30 Communication network 101 Authentication unit 102 Transmission unit 103 Encryption unit 201 Reception unit 202 Verification unit 203 Decryption unit 500 Computer 501 Input device 502 Display device 503 External I/F
503a Recording medium 504 Communication I/F
505 RAM
506 ROM
507 Auxiliary storage device 508 Processor 509 Bus

Claims (8)

a tag generator configured to generate a tag T=MAC1 _K (X) for verifying the authenticity of data X by using a tag generation function MAC1 _K (where K is a key) of a message authentication code that is secure against a white-box attack;
The tag generation function _MAC1K is
An information processing device configured using an encryption function _EK of a block cipher that is secure against white-box attacks and has an input/output length of n bits, a predetermined hash function H with an output length of m≧2n bits, and predetermined functions f1, f2: {0,1} ^m →{0,1} ⁿ and f3: {0,1} ⁿ ×{0,1} ⁿ →{0,1} ⁿ . The tag generation function _MAC1K is
Taking the data X as input,
h←H(X) or h←H(E _K (0 ⁿ )∥X) (where ∥ is a bit combination),
s ₁ ←E _K (f1(h)), s ₂ ←E _K (f2(h)),
T←E _K (f3(s ₁ , s ₂ )) or T←(exclusive OR of s ₁ and s ₂ ),
The information processing apparatus according to claim 1 , wherein the tag T is output by: The function f1 outputs the most significant n bits of an m-bit input,
The function f2 extracts the most significant 2n bits from an m-bit input, and then outputs the least significant n bits of the most significant 2n bits;
The information processing device according to claim 2 , wherein the function f3 outputs an exclusive OR of x and y when (x, y)ε{0, 1} ⁿ ×{0, 1} ⁿ is input. The function f1 extracts the most significant n bits from the m-bit input, and then further extracts d ₁ representing the lower (n−2) bits from the most significant n bits, and outputs 01∥d ₁ ;
The function f2 extracts the most significant 2n bits from the m-bit input, and then further extracts _d2 representing the lower (n-2) bits from the most significant 2n bits, and outputs 10|| _d2 ;
3. The information processing device according to claim 2, wherein when (x, y) ∈ {0, 1} ⁿ × {0, 1} ⁿ is input, the function f3 extracts s ₃ representing the lower (n-2) bits of the exclusive OR of x and y, and outputs 11∥s ₃ . an encryption unit configured to generate a ciphertext C of data M using an encryption function E _(K,K') (where K' is a key) of authenticated encryption that is secure against white-box attacks, and to generate a tag as the tag T for verifying authenticity of the ciphertext C by the tag generation unit;
The encryption function E _(K,K') is
The information processing device according to claim 1 , wherein the information processing device is configured using the tag generation function MAC1 _K and an encryption function Enc _K′ of a common key cryptosystem that is secure against white-box attacks. The encryption function E _(K,K') is
Taking as input the initial vector IV, associated data A, and said data M,
Calculate a tag T←MAC1 _K (X) by the tag generator, where X=IV∥A∥M∥len(M) (where ∥ is a bit combination, and len(M) is a bit string representing the length of M);
Calculate C←Enc _K′ (adj(T), M) (where adj(T) is a predetermined function that adjusts the length of T to the length of the initial vector of the common key cipher);
The information processing apparatus according to claim 5 , further comprising: an information processing device configured to output the tag T and the ciphertext C. a tag generation procedure configured to generate a tag T=MAC1 _K (X) for verifying the authenticity of data X using a tag generation function MAC1 _K (where K is a key) of a message authentication code that is secure against white-box attacks;
The tag generation function _MAC1K is
A method comprising: an encryption function _EK of a block cipher that is secure against white-box attacks and has an input/output length of n bits; a predetermined hash function H with an output length of m≧2n bits; and predetermined functions f1, f2: {0,1} ^m →{0,1} ⁿ and f3: {0,1} ⁿ ×{0,1} ⁿ →{0,1} ⁿ . a tag generation procedure configured to generate a tag T=MAC1 _K (X) for verifying the authenticity of data X using a tag generation function MAC1 _K (where K is a key) of a message authentication code that is secure against white-box attacks;
The tag generation function _MAC1K is
A program constructed using an encryption function _EK of a block cipher that is secure against white-box attacks and has an input/output length of n bits, a predetermined hash function H with an output length of m≧2n bits, and predetermined functions f1, f2: {0,1} ^m →{0,1} ⁿ and f3: {0,1} ⁿ ×{0,1} ⁿ →{0,1} ⁿ .

Images