66
For example, for a target bitstring of 100 bits, I cannot scan all bitstrings of 100 bits and XOR each with the target, hoping to recover the message. This approach will produce all messages that can be expressed with 100 bits.
That's not the reason why one-time-pads are considered secure. The reason is that even if you try all possible keys that you get ...
24
To begin with, your definition of perfect secrecy is non-standard. The standard definition is given in an excellent answer to the question how is the OTP perfectly secure?.
Essentially, perfect secrecy means that observing the ciphertext does not affect the relative likelihoods of various plaintexts under the unknown key. So the fact that different ...
21
Does that violate the perfect secrecy in any way?
Yes, obviously. Restricting the message space doesn't hurt in any way (the attacker can't get any additional information about the message, even if he knows quite a lot about it already); restricting the key does.
OTP uses a group operation to combine the message and the key; one thing that it needs to ...
18
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 ...
16
Salt-less password hashing is only a problem since the amount of passwords actually used in practice is comparably small and also not evenly distributed. Thus it is both in terms of time and memory possible to generate a table with pre-computed hashes and then check the salt-less hashes against this table to reverse the hash. The protection against this are ...
13
I'll try a practical example:
I trade stocks. Instructions to my broker use a simple Caesar shift cipher, but the shift varies by values in a one-time encryption pad. Common 8-char instructions include: "buy more" "sell all" and "short it".
You intercept an instruction to my broker: "AAAAAAAA"
What is my instruction? Buy, sell, or short?
13
The answer is incorrect, but it's a bit more subtle than it seems. To make this clear, note that encrypting $x$ by computing $c=\operatorname{AES}_{0}(k) \oplus x$ would be perfectly secure (here the key is fixed to 0, but any fixed key value would give the same effect). This is due to the fact that AES is a permutation and so when $k$ is uniformly ...
13
The Hill cipher is vulnerable to known-plaintext attack. Once the attacker gets $n$ plaintext/ciphertext pair it can break the cipher by solving a system of linear equations. Consider AES, it is not proved but considered secure against known-plaintext attack, see this question for details.
And, also, key size itself doesn't represent the security. High key ...
12
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 ...
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 ...
10
No it does not.
Perfect forward secrecy implies that even if you retrieve the private key of the asymmetric key pair that you cannot read any of the past or future messages within a connection. It is only possible to derive the secret session keys of the session that you've retrieved the private key for.
Perfect forward secrecy - or forward secrecy for short ...
10
Nowadays, the most standard method is to use oblivious transfers. Oblivious transfer involve a sender with two messages $(m_0,m_1)$ and a receiver with a selection bit $b$. At the end of the protocol, the receiver learns $m_b$ (and gets no information about $m_{1-b}$) while the sender gets no information about $b$.
Suppose Alice and Bob want to generate a ...
10
In Shannon perfect secrecy, it is assumed that $|K| = |M| = |C|$. Does this imply that $Enc$ is deterministic
Actually, the standard definition doesn't actually imply that. It is necessary that $|K| \ge |M|$ and $|C| \ge |M|$, however in neither case does equality have to hold.
In any case, I'll proceed with the assumption that we have $|M| = |C|$ (the ...
9
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 $ENC(M,K_1,K_2)=...
8
The intuition behind the proof is as follows. Since the output of AND equals 0 when party P2 has input 0, then the transcript is distributed identically when P1 has input 0 and when P2 has input 1. Likewise, in the opposite direction. Thus, the set of possible transcripts when P1 has 1 and P2 has 0 equals the set of possible transcripts when both have 0, and ...
8
However, not all bitstrings are random, e.g. 11111111111111 is less random than 01101001001101. This observation seems to contradict the idea of an unbreakable one time pad.
When cryptographers use the word random they use it in the sense of probability theory. What you're calling "randomness," however, is Kolmogorov complexity, "the length of the ...
8
What if we XOR it multiple times with different keys, like this:
$Cyphertext=((((((Plaintext⊕K1)⊕K2)⊕K3)⊕K4)⊕K5)....⊕Kn$
This is equivalent to XOR with a single key $K$ where $K = K_1 \oplus K_2 \oplus K_3 \oplus ... \oplus K_N$. As such, it would be no stronger than a regular OTP.
Even if the key is biased or contains low entropy, the Xor function is ...
8
We choose groups like RFC 3526 Group #14 or larger so that the precomputation is so large it is not feasible. The main problem with weakdh/logjam is that the chosen groups were originally chosen to be breakable for ‘export-grade’ cipher suites, or what I like to call ‘US imperialism-grade’ cipher suites.
The scheme was that US companies—which are the only ...
7
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?
Ps. ...
7
The way to extend the proof to arbitrary $t,n$ and this threshold is as follows. Assume that there exists a protocol for any $n$ parties that withstands a threshold of $t=n/2$ corrupted parties, for computing $f(x_1,\ldots,x_n)=x_1 \wedge x_{n/2+1}$. (If it withstands $t>n/2$ then it also withstands $t=n/2$, so that's fine.) I will now construct a two-...
7
The reason you can't crack a one-time-pad is because brute forcing will just end up generating every possible solution. But you'll be no closer to knowing which of those solutions is the right one! To give an example, say that someone encodes an ip address using a one time pad. You intercept the message. So you start brute forcing it. Most of the ...
7
No, one can not claim that AES has perfect secrecy for a key size and message size of 128 bits. The answer quoted in the second part of the question is seriously wrong.
Perfect secrecy is an information-theoretic concept, assuming an adversary with infinite computing power, and AES is not safe against that.
In the context of the question: revealing $\...
6
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 &...
6
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 ...
6
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] ...
6
In cryptography, forward secrecy = perfect forward secrecy, backward secrecy = future secrecy.
First, recall some background. The above terms are often discussed in the setting of secure channel establishment protocols, e.g., TLS, Signal, etc. In such a protocol, consider two parties, a client and a server, try to communicate with each other securely. The ...
6
Hiding which cipher you are using means violating Kerckhoff's principle. That's actually an extremely common mistake. The problem is that such a cipher becomes very hard to analyze because you have to consider all the options for an attacker to learn parts of the system.
In general we don't analyze cipher designs on this website because it is too easy to ...
6
This is an inconsequential variation on a two-time pad and falls just as readily.
Say your pad is $n$ symbols long. Fix a permutation $\pi \in S_n$ of $\{1,2,\dots,n\}$—this is determined by your $\operatorname{permute}$ operator. If the pad is $(p_1, p_2, \dots, p_n)$ and the $i^{\mathit{th}}$ message is $m_i = (m_{i,1}, m_{i,2}, \dots, m_{i,n})$, then ...
answered Mar 12 '19 at 21:08
Squeamish Ossifrage
44.6k3 gold badges94 silver badges194 bronze badges
6
Information-theoretic security means that any algorithm (even unbounded) has a negligible probability of breaking the security property (in the security parameter). This is the same as unconditional security: it does not rely on any computational assumption, and is not limited to probabilistic polytime adversaries.
A perfectly secure protocol is such that ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible