66
votes
Accepted
Are one-time pads crackable in theory?
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 ...
- 85.9k
24
votes
Are one-time pads crackable in theory?
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 ...
- 16.7k
21
votes
Is OTP still perfectly secure if we limit message and key space
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 ...
- 134k
16
votes
Accepted
Why is PerfectForwardSecrecy considered OK, when it has same defects as salt-less password hashing?
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 ...
- 1,298
14
votes
Can one claim that AES has perfect secrecy for a key size and message size of 128 bits?
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 ...
- 27k
13
votes
Accepted
Does perfect forward secrecy (using DH or ECDH) imply quantum resistance?
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 ...
- 85.9k
13
votes
Are one-time pads crackable in theory?
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 ...
- 231
13
votes
Accepted
An unbreakable Hill cipher?
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 ...
- 43.5k
12
votes
Accepted
Is perfect-forward secrecy achieved with RSA?
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 ...
- 125k
11
votes
What are the ways to generate Beaver triples for multiplication gate?
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, ...
- 17k
11
votes
Accepted
Does Shannon perfect secrecy imply a deterministic encryption algorithm?
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| ...
- 134k
10
votes
Perfectly secret cipher can leak about the key?
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 ...
- 911
9
votes
Accepted
Perfectly secret cipher can leak about the key?
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 ...
- 37.8k
8
votes
Accepted
2 party AND computation under passive perfect security
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. ...
- 27k
8
votes
Are one-time pads crackable in theory?
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 ...
- 14k
8
votes
Multi-Embedded Xor for Perfect OTP
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 \...
- 19.3k
8
votes
Accepted
What is the difference between information-theoretic and perfect types of security?
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 ...
- 17k
8
votes
Why is PerfectForwardSecrecy considered OK, when it has same defects as salt-less password hashing?
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 ...
7
votes
Accepted
If a cipher has key length shorter than plaintext, then it is not perfectly secure
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\}$...
- 7,924
7
votes
Accepted
Optimal threshold for passive and perfect security
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 ...
- 27k
7
votes
Accepted
Definitions of secrecy
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 ...
- 2,635
7
votes
Are one-time pads crackable in theory?
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! ...
- 171
7
votes
Accepted
Can one claim that AES has perfect secrecy for a key size and message size of 128 bits?
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 ...
- 125k
6
votes
Accepted
Does perfect secrecy imply uniform ciphertext distribution?
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:...
- 134k
6
votes
Accepted
Which is better ECDHE with TLS 1.0
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 ...
- 44.7k
6
votes
How can a cryptosystem be unconditionally secure?
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 ...
- 465
6
votes
Accepted
Cryptography - Perfect secrecy $\implies$ adversarial indistinguishability - proof
Hopefully I'm able to at least give a partial answer. In the first step of the three equalities, there are three simultaneous steps taken:
$$Pr[M=m_0]=Pr[M=m_1]=\frac{1}{2}$$ and $$Pr[b'=b|M=m_0]=Pr[...
- 3,399
6
votes
Perfect secrecy with XOR & SHIFT?
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 ...
- 4,691
6
votes
When does multiple OTP encryption become insecure if new keys are permuted?
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 $\...
5
votes
Perfectly secret cipher can leak about the key?
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 ...
- 44.5k
Only top scored, non community-wiki answers of a minimum length are eligible