68
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 ...
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?
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 ...
12
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 ...
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
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 ...
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
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
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 ...
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
40.3k3 gold badges77 silver badges166 bronze badges
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 ...
5
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 &...
5
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 ...
5
First, do not ever use RC4.
Second, it depends on how you use that stream...
If you use AES-CTR as a stream cipher (see more here), you will specify a key $K$ (and a nonce $IV$). The CTR mode of AES will generate a stream of bits, whose length matches the messages. All that is required is to XOR it with the message.
In order to decipher. One will require ...
5
You can do anything in MPC, as long as you can express it in a circuit. I assume that there is a known upper bound on $k$ (otherwise you can't even share it). In that case, all you need to do is to take enough randomness (security parameter number of bits more than the upper bound) and then compute the sum of the randomness held by each party modulo $k$ (...
5
In order for information-theoretic security to imply computational security, you need to require that the simulator run in time that is polynomial in the running time of the real adversary. This is the standard definition, specifically to avoid protocols such as you presented in your question.
So, the answer is:
If you allow the simulator to be unbounded ...
Only top voted, non community-wiki answers of a minimum length are eligible
