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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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| ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
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 \...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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\}$...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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! ...
user avatar
  • 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 ...
user avatar
  • 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:...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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[...
user avatar
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 ...
user avatar
  • 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 $\...
user avatar
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 ...
user avatar

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