# Tag Info

13

Contrary to what Stephen says, you absolutely can compute the tag in parallel. Here's how it works; the tag computation is essentially "assemble the AAD, data, the length field and $Encr(Nonce)$ into a series of values $x_n, x_{n-1}, x_{n-2}, ..., x_0$", and then "compute the polynomial $x_nh^n + x_{n-1}h^{n-1} + x_{n-2}h^{n-2} + ... + x_0h^0$ This ...

6

I'll answer in order: Output size = input size That's correct, GCM uses CTR internally. It encrypts a counter value for each block, but it only uses as many bits as required from the last block. CTR turns the block cipher into a stream cipher. IV of any size For GCM a 12 byte IV is strongly suggested as other IV lengths will require additional ...

5

The GCM flowchart on Wikipedia and my intuition support the notion that some of the GCM work can be done in parallel. At the very least you can do each $E_k(ctr)$ operation in parallel, but it doesn't look like you should be able to parallelize the authentication, as each $mult_H$ requires the output of a previous call as its input. Edit: poncho explains why ...

4

The authentication tag is defined as an output parameter in GCM (see section 7, step 7 of NIST SP 800-38D). In all the API's I've encountered it's appended to the ciphertext. Where it is actually placed is up to the protocol designer. The protocol designer may well consider the place behind the ciphertext as ad hoc default though. The name "tag" of course ...

3

In asymmetric crypto including RSA, we ALWAYS encrypt with the public key, and decrypt with the private key (NEVER the other way around). In the question, what's wanted is to sign with the private key, not encrypt. And that's enough to solve the whole problem, since RSA signature schemes exposed in BouncyCastle or the Java crypto API allow to sign data of ...

3

Yes, it appears that it can be solved in practical time in $GF(2^n)$, if the attacker gets $n+\epsilon$ random $a_i$ values, even if he gets a single bit of the $a_i \times k$ values. The chief observation is that the mapping from $a_i$ to bit $j$ of $a_i \times k$ (which I'll refer to as $bit_j(a_i \times k)$) is bitwise linear (for constant $j$, $k$). ...

3

As SOJPM says in their answer, the proofs for AES-GCM assumes that AES is a PRP. I can't believe that there is anywhere in the proof that using a PRF (possibly truncated) would break things -- but I haven't looked carefully for this. Depending on how the GCM proof is structured, (using/not using) the PRP/PRF switching lemma [1] may suffice, but I don't ...

3

You don't actually need 384 bits of key material. The IV for GCM does not need to be secret, and may be chosen deterministically, e.g. as an incremental counter. Thus, you only need 256 bits for the AES key, which you already have. That said, if you did actually need more key material, you could use any standard KDF to expand your 256 bits. Since you ...

3

If you are constrained by the embedded environment, you should consider CCM instead of GCM as AES mode. One of the major constrain when implementing GCM is that the authentication part (the GHASH) is totally unrelated to AES and should be implemented in its own way. And, to make it reasonably fast, you have to use key-depended look up tables which will ...

3

Well, the GCM tag can be rearranged as $Tag = (Len(C, A) \times H) \oplus \textit{Other Stuff}$; if the length of your ciphertext (and additional authentication data) is consistent, you could precompute $Len(C, A) \times H$, and xor that in along with everything else in the final step. One note: the (add/multiply) that you do in cycle 6 has the side effect ...

3

Should the external nonce passed to GCM be authenticated separately when passing over network? No, that is not necessary; it is implicitly authenticated by GCM itself, pretty much as the AAD is also authenticated. That is, if someone in the middle modifies the nonce, then that will alter the authentication tag that the decryptor computes as a part of ...

3

A message encrypted with AES-GCM can be decrypted with an AES-CTR library IF the authentication tag is stripped from the message. If you are encrypting with AES-GCM and then adding an HMAC tag, you need to strip the HMAC and the GTAG off the message in order to decrypt it, assuming the IV section of the message is in the correct location for each library to ...

3

AES has a block-size of 128 bits in all its variants. The number in AES-128/192/256 is the key-size. Rijndael, the block-cipher that became AES, also supports 256 bit blocks, but that part was not standardized as AES. Since the block-size is 128 bits, GCM works exactly the same way for AES-256 as it does for AES-128.

2

I did some more research and yes it does include both AD length and ciphertext length, so is not vulnerable to a length extension attack as length is part of GCM GHASH. Based on NIST SP-800-38D (PDF) page 18 len(A) and len(C) are both part of the input into the GHASH function. And double-checked this in an implementation gcm_finish method: both lengths are ...

2

Those ciphersuites do use GCM for both encryption and authentication. The hash function mentioned at the end is not used for integrity, but in the pseudorandom function. The TLS PRF is used to derive valid keys for the ciphersuite from the shared secret generated in the key exchange.

2

The field polynomial used for GHASH limits most definitions to 128-bit block size. That does not mean you could not define it for other sizes – the proposal defined it for 64-bit as well (pdf, see Appendix A) even if NIST did not standardize that. However, defining it for arbitrary block sizes would be more difficult. You would need to define a ...

2

That might not be speed-efficient, but for educational purpose it is possible to implement the CTR internals manually, by using the ECB mode of CNG: Set the Algorithm mode: BCryptSetProperty(hAesAlg, BCRYPT_CHAINING_MODE, (PBYTE)BCRYPT_CHAIN_MODE_ECB, sizeof(BCRYPT_CHAIN_MODE_ECB), 0) Encrypt all blocks the IV with counter with the key hKey: ...

2

With concatenation the caller only has to ensure the nonce is unique. For example they can use a counter that increments for each message. Incrementing a counter for each message is convenient in many scenarios, including encrypted network transports like TLS. If you use xor or add nonce and counter you get overlaps, so a counter as nonce would be fatally ...

2

For any $k$-bit MAC, an attacker blindly guessing a tag has a one-in-$2^k$ chance of successfully forging a message. Thus, the expected number of attempts needed to forge a message by brute force is $2^{256}$ for a 32-byte tag, $2^{128}$ for a 16-byte tag, and $2^{64}$ for an 8-byte tag. In practice, attempting $2^{128}$ forgeries is far beyond the reach ...

2

According to Wikipedia, GCM is defined for block ciphers with a block size of 128 bits. So no, you can't use GCM with 3DES or DES, because of the 64-bit block size. You could use something similar to GCM, but it wouldn't be GCM.

2

TLS has different keys for the two different directions. That is, the server-to-client connection is encrypted with one set of keys, and the client-to-server connection is encrypted with another. Both sets of keys are derived at the same time, however they are distinct. Because the keys are distinct, using the same nonce isn't an issue. Technical point ...

2

Thanks @poncho for providing a correct answer. I investigated it deeply, viewing it as a linear algebra problem. Here's what I obtained: in $GF(2^n)$, the series of equations $r_i=a_i\times k$ can be written as $R = K \cdot A$ where: $A$ is a known $n \times n$ matrix, where each column is a bit representation of $n$, linearly independent, $a_i$ $R$ is a ...

2

Theoretically, there is no issue adding some kind of MAC on top of authenticated encryption's builtin. However, in practice there might be subtle flaws with composing the particular primitives you're using, or you may make an implementation flaw that renders them both vulnerable to a side-channel attack that didn't exist previously. Ultimately, it's best to ...

1

This sounds like Kerberos. ( https://en.wikipedia.org/wiki/Kerberos_%28protocol%29 ) In any case, you didn't mention, but it would seem quite important, how long are the generated auth tokens valid for, or how would you expire one. There is no such thing (IMHO) as permanent/indefinite authorization--if you believe otherwise, you should not be doing ...

1

No, not as described in the question. Putting aside the block size confusion that Richie Frame mentions in a comment (AES block size is always 128), there is no advantage to encrypting a second half of an IV in GCM mode in particular, and rarely in other modes. In GCM mode the actual IV is used to derive a nonce for CTR mode encryption. By adding a block ...

1

The authentication tag in GCM is generated by XORing a block cipher output with the Galois field hash (and truncating it for shorter lengths). It is thus assumed to look PRF. So it is effectively just a random nonce that should not collide until a birthday bound of $2^{t/2}$. With a tag length of 96 or more bits, it should be secure. Shorter random IV ...

1

GCM is sometimes called a 1.5 pass AEAD cipher, where the CTR encryption counts for 1 and the GMAC counts for 0.5. So you would indeed expect it to be faster than encryption + CMAC and HMAC with regards to the amount of CPU instructions. That is: as long as the encryption is using AES for both solutions. GCM requires a 128 bit block cipher while CMAC and ...

1

Reusing an IV once opens you up to someone finding the XOR of those two plaintext, seriously compromising their confidentiality. Moreover, with GCM, a single IV reuse leaks significant information about the key used for authentication; if there are even a few pairs of reused IVs (not even one IV used many times; a few IVs each of which are used twice is ...

1

The ZFS file system uses AES in CCM or GCM modes. This works because in ZFS the data and file system metadata is encrypted but the block pointers are in the clear, the AuthTag (MAC) is stored in the block pointer. ZFS also has a SHA256 based merkle tree based on the block pointers that is used for data integrity for resilvering and navigation purposes. ...

1

GCM is a specific mode for block ciphers that combines CTR encryption mode and GMAC authentication. Since Salsa and ChaCha are already based on CTR mode internally, that would not be a relevant mode. However, there is no problem using GMAC. Salsa and ChaCha output larger blocks than GMAC accepts, so you would need to break them in the correct size chunks to ...

Only top voted, non community-wiki answers of a minimum length are eligible