Tag Info

Hot answers tagged

10

mikeazo's answer clearly covers what the question asks. However, I want to go further and answer this: How much information does a perfectly secure cipher leak about the key? Exactly all the excessive information of the key that does not help in finding anything about the message. In simple words: if the key length is $k$ bits and the message is $m$ bits ...


7

Sure, it can leak something about the key as long as that doesn't leak anything about the plaintext. Consider the following cipher, I'll call it 2-OTP. 2-OTP takes as input a message $M$ and two keys $K_1$ and $K_2$. Each key must be truly random, independent of one another, and each the same length as the message $M$. Define encryption as ...


6

This expands CodesInChaos's comment into an answer. Forward Secrecy (that is, maintaining confidentiality of messages enciphered before compromise of the long term key) can be achieved in a protocol using a public-key signature scheme with a long-term public key, and a public-key encryption scheme with a per-session key; but in the case of RSA signature and ...


6

Actually, the problem with OTP isn't the storage of the pad (although secure erasure of the parts of the pad you used is trickier than it looks), and it isn't the pad generation (although, again, that's trickier than it looks), but the secure transport. After all, it's not enough for you (Alice) to have the secure pad, you also have to give a copy to the ...


5

The one-time pad is perfectly secure. It will also leak the complete key to any attacker who knows the message (and will leak some information about the key to any attacker who knows something about the message). It's important to note that there's nothing in the definition of perfect security that says that the attacker can't already know something, or ...


4

No, DHE is secure and allows to share a common secret between two parties over an insecure channel. But you cannot know, if the one you share the secret with is the one you want (DHE is vulnerable to man in the middle attacks). So DHE-RSA uses DHE to share a common secret and signs the communication with RSA to make sure, that both persons communicate with ...


4

For a nonuniform construction with perfect secrecy, consider this scheme, with 2 bits of plaintext $(b_1, b_0)$, and four bits of key $(k_3, k_2, k_1, k_0)$. The ciphertext consists of the three bits: $$(k_3 \land k_2) \oplus b_0 \oplus k_0$$ $$b_1 \oplus k_1$$ $$b_0 \oplus k_0$$ This has perfect secrecy, in that for each ciphertexts, there is the same ...


3

Imagine the following three scenarios. In each, you intercept an encrypted message and you know from context: the message is a randomly chosen key in $\{0,1\}^n$ for some other cryptosystem the message is either "It's a boy!_" or "It's a girl!", both are equally likely the message is a vote from someone in a referendum; it's either "yes" or "no_", and the ...


3

The best option you have is TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA. This is likely to provide most security, as the AES keylength is maximal and ECDSA keys tend to provide more security than RSA keys, as a 128-bit security level is quite common with ECDSA (field size: 256 bit) whereas 112-bit is the standard with RSA (keylength: 2048 bit). However in practice ...


3

The security notion one usually considers for OTP is perfect secrecy, which informally means that the ciphertext does not reveal any information about the original message, regardless of the computational power of the adversary. It is already known that this requires that the key size must be equal to the plaintext size and that all keys are equiprobable. ...


3

Since this is homework, let me just give you a hint: consider the two-character messages $m_1 = \text{"aa"}$ and $m_2 = \text{"ab"}$. Given a ciphertext $c$ encrypted with a monoalphabetic substitution cipher, can you tell which of $m_1$ or $m_2$ it corresponds to, even without knowing the key? Why (not)? What does this imply about perfect secrecy?


3

One possibility for what you might be missing: normally the same key (the same matrix) is re-used to encrypt many messages. So now try counting the total entropy in $M$ length-$N$ messages, and the entropy in a $N\times N$ matrix, and compare what happens when $M$ gets large.... Another possibility you might be missing is the consequences of the fact that ...


3

To use the proper terminology: in TLS, cipher suites which include "some Diffie-Hellman" are: Anonymous Diffie-Hellman: DH_anon Static Diffie-Hellman: DH-RSA, DH-DSS... Ephemeral Diffie-Hellman: DHE-RSA, DHE-DSS... There is no "plain DHE" cipher suite in TLS; it is called "DH_anon". As the name indicates, with DH_anon, the server is "anonymous": you ...


2

Well, for perfect secrecy, we require that for all message distributions over $\mathcal{M}$, all messages $m\in\mathcal{M}$, and all (possible) ciphertexts $c$ it holds that $$Pr[M=m\ |\ C = c] = Pr[M=m]$$ In particular, that means, if we can find a single counterexample, i.e. a distribution over $\mathcal{M}$, a message $m\in\mathcal{M}$, and a ...


2

The term unconditional security was (as far as I know) coined by Diffie and Hellman in their seminal paper New Directions in Cryptography. Here is the snippet [... ] a system which can resist any cryptanalytic attack, no matter how much computation is allowed, is called unconditionally secure. Unconditionally secure systems are discussed in [3] and [4] ...


2

Imagine that you have a ciphertext: Perfect secrecy means, that without knowing the key, any plaintext has to be a possible preimage. Because otherwise the ciphertext would give you information about the plaintext. Encryption is an injective function, because otherwise it could not be reversed. That means, for a given key and ciphertext you have at most ...


2

Assume that $P_1$ contains " the ". In that case you can get the key stream by XOR'ing " the " with $C_1$, lets call this key stream $K^1$. If this key stream is correct then $P_3^1$ should make sense, where $P_3^1 = K^1 \oplus C_3$. If $P_3^1$ doesn't make sense then you can create $K^2$ and $P_3^2$ from $C_2$ in using an identical calculation and check ...


2

This would read out to the following: (I'm citing myself here) An encryption scheme, defined by key generator, encryption function and decryption function over a message space $M$ is perfectly secret if for every probability for a message $m$, for every message $m$ and every ciphertext $c$ which might occur ($Pr[C=c]>0$), ...... the ...


2

What you need for this is something called an $n$-wise independent hash function (like "pairwise independent" but $n$ instead). Such a hash function has the property that when applied to at most $n$ different inputs, its outputs are completely random. These can be constructed efficiently; e.g., a random polynomial of the appropriate degree works. What you ...


1

Both constructions are not perfectly secure! In an attempt to express things a bit more mathematically, I'd say you can implement a one-time-pad with a message $m$ and a key $r$, when $m$ and $r$ are elements of $\mathbb{Z}/n\mathbb{Z}$, the additive group of integers modulo n, or when $m$ and $r$ are elements of a group $G$ isomorphic to ...


1

$\;\;\;$ Sure. $\:$ The simplest way is to OTP-encrypt the $\;\;\;$ output of an almost xor-universal hash family. $\;\;\;$ That could be used for encrypt-then-MAC, where $\;\;\;$ the MAC is applied to an ordered pair that indicates $\;\;\;$ [the message number or how far into the pad to start] and the OTP ciphertext. $\;\;\;$ (Presumably, the pairing ...


1

The threshold for a perfectly secure system is that a computationally unbounded adversary cannot conclude anything about the plaintext from the ciphertext. With a public-key system, the attacker can try to encrypt messages with the real public key; this is not possible with one-time pads. What the attacker can do, quite simply, is to try all one-bit ...


1

Are M and C correlated? No. The distribution that the values the M and C may take on are independent of each other. The condition probability distribution that M has is unchanged no matter what the observed C value is. This is true whether you are using the statistical meaning of correlation, or whether you are looking more specifically at linear ...


1

The usage of the r key forces both parties to "fix" the public DH keys. So Alice doesn't know Bob's public DH key before she's generating her own one. And Bob can not make the choice of the public key dependant on Alice's choice and vice versa. This forces both parties to be honest and to generate both public keys at random as there is no opportunity to ...


1

You might be trying to keep the ciphertext length equal to the plaintext length. This is a "Just Do It" construction: Choose [0 or 1] and [[bit then original output] or [original output then bit]], modify the encryption algorithm to have it concatenate the chosen bit with the original encryption algorithm's output in the chosen order, and modify the ...


1

Here's a more "down to earth" example. The following cryptosystem with plaintext space $\mathcal{M} = \{a,b,c,d\}$, keyspace $\mathcal{K} = \{1,2,3,4\}$ and ciphertext space $\mathcal{C} = \{A,B,C,D\}$ has perfect secrecy: $$\begin{array}{c|c c c c} & 1 & 2 & 3 & 4 \\ \hline a & A & B & C & D \\ b & B & C & D ...


1

If the key would be smaller than the plaintext then you could brute force the cipher by using less than $N$ steps, where $N$ represents the amount of possible messages. Of course the brute force approach is an upper bound to what can be tried. If there are attacks on the cipher (that are less complex than brute force) then the plaintext may be recovered ...


1

Imagine a one-bit message $m$. Attacker knows that $m = 0$ with probability $p$ and $m=1$ with probability $1-p$. (In many cases, $p=0.5$.) With one-time pad (Vernam's cipher) encryption, the attacker can't guess anything. If the ciphertext is 0, the plaintext is 0 with probability $p$ (and the plaintext is 1 with the probability $1-p$). Attacker can't ...


1

What you are describing is One-Time-Pad encryption, and yes it does have perfect secrecy. Note that for any ciphertext $y$ there is exactly one key $k'$ for each possible plaintext $x'$ so that $E_k(x') = y$. So if you choose the key uniformly at random the ciphertext gives no information on the plaintext, because any plaintext is equally likely.


1

I'll further explain the comment of @CodesInChaos and then give a simple example: Explanation When the correctness requirement is weakened the encryption scheme can omit part of the message $m$ (of length $|m|$) to be encrypted and just "loose" it in a way that the cipher (the output of the Encrypt method) is totally independent of that part. Thus the ...



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