# Tag Info

12

The definition of DAE security, as given in Rogaway and Shrimpton's original paper (which both defines the security notion and proves that SIV mode satisfies it), does effectively require that a DAE scheme must protect ciphertext integrity. Specifically, the definition of DAE security (definition 1 in the paper) says that an encryption scheme is DAE secure ...

11

Deterministic authenticated encryption indeed provides authenticity and it doesn't require a nonce or IV. In that sense it doesn't provide CPA security as identical messages would result in identical ciphertext. Authentication however doesn't really have to do with CPA security. It is about ensuring that the ciphertext was created by a specific party ...

8

Summarizing fkraiem's comment, a CPA-secure encryption scheme can not be deterministic. The reason is simple: the attacker is challenged to distinguish between the encryption of $m_0$ and $m_1$, but he also has access to an encryption oracle (and he can query the oracle at whatever input he wants!). If the encryption scheme yields the same ciphertexts each ...

8

You can safely use HMAC-SHA256 instead of the SIV mode custom PRF to derive the nonce/authentication tag. There's some caveats: HMAC-SHA256 gives a 256-bit output; you'll have to truncate it to the nonce size. HMAC-SHA256 takes in a single bit string, so it can't distinguish the boundary between a header (unencrypted associated data) and payload (encrypted ...

7

As a high level concept, nondetermistic encryption is where the encryption function takes three inputs, the key $k$, the plaintext $P$ and a random value $R$, generating a ciphertext $C = E_k(P, R)$; the idea is that a) two different random values $R$ gives completely different ciphertexts $C$, even if the plaintexts where the same (or related), and b) no ...

6

What you're describing is pretty similar to the SIV block cipher mode. It also uses a deterministic function of the message to derive the nonce for CTR encryption. Under some pretty widely accepted assumptions about HMAC-SHA256 this is a perfectly fine way of achieving deterministic authenticated encryption. It doesn't meet IND-CPA (as you pointed out) but ...

6

You might be limiting yourself at the wrong aspect there. Your goal is the ability to search on ciphertext; and you just look at deterministic encryption in your set of tools. In order to use DE securely, the messagespace HAS TO contain enough entropy in order to protect from brute-force search. The only way to solve this is adding entropy at random either ...

6

In a short paper "On sharing secrets and Reed-Solomon codes," Communications of the ACM, vol. 24, pp. 583-584, September 1981, Bob McEliece and I described a secret-sharing system that uses no randomness (cf. the second paragraph of the paper). This is most useful for very large secrets (lots of bits) since it divides the secret into $k$ parts, and then ...

6

Any deterministic secret sharing scheme as in the question has the property that any participant can run the deterministic algorithm for a guess of the shared secret, and eliminate the guess if the share that the algorithm deterministically assigns him/her does not match his/her share. This implies that some information about the secret is leaked in his/her ...

6

Does this design provide deterministic authenticated encryption? This provides reasonable security as long as you limit the total volume of data encrypted to well below $2^{64}$ bytes. Details. The SIV theorem[1], roughly, is that if $F_{k_1}$ is a $t$-bit PRF, with PRF distinguisher advantage bounded by $\varepsilon_F$, and if $E_{k_2}$ is a randomized ...

5

Here is the answer for why a deterministic public-key encryption scheme cannot be CPA secure. For CPA security it is sufficient if an adversary can distinguish between encryptions of two messages $m_0$ and $m_1$. That is, an adversary gets to see an encryption $c \gets \textsf{Enc}(pk,m_b)$ for a random bit $b$ together with the public key $pk$. Now in ...

4

The key thing here is that even in the case that the final algorithm used is "SHA1PRNG", some entropy will be collected somehow for generating the seed that initializes the PRNG. So, it all depends on the seed. In this case, you can see in the code of sun.security.provider.SecureRandom that the seed is generated by the class sun.security.provider....

4

Deterministic encryption means that if the same plaintext is encrypted twice, it results in the same ciphertext. This is intrinsically a breach of security. “Absolute security” is not a technical term — but deterministic encryption breaks many definitions of security, including perfect security. If two ciphertexts are identical, it reveals the fact that the ...

4

Your construction seems quite similar to SIV mode, except that you're using CBC rather than CTR mode for the encryption step and that you're truncating the MAC value to only 32 bits (and re-expanding it by hashing to derive the actual IV). The only obvious weakness I see in your scheme is the shortness of $y$ and the consequent small IV space. I'd prefer a ...

4

Correctly implemented, it should be secure deterministic authenticated encryption. In fact, it is SIV, in the wider sense of using the "SIV construction" as defined in Deterministic Authenticated-Encryption by Rogaway and Shrimpton (except for lacking a header input). The proof of the security of the SIV construction is that: We will now show that if $F$ ...

4

Informally, in probabilistic encryption random values are used to encrypt a message. Thus, each time we encrypt a message we pick a fresh random value; as a result if we encrypt the same message twice we would get different encrypted value (or ciphertext).This means that the ciphertext does not depend only on key and plaintext.

4

SIV is considered determanistic authenticated encryption because: It is deterministic; given a key, a plaintext maps to a specific ciphertext; there is no randomness involved. It is authenticated encryption; it provides privacy (that is, someone with a set of ciphertexts but without the key gets no information about the plaintexts, other than its length, ...

4

As it was already mentioned by @fkraiem and summarized by @Daniel, deterministic encryption scheme cannot be secure under standard definition of CPA-security. But as deterministic encryption can be quite useful for some purposes (for example, encrypting database keys and entries), there is a weakened definition of CPA-security known as deterministic CPA-...

4

In the context, the IV is part of the ciphertext (as usual with AES in CTR mode). That part of the ciphertext leaks information about the plaintext including for one who does not know the AES key, which is bad in theory at least. This is because the (SHA-1) hash of the plaintext (or part of it) is the IV. In particular, an adversary can use a ciphertext to ...

4

At SEJPM indicated, MD5 and SHA-1 probably are resistant enough for you never to get a collision. However, that doesn't mean that either of them is secure. Neither is SHA-2 or SHA-3. That is, given that the usernames do not have a special structure that makes them hard to guess. The problem is that user names can - generally - easily be guessed. So whatever ...

4

When you use textbook RSA, the public key is $(e,N)$ and the ciphertext of a message $m$ is $c = m^e\bmod N$. The encryption process of textbook RSA involves no randomness; this causes the problem. It is easy to see that when having $m_1=m_2$ the ciphertexts of them $m_1^e =m_2^e \bmod N$. Deterministic encryption is not CPA-secure. When using a Padding ...

4

As long as you are not wedded to RSA, here's a way that completely solves the problem (and scales to more than two targets). The general idea is that we do EC-ElGamal in a pairing friendly curve (that is, an elliptic curve that has a computable function $e(X, Y)$ that satisfies the identity $e(aG, bG) = e(G, G)^{ab}$, for any integers $a, b$ (and $G$ is the ...

3

The padding used for RSA is not the PKCS #5/#7 padding (as you seem to suggest in your own answer), but the Wikipedia entry seems to refer to PKCS #1 v1.5 (RFC2313)) which uses a padding 00 || BT || PS || 00 || D where for RSA encryption we start with a 0x00-byte (to guarantee that the resulting number is below the modulus), then use BT (Block Type) equal ...

3

When talking about encryption with block ciphers, you should distinguish block cipher itself from the mode of operation that employs the block cipher. Block cipher takes an input $P$ of fixed length $n$ and transforms it under key $K$ (and possibly under other parameters such as tweak $T$) to output $C$ of the same length $n$: $$E:\; P \xrightarrow{K(,T)} ... 3 You neglected the most important part, I believe; the encryption map itself may be probabilistic which means we might have$$c \leftarrow \mathrm{Enc}_k(m),$$instead of$$c =\mathrm{Enc}_k(m), which is deterministic. In the first case a second encryption with the same key and message might result in a different ciphertext. Once you realise this and given ...

3

Yes, the most common / secure deterministic encryption is SIV mode, which stands for synthetical IV mode. Here the IV that is used to randomize each message is replaced by an authentication tag (MAC) over the plaintext message. Of course, this means that identical messages will be distinguishable. But if even a single bit of the messages differ then the ...

3

First, you should specify: what you need to be able to do in your database to get your job done; what capabilities an adversary may have; and what you want to ensure the adversary can't do. Here's some generic guesses, but you should fill these in with specialized knowledge of your application's needs. For (1): If all you need to do is search by a known ...

2

I ended up with the following solution: For each email store two values: encrypted email and signature for the email. For encryption I used AES in CBC mode with random IV. For signing I used HMAC SHA256. The keys used for encryption and for signing are different. Later on I found the following link: docs.oracle.com. So looks like this is pretty standard ...

2

I cannot prove that your scheme is secure, but as far as I know, a non-cryptographic hash function would work fine as there is an infinite number of inputs to any given hash, making it impossible to bruteforce all but the shortest messages (which would be an issue for short messages, you may want to append some sort of 128-bit padding). However, that said, ...

2

Assuming that nobody's screwed up the implementation, it should not matter what kind of RNG you get. This is because all java.security.SecureRandom implementations are supposed to be cryptographically strong, as defined in RFC 1750 §6.3 (emphasis mine): 6.3 Cryptographically Strong Sequences In cases where a series of random quantities must be ...

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