Can you help me find a cryptanalytic way to attack a simple monoalphabetic substitution cipher algorithm? I have decided to make a project at uni that requires me to crack a monoalphabetic substitution cipher. The text is an english text with spaces. The key is a permutation of the alphabet. This isn’t some big project and it should be fairly simple to do. So, I am looking for an algorithm (doesnt have to be really fast) that is fairly simple.

I googled a bit and all the proposed algorithms like this answer to “Strategy to crack a presumed substitution cipher” are some genetic ones (i dont want to get into that) or some advanced (I mean not really basic) statistics (like here http://practicalcryptography.com/cryptanalysis/text-characterisation/quadgrams/#a-python-implementation and you need some other files).

Is there some reliable (I assume not so fast way) to crack the cipher with only the knowledge and use of the letter frequences and some list of the most lets say 10k or more english words?

I thought about it for a while and I cannot come up with a good way to make the function to rate the ciphertext (as is used in most of the algorithms). What would be a well-vetted cryptanalytic way to attack a simple monoalphabetic substitution cipher algorithm?

In the absence of clues, I think you might be left with trying to brute force the ciphertext. However there are ~ $26^{26}$ (maybe it's $26!$ which is still a big no) possible permutations of a 26 character alphabet. That's something that would require enormous computing power.
Brute forcing then might be impractical.

You mentioned the Key is a permutation of the alphabet, the word key sort of suggests a vigenere cipher and the key length is 26 Scrambled up letters. As a general rule, Keywords are shorter. The longer the Keyword, the tougher the Vigenere cipher is going to be to crack. I'm thinking that a key word consisting of the alphabet scrambled is going to be incredibly difficult.

I'ld question what you mean when you say …The key is a permutation of the alphabet… because as a general rule, university professors set difficult problems – not impossible ones. I'm guessing, with my limited knowledge of the subject that greater clarification is needed.

The other thing you can do is carry out a frequency analysis of the letters in the ciphertext, see if there are clear differences in frequency between some letters and others.

Also look for recurring sequences of letters, the distance between these recurrences in the Vigenere is indicative of the key length.
For example, some way in to the ciphertect there may be a three letter sequence like YDS if this occurs later, maybe several times, the distance between those occurences can give away the key length.

So, Three suggestions.

Frequency analysis… Recurring sequences of letters…

Get a second and third opinion from a specialist in Cryptography as I'm merely a beginner and a hobbyist.


Details about ROS attack on blind Schnorr signatures My question concerns the recently uploaded paper On the (in)security of ROS that describes an expected polynomial-time attack on the unforgeability of Schnorr blind signatures.
a) Does this mean that Schnorr blind signatures should not be used anymore (ie. is the attack merely theoretic or can it be used in practice)?
b) How does this attack affect Okamoto-Schnorr blind signatures? In particular, I do not understand the comment of the authors that their attack does not contradict the analysis of Pointcheval-Stern. Were Okamoto-Schnorr blind signatures already broken?
c) The ROS problem mentioned by the authors and initially by Schnorr himself seems quite generic. Could the attack be applied to all blind signature schemes?

The attack is practical. The only safe way to use blind Schnorr and Okamoto-Schnorr signatures is to forbid parallel sessions, that may be impossible if performance is critical.
You can see great explanation of attack here https://youtu.be/W-uwVdGeUUs (Authors of paper offer solution against ROS attack - some modification of Schnorr blind signature, but IMHO it's unsafe)
RSA and BLS blind signatures are not affected by ROS attack.


How to design a balanced LFSR with period 1023 and linear span 55? I am trying various combination of LFSR's to try to design sequence of period 1023.
The linear span should be 55 and the output 1023 bits has to be balanced.

I have tried with five LFSR's with degree 10 and one LFSR with degree 5, XORing all ..which gives 55 as Linear span and period 1023.
However, it is not balanced.
With trial and error, I get a balanced output with XORing 9 LFSR of degree 10 and one LFSR of deg 5.

Can anyone give some idea what path to take to solve this ?

The polynomial factorisation of $X^{2^L-1}+1$ into irreducible factors gives you all the polynomials $g_i(X)$ that can be used as LFSR polynomials in generating any sequence of period $2^L-1.$ Say your goal is to generate a sequence of this period with linear complexity $c.$ Assume

$$(X^{2^L-1}+1)=\prod_{i=1}^v g_i(X),$$
there will be no repeated factors. Not all factors will be primitive of course.

Then for each $g_i(X)|(X^{2^L-1}+1),$ find the linear complexity of the periodic sequence it generates, say it is $L_i.$ You can use Berlekamp Massey for this.

If you can find a subset $J\subset \{1,2,\ldots,v\}$ with $\sum_{i\in J}L_i=c,$ then the corresponding polynomials $$g_i(X),\quad i\in J$$ will generate the sequence you need, for some initial conditions. Some of these polynomials will generate a sequence of length dividing $2^L-1$ of course.

More generally, given polynomials $f_i$ and letting $\Omega(f_i)$ be the set of sequences they generate, then
$$
\Omega(f_1)+\cdots+\Omega(f_v)=\Omega(lcm(f_1,\ldots,f_v)),
$$
and this has been known since the 1950s, published by Zierler in 1959, in Siam Journal of Discrete Maths.

Another good and accessible but somewhat dated reference is the book by Rueppel, The Analysis and Design of Stream Ciphers.

Appendix:

Magma online calculator gives the following factors for $X^{1023}+1$ (truncated)

  X + 1, X^2 + X + 1, X^5 + X^2 + 1, 1>, other degree 5 factors,
  X^10 + X^3 + X^2 + X + 1, other degree 10 factors

so what you found experimentally is not surprising.

Edit: As I alluded to, and this holds for any characteristic, but I will state it for binary, given any sequence $s(t)$ over $F_2$ with period dividing $2^L-1$ (and thus for period equal to $2^L-1$) there is an appropriate trace expansion for that sequence of the form
$$
s(t)=\sum_{i \in J} tr^{L_i}_1(\theta_i \alpha^{i t})
$$
and each of those trace sequences are some cyclic shift of some maximal length sequence (equivalently some cyclic shift of the output of some primitive LFSR) with length $L_i | L,$ where $L_i$ is the number of elements in the cyclotomic coset of $i$ modulo $2^L-1.$ So if a sequence with the parameters you want exists (w.r.t. linear complexity) it can be constructed this way.


Testing Kasiski Test and Mutual Index of Coincidence on Vigenere Encryption on Vigenere Encryption? I was learning about Vigenere Ciphers and its various cryptanalytic attacks. One of them was, Kasiski test and Mutual Index of Coincidence. So, I was wondering can Kasiski test and Mutual Index of Coincidence crack the Vigenere encryption of Vigenere encryption itself (keys may be different or same) i.e. plaintext encrypted using Vigenere cipher and the output of this again encrypted using Vigenere cipher? Will using such scheme create appropriate confusion for the attacker or will it act as a vulnerability?

Vigenere algotrith suppose that Alice would send a message (M) to Bob.
The message is written in some language and has a length ML (symbols that compose the message have a known frequency and belong to an alphabet A with a given size AL).
To encript a message Alice use a key (K) that in Vigenere alogrithm is a seqeuence of symbols called Worm shortest (by definition) than the message, both Alice and Bob knwon K that does not need to be exchanged.
The encripotion is applied by adding the value of each message symbol by the value of the corresponding worm sybol (worm could be completly random) modulo AL.

Eg :

M = "hello world today is fine"
ML = 25
K = "abc"
KL = 3

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
K as values :
61 62 63

As you can see because the worm is short than message (by definition) we need to repeat it, again and again to reach ML

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
K as values (repeated) :
61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61

What we obtain indeed is a sequence of three Caesar encription (in the general case the number of Caesar encription is KL = Key Length):

This is the first Caesar

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
|        |        |        |        |        |        |        |        |
K as values (repeated) :
61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61

Caesar SubMessage : 68 6C 77 6C 74 61 69 66 65
Caesar Key : 61

This is the second Caesar

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
   |        |        |        |        |        |        |        |
K as values (repeated) :
61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61

Caesar SubMessage : 65 6F 6F 64 6F 79 73 69
Caesar Key : 62

This is the third Caesar

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
      |        |        |        |        |        |        |        |
K as values (repeated) :
61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61 62 63 61

Caesar SubMessage : 6C 20 72 20 64 20 20 20 6E
Caesar Key : 63

Symbol frequencies on the main message remain the same if we "regulary split" it on the submessage, so classical attack on Caesar (the ones based on frequency) is still applicable on the three Caesar Submessage.

As you can image if you double the Vigenere encription the complexity of the attack does not change ( EG : add K1 = "def").

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
K as values :
61 62 63

K1 as values :
64 65 66

This because Vigenere encription is composed by Caesar encription and Caesar encription is an associative operation so :

( 68 + 61 mod AL ) + 64 mod AL = ( 68 + ( 61 + 64 mod AL ) ) mod AL

so a double encription is equivalent to a change of the key in a single encription, but the key nature (random or not) does not fix any security problem of that alogrithm.

In the example above (about the double encription) the resulting key, obtained by combining K and K1 is called K2 (i have assumed that AL = 256 and A is the ASCII table) :

K2 = C5 C7 C9

So the double encription is equivalent to a single instance like the below

M as values :
68 65 6C 6C 6F 20 77 6F 72 6C 64 20 74 6F 64 61 79 20 69 73 20 66 69 6E 65
K2 as values (repeated) :
C5 C7 C9 C5 C7 C9 C5 C7 C9 C5 C7 C9 C5 C7 C9 C5 C7 C9 C5 C7 C9 C5 C7 C9 C5

That istance certainly is not stringer than the first ones.


Whats the most secure way to encrypt a string without the use of a computer? I want to decrease attack surface by preventing the plaintext string or encryption key from ever being typed or otherwise entered into a computer. Ideally the decryption key would be something that the user can generate and store in their head. But encryption should still be as strong as possible. I don't need to be able to decrypt without a computer, though that would be cool.

A one time pad, the first problem is the key is as big as the message, the second problem is you have to roll some dice a whole bunch of times and do a lot of repetitive math and looking at tables to convert numbers to characters.

The advantage is perfect secrecy. But I think that answers the question as nothing is more secure.


What is the entropy of a Mersenne Twister (MT)? From Serious Cryptography:
"Entropy is maximized when the distribution is uniform because a uniform distribution maximizes uncertainty: no outcome is more likely than the others. Therefore, n-bit values can’t have more than n bits of entropy."

The MT strives to have as uniform a distribution as possible, so one would think the entropy is maximized and equal to the bit length of the seed.

But the MT becomes entirely predictable after 624 iterations, at which point its entropy should be considered to be zero, but the subsequent distribution is still uniform.

These two ideas seem to contradict each other.

But the MT becomes entirely predictable after 624 iterations, at which point its entropy should be considered to be zero, but the subsequent distribution is still uniform.

The subsequent distribution is not, in fact, independently uniform.

Given 624 32-bit outputs $$V = V_1 \mathbin\| V_2 \mathbin\| \cdots \mathbin\| V_{624},$$ I can deterministically recover the Mersenne twister state by $$S(V) = \tau^{-1}(V_1) \mathbin\| \tau^{-1}(V_2) \mathbin\| \cdots \mathbin\| \tau^{-1}(V_{624}),$$ where $\tau$ is the tempering transform, and then compute the next output by deterministically running the generator $G$ on the recovered state $S(V)$.  If the $V_i$ were independently uniformly distributed, we would have $$\Pr[V_{625} = G(S(V))] = 1/2^{32},$$ but if the $V_i$ are instead generated by the Mersenne twister with uniform random initial state, we have $$\Pr[V_{625} = G(S(V))] = 1.$$

This test—evaluate whether $V_{625} = G(S(V))$—will distinguish the Mersenne twister under a uniform random initial state from a uniform random string with high success rate.

Does this nonuniformity matter for the Monte Carlo physics simulation you're doing?  Perhaps not: your physics model is unlikely to, by happenstance, interact with the Mersenne twister output generation function $G$ in a way that would be a problem, because physics itself is usually not adversarially trying to screw you up personally, no matter how much the years of pain in grad school might make it seem.

On the other hand, if there is an intelligent adversary, as we assume in cryptography, that intelligent adversary will exploit this relation to decipher your messages, steal your money by forging signatures, etc.

In other words, the Mersenne twister is designed to appear uniform to stupid algorithms that don't even know it's the Mersenne twister they're trying to distinguish, but falls flat on its face when it trips on an adversary who knows it's the Mersenne twister but just doesn't know the initial state.


McEliece and cryptanalysis What is the computational time to break McEliece on a quantum computer?

I've seen that polynomial time algorithms exist, but for special conditions. What about the general case?

Dinh, Moore, Russell have shown that the quantum algorithm (Quantum Fourier sampling) used to attack RSA and ElGamal does not work on McEliece-like crypto systems. (I think) this means, that there are no known algorithms on quantum computers that decrease the complexity of attacks on McEliece, and thus McEliece is just as safe post-quantum computers as it is now.


How to create an EC point from a plaintext message for encryption It seems that ElGamal encryption is also possible for Elliptic Curve cryptography. However, that requires the user to convert the message to a point on the curve. What strategies are there to derive a point from a plaintext message? Is it simply generating an X value that just the message converting to a number and finding the Y coordinate for that X value?

The standard approach for this goes as follows, which I think is usually attributed to this paper by Koblitz:

Suppose you have a curve over an $k$-bit prime field. Also suppose you want to encode a fixed-length $k-1-\ell$ bit message - the one bit is subtracted to not having to mess with non-power-of-two field sizes. Then iteratively execute the following:

Compute $x=m\mathbin\|0^\ell$
Compute $x'=x^3+ax+b\bmod q$ for the curve's parameters $(a,b)$ and the field prime $q$.
If $x'$ is a quadratic residue, compute $y=\sqrt x\bmod q$ and return $(x,y)$ else increment the last $\ell$-bit of $x$ by 1 and try steps 2 and 3 again. If these fail $2^{\ell}$ times abort with "non-encodable"

Decoding simply ignores the $y$-coordinate and strips away the last $\ell$ bits of the received point.

This should work because the set of quadratic residues modulo a prime has size roughly $q/2$ and so you have roughly a $1/2$ chance of any given $x'$ working and given that you try $2^\ell$ values, you have a chance of $2^{-\ell}$ of none of them working.


RSASSA-PSS p1v2.1 (rfc 4056) signing I'm signing mails with the RSASSA-PSS (p1v2.1) certificate. When I click Details, it shows "Signature Algorithm: RSASSA-PSS".
openssl x509 -text shows
    Signature Algorithm: rsassaPss
     Hash Algorithm: sha256
     Mask Algorithm: mgf1 with sha256

certutil -dump shows:
1.2.840.113549.1.1.10 RSASSA-PSS

Now, whem I send my signed emails and click on Details in outlook, it shows "Signature Algorithm: RSA (2048)"
I'm using bouncycastle for signing and when I use "SHA256WithRSAEncryption" it works fine, but when I'm using "SHA256WithRSAAndMGF1" Signature, Outlook tells me "The digital signature on this item is Invalid or Not Trusted." and when I click details, I see "Signature Algorithm: RSA (2048)".
Is p#1v2.1 still not supported by outlook/microsoft or am I just crazy?

Is p#1v2.1 still not supported by outlook/microsoft or am I just crazy?

PSS seems still not introduced to Microsoft, please see here. It's a long discussion, but in the end it seems that you cannot select PSS as a signature scheme when sending, I presume that also means that PSS signatures are not accepted.
RSA-OAEP based encryption is generally supported earlier than PSS. There are padding oracle attacks against the PKCS#1 v1.5 encryption scheme. The PKCS#1 v1.5 signature scheme is still considered secure, so there is much less need for upgrading it.


Can I prove set membership and uniqueness without revealing the element? Assuming a publicly known set $\Psi$ with $N$ unique elements.

I have a set $\Sigma=\{\sigma_1,\sigma_2,...,\sigma_m\}$ where $m\leqslant N$. I would like to publicly prove that all the elements in $\Sigma$ are unique and are also elements of $\Psi$. I would like to do this without actually revealing the elements of $\Sigma$.

I happened upon this paper. If I understand it correctly, the above should be possible by publicizing commitments for every $\sigma$. However most of the paper is way over my head and I'm not really sure what commitment scheme I should use, what extra information should be made public and how exactly would a third party Verifier go about verifying the claim.

Proving uniqueness

You can prove that the elements are unique in $O(m)$ time and space by pre-sorting them and then giving a zero-knowledge proof that they are in sorted order.  Details follow.

Assume the elements of $\Sigma$ are integers in the range $[0,K-1]$, where $K$ is a constant chosen in advance and made public.  Pick a large prime $p$ and a group element $g \in (\mathbb{Z}/p\mathbb{Z})^*$ of prime order $q$, such that $q > 2K$.  The scheme is:

First, sort the elements of $\Sigma$, so $\sigma_1 < \sigma_2 < \cdots < \sigma_m$.  Next, commit to all the elements, using a discrete log based commitment scheme with generator $g$; for instance, you might use Pedersen commitments.  Finally, prove that the elements are in sorted value, i.e., that $\sigma_i < \sigma_{i+1}$ holds for all $i$.

You can prove they are in sorted order using a range proof for discrete logs: for all $i$, you show that $\sigma_i \in [0,K-1]$, and you show that $\sigma_{i+1} - \sigma_i \in [1,K-1]$ (again, considering the $\sigma_i$'s as integers).  To prove that $\sigma_{i+1} - \sigma_i \in [1,K-1]$, it suffices to prove that $d_i = \sigma_{i+1} - \sigma_i \bmod q$ is in the range $[1,K-1]$: since you've proven that each $\sigma_i$ is in $[0,K-1]$, and since $q \ge 2K$, there can be no wrap-around modulo $q$.  All that remains is how to describe that each $d_i$ is in the specified range.

One standard way to do a range proof is to express each $d_i$ in binary, i.e.,

$$d_i = \sum_j b_{i,j} 2^j.$$

Then you commit to all the $b_{i,j}$'s, use the homomorphic property of commitments to show that the $b_{i,j}$'s are consistent with the $d_i$'s (i.e., that the equation above holds), and show that $b_{i,j} \in \{0,1\}$ for each $i,j$.  Of course, you can prove that the $d_i$'s were computed correctly by using the homomorphic property of discrete log-based commitment schemes: given the commitments $C(\sigma_{i+1})$ and $C(\sigma_i)$, anyone can compute a commitment $C(d_i)=C(\sigma_{i+1}-\sigma_i \bmod q)$ to $d_i$, even without knowing $\sigma_i,\sigma_{i+1}$.

When using this method of range proofs together with the idea above, it will give you a valid proof that the elements $\sigma_1,\dots,\sigma_m$ are mutually disjoint.

Proving it is a subset

You can show that $\Sigma \subseteq \Psi$ using the techniques in the paper you mentioned.


Are there public slow-but-strong algorithms out there that resist brute-force attacks better? I'm reading that AES uses 4x4 bytes (4*4*8 = 256 bits key) matrix for performances matters (since it's a requirement for common standard encryption algorithms), but are there implementations with choosable key size for this particular algorithm, so I can make brute-force attacks harder with a good password ?

Also, if I'm worried that I can't make user use good passwords (it's a shame, but lets imagine that), can I make an algorithm deliberately slow to make brute-force attacks infeasible with weak passwords, but really secure ?

Could we one day make users switch to key files instead of passwords to completely forget about brute-force, even with the potentially theft of those keys ?

Bruteforcing the AES algorithm itself (i.e. trying all possible keys to encrypt or decrypt some blocks to see if they give the right result in a known-plaintext attack or similar) is not really a problem, even in the 128-bit key version.

(This takes on average 2127 tries. If you can try 230=109 AES-keys per second, it will still take around 5·1021 years, much longer than the universe existed, and any life will exist. Parallelizing this makes it faster, but there is some limit, too ... if you can calculate on 109 processors in parallel, it still needs 5·1013 years ... about three times the estimated age of the universe until now.)

So, the attackable point is not bruteforcing the AES key, but bruteforcing the derivation of a key from a password. And here is where we have to enforce our design. You should not use the password directly (maybe with padding) as an AES key. Instead, use a slow password derivation function, and incorporate some salt.

NIST proposes the PBKDF2 construction based on iterated calling of some fast hash function. Setting the iteration number high enough will make it slow enough.
PBKDF2 is easily parallelizable on GPUs, which makes brute-forcing slightly faster than we would wish, though.

Other alternatives might be bcrypt, or the newer scrypt.
These are firstly slow hash functions for secure password storage, but I think one can also reuse their output as a key for AES or any other symmetric cipher of the right key size. (You just have to think of a protocol to transfer the salt.)


Compared to GCM or XTS modes, how secure is H xor R1, E (R2, R1, Message) for confidentiality and integrity? Let R1 and R2 be (32 byte) random values, and let a H = Hash (R1, R2, Message) be of the same length as each R value.  Provided E (R2, R1, Message) is operating in some chaining mode, are there any known weaknesses of a scheme like this which aims to provide confidentiality and integrity?  The hash could also be an HMAC.

Basically, the following would be presented in succession:

(H xor R1), E (R2, R1, Message)

And verification would involve decrypting with the shared key to arrive at R1; xoring with the first part to arrive at a calculated H, and verifying that H agrees with the hash value that it should.  From that point onward only, further processing on the remainder of the message takes place.

I don't see any reason to expect this to provide integrity (INT-PTXT or INT-CTXT).  In fact, if $R1,R2$ were known to the attacker, I can show that in general it does not provide integrity: there exist some encryption algorithms that are IND-CPA secure but where your scheme does not provide integrity.  (e.g., any stream cipher.)  This sounds like a certificational weakness that makes me skeptical about this construction.

I can't see any reason why you would want to invent a homebrew scheme, that comes with no proof of security, and might have some problems that are known not to occur in existing authenticated encryption schemes... rather than using a well-analyzed authenticated encryption mode.

Basically: don't use this.  Use a standard authenticated encryption mode.  There's a reason they are standard; they have been analyzed in depth.

Here is the attack on integrity, assuming $E$ is a stream cipher.  Suppose we are given an encryption of message $M$, and $R1,R2$ are known.  The attack will change the ciphertext into a valid encryption of some other message $M'$ of the attacker's choice, as follows.

Compute $\Delta = \text{hash}(R1,R2,M) \oplus \text{hash}(R1,R2,M')$.  Xor $M \oplus M'$ into the part of the ciphertext that encrypts the message $M$.  Next, xor $\Delta$ into the part of the ciphertext that encrypts $R1$.  This is now a valid encryption of $M'$ (an encryption that'll be accepted by the recipient and that decrypts to $M'$), which breaks integrity.

Why does this attack work?  If you xor $\Delta$ into the $R1$ part of the ciphertext, this will cause the recipient to think the hash is $H \oplus \Delta$ instead of $H$.  That sounds like a bad property in itself, to me.

I realize this property doesn't actually break your scheme, because in your scheme, $R1,R2$ are presumably not known to the attacker.

Nonetheless, it "smells" to me like it is going to be hard to prove the security of your scheme, because of a circular dependency here.  The integrity of the message depends upon the integrity of $H$, which in turn seems to partly rely on the integrity of $R1$, but the integrity of $R1$ depends upon the integrity of $H$.  In addition, there is no "separation of concerns".  The integrity of the message depends upon the secrecy of $R1,R2$; and the secrecy of the scheme depends upon its integrity properties.  Standard proofs typically rely upon a separation of concerns, where integrity does not rely upon confidentiality.  These kinds of circular dependencies seem like like they are going to make it challenging to prove this scheme secure (if it is even secure).

Now maybe there is a way to prove your scheme secure.  But the onus is on you to show the proof of security.  Why would we use a scheme with no proof of security, when we have one that does come with a proof of security?


Why isn't the alternating step generator used more often? According to the Wikipedia entry for the Alternating Step pseudorandom number generator, there is no public cryptanalysis for this device since it was invented back in 1987 by C.G. Gunther. I have several questions about this:

If it hasn't been cracked since 1987, why is it not considered to be a candidate for a "one way function" like the RSA crypto system, the discrete logarithm system, etc.?
If it is unbreakable, why isn't everybody using it?
Why doesn't Mr. Gunther have a U.S. patent for such a great invention?

A stream cipher, RSA, or whatever you designate by the expression "discrete logarithm system", are not "one-way functions". In particular, asymmetric encryption algorithms and digital signature algorithms provide functionality which is not doable (or not with the same usability) with only the "scrambling" techniques of symmetric cryptography. Let's not confuse things.
ASG is a stream cipher: it produces a key-dependent sequence of pseudo-random bits, which can be combined with some data (bitwise XOR) to encrypt or decrypt it. This is symmetric encryption. As a symmetric encryption engine, it is rather lousy:

Linear Feedback Shift Registers are inefficient in software. They used to be popular in the 70s and 80s because a LFSR is inexpensive, in terms of silicon area, when implemented in a custom ASIC. However, the World has evolved since, and has gone more and more software-based. As of 2011, extreme silicon efficiency is relevant only to very small platforms (RFID tags). For all others, ASG is just slow.

ASG is wasteful of its state. For n-bit security, it requires three LFSR of size at least n bits. Compare it with A5/1: A5/1, with m bits of state, has a security equivalent to 22m/3. The original A5/1 state size is only 64 bits, so its security is in the realm of the highly breakable and open to many kinds of optimizations with precomputations; but the structure of A5/1 could be extended to longer registers, and yield adequate security. For instance, with three LFSR with a total size of 192 bits, you could get with an A5/1-like cipher about 128 bits of security, which is, in simple terms, "totally unbreakable for the foreseeable future". To get the same security level with ASG, you need 384 bits of state, i.e. twice as much.

There is more to a stream cipher than simply spouting out bits. A complete specification should define how the key is transformed into the initial state, preferably along with an Initialization Vector, so that one could encrypt several messages with the same key (exactly what RC4 lacks, and it proved to be an endless source of vulnerable implementations). Weaknesses often hide in those steps. Without such a specification, ASG is like a car engine: regardless of its power, it will not get you far unless you add wheels.

As @Marsh points out, ASG has been patented. This alone is enough to explain that it is not widely used. There is no shortage of good stream ciphers, that we do not know how to break; why would anybody use yet another one, of questionable efficiency and subject to usage conditions and assorted royalties ? In cryptography, a patent is often a way to make sure that a given algorithm will not get used.


CCA-Security Proof of a particular scheme Suppose to have a scheme that works so:
$\mathcal{P}_k =:\{P_k\colon \{0,1\}^{2n} \to \{0,1\}^{2n} \}$ is a strong PRP family.

Encryption: $\operatorname{Enc}(k,m)=P_k(m\mathbin\Vert r)$, where $\Vert$ indicates the concatenation and $r\leftarrow \$ \{0,1\}^n$ ($r$ is random from $\{0,1\}^n$)

Decryption: $m\mathbin\Vert r={P^{-1}}_k (c)$,  return $m$;

I remember that we can define $G^{CCA}_{\pi,\mathcal{A}} (\lambda, b)$ as follows:

1) $k \leftarrow \{0,1\}^\lambda$

2) The adversary $\mathcal{A}$ choose two messages $m_0,m_1$.

3)$c_b \leftarrow Enc(k,m_b)$, where $b \leftarrow \$ \{0,1\}$. (I denote with $\$$ to say that $b$ is random).

4) Adversary must say what message has been decrypted.
Let's assume that $\mathcal{A}$ have access to both $Enc_k()$ and $Dec_k()$ (CCA-Security) algorithm. So $b' \leftarrow \mathcal{A}(1^{\lambda},c_b)$.

5)$\mathcal{A}$ succeeds if $b'=b$.

We have CCA-security if $\mathcal{A}$ can not do better than guessing, that's for all PPT adversary $A$

$$|Pr[G^{CCA}_{\pi,\mathcal{A}} (\lambda, 1)=1]-Pr[G^{CCA}_{\pi,\mathcal{A}} (\lambda, 0)=1]| \leq \upsilon(\lambda) \in negl(\lambda)$$

How can I proceed by reduction? Can someone give me an help?


Is there a counter mode of encryption where the key is being changed for every block of data? I thought like encrypting an IV concatenated with a CTR but instead of XOR-ing this output with the plaintext this output should be used as a temporary key for another encryption block that actually converts the plain- to ciphertext. In other words in a regular CTR mode of operation the XOR would be replaced by a full encryption algorithm and the OTP would be its key.

There are some ciphers which do this, most notably E0, a 128-bit stream cipher based on four LFSRs that is used in older versions of the Bluetooth protocol. As vulnerabilities have been found in E0, a scheme was devised to reduce the security impact called two-level E0. Normally, the cipher encrypts 2745 bits (one Bluetooth frame) at a time. With two-level E0, every 128 bits of the keystream is used to seed another instance of E0 which generate only 2745 bits of keystream from that key.

Note that this is not a special mode of encryption, but the use of true stream ciphers. This difference is minor, as counter mode is merely a way to convert a block cipher into a stream cipher. Most block ciphers (and many stream ciphers) have a key schedule, which is an expensive setup phase whenever a new key is used, making it impractical to frequently switch keys. The stream cipher E0 does not have a complicated key schedule. The 128-bit key is used directly as the cipher's inner state (specifically, it is split up into 25, 31, 33, and 39 bits, each of which is used as the initial state for each of the cipher's four LFSRs). This allows it to change keys frequently without a significant performance impact.

Please note that E0, even two-level E0, is not a particularly secure cipher. The key must be changed very regularly or known-plaintext attacks can allow for key recovery. These weaknesses stem from both problems in the design of two-level E0, as well as the fact that E0 is built off of LFSRs, which are non-cryptographic algorithms. Using AES in CTR mode will be far more secure than any type of E0.


Uniqueness in modular artihmetic I'm pretty new in crypto, and studying RSA now. I saw few videos and read about it and how it works. So  basically, after we have the modulus N and exponent, we encrypt a message with:
m^e mod N = Cipher

and then decrypt that cipher with d
My question is that, seemingly, we can have multiple values for m that would yield the same cipher C, so how can the original text can be determined? For example:
p = 11
q = 13
n = 143
e = 7
d = 103

Now if we encrypt the message 9
for example:
9^7 mod 143 = 48

We get 48, which is the same if we encrypt 152.
How does it work then?

What you are using is the so-called Text-Book RSA. For encryption, we always want the correctness requirement and for public-key systems, this is;
$$D(prv,(E(pk,m)) = m$$ where $E$ is the public key encryption with the public key ($pk$) and $D$ is the decryption with the private key ($prv$).
In Text-Book RSA if we let the messages $m\geq n$ then as you noticed the decryption is not giving back the original message instead provides the $m'$ such that $m' = m \pmod n$ $(9 \equiv 152 \pmod{143})$. Therefore the meaningful resolution is restricting the message space into $[0..n-1]$. Then we can have the correctness requirement.
If you want to encrypt messages with Text-Book RSA then you can split your files into a chunk of sizes in bits at most $\lfloor \log_2 n \rfloor$-bit*.  Here one should consider putting information like the $i$-part of $\ell$, etc. This, however, is not the way to encrypt messages and you must never use the text-book RSA.
We prefer a hybrid-cryptosystem in which the public-key is used to key exchange like RSA-KEM or DHKE and a symmetric cryptosystem is used to encrypt the message with the key.
If you still want to use RSA for encryption then use the correct padding to be secure since the text-book RSA is not secure. RSA should be used with PKCS#1 v1.5 padding or with OAEP.

* To find the number of digits in binary representation of given base 10 integer $n$, calculate $\lfloor \log_2 n \rfloor +1$. Using bits, or actually bytes is much fastert than calculating the data as integer and comparing to the integer $n$.


How to deal with different setup in Multikey FHE? The scenario : using a Multikey FHE scheme, let's say LTV-FHE scheme, parties delegate the computation of some function to the mighty cloud. In LTV-FHE scheme the parties generate their keys and encrypt their messages independently.

If parties have different moduli ladders then what rings should the cloud choose for its computation ? Or the parties should have a common setup in what regards the moduli ladder ?

This question is related with your other question, and the reason the parties can't use different values of $q$ is the same: operations will not be well defined.

Moreover, the statements, proofs, etc, on the paper you have cited are done assuming that all the users are using the same parameters, which means, not only the same value of $q$, but also the same $B$-bounded distribution $\chi$, the same cyclotomic polynomial $\phi$ and so on...

For instance, take a look at lemma 3.6. The authors start it by fixing the parameters and then saying that the scheme is "multikey homomorphic for $N$ keys".

So, the users have to agree about a set a parameters and then generate their own keys independently.


Pollard's $(p - 1)$ factorization method runtime Wondering if anyone knows a good reference for Pollard's $p-1$ algorithm's runtime? I was looking on the Wikipedia page and the runtime cited there is $\mathcal{O}(B\cdot \log B\cdot \log^2 n)$. However, I can't find any reference on the Wikipedia page to this.

Where / how is this result proven?

The $p-1$ method finds factors $p$ of an odd $n$ for which $p-1$ divides only (powers of) primes smaller than some user-selected bound $B$. It does this by computing
$$
\gcd(2^M - 1, n),
$$
where $M = \mathrm{lcm}([1, 2, \dots, B]) = 2^{\lfloor \log_2 B \rfloor}\cdot 3^{\lfloor \log_3 B \rfloor} \dots$. Note that the exponentiation $2^M - 1$ can (and should!) be performed modulo $n$. We can split the computation into three steps:

Find the primes up to $B$. Using the sieve of Eratosthenes, this takes time $O(B \log \log B)$. This only needs to be (pre)computed once, regardless of which $n$ we're factoring.
Compute $2^M - 1 \bmod n$. Instead of computing $M$ explicitly, one may opt to exponentiate $2$ by $2^{\lfloor \log_2 B \rfloor}$, then by $3^{\lfloor \log_3 B \rfloor}$, etc. Each exponent has $O(\log_2 B)$ bits, and there are approximately $B / \log B$ primes, by the prime number theorem. This gives us an exponent of $B / \log B \cdot \log_2 B = B / \log 2$ bits, which leads to $O(B)$ multiplications modulo $n$ using binary exponentiation.
A final GCD of integers at most $n$ sized, which costs at most $\log n$ multiplications of $n$-sized integers.

Unless $B$ is very small, the cost will be dominated by the second step, which has complexity $O(B \cdot \log n \cdot \log \log n)$ using fast multiplication, or $O(B \cdot (\log n)^2)$ using schoolbook multiplication. Wikipedia's bound appears to be the complexity of the variant which uses $M = B! = O(2^{B \log B})$ as the exponent, instead of $M = \mathrm{lcm}([1, 2, \dots, B])$.


AES-256, CBC, plaintext length is multiple of block size: Does PKCS #7 padding weaken the encryption? Of course, padding is superfluous when AES with CBC is used if you know that the plaintext length is a multiple of the block size.
But does the padding precipitate a weakness in the encryption?
Because due to the padding at a block length of 16 bytes, you always have the last block containing just 0x10. So, to my understanding, this is "known-plaintext".
Can this be exploited in real life (today)? Or is this just a theoretical problem (today)?
This answer makes it sound like it's no problem.

If the cipher can't resist a known plaintext attack then the problem
is with the cipher, not the padding.

But is this true for AES-256?

But does the padding precipitate a weakness in the encryption?

If padding oracle exist then you can decrypt the entire ciphertext in 128 tries per byte (on average). However, similar plaintext oracle attacks may be about as strong, and plaintext oracles are not just about CBC mode either. You will need to use an authenticated cipher (such as AES-GCM) to avoid plaintext oracle attacks.
Otherwise the answer is right, it doesn't weaken the encryption. Good ciphers should be even IND-CPA secure, which means that they are secure even if the adversary controls the plaintext.
And yes, padding may hide some information about the plaintext size, but you should not overestimate the security that this provide. Attackers may for instance try and make you put the plaintext on a block boundary, getting back precision when it comes to plaintext size estimates.

But is this true for AES-256?

AES is a block cipher; padding only applies to the specific mode in which the cipher is used. And in such a sense, it is more an issue for the mode of operation than the cipher. AES-256 is certainly considered a secure block cipher, so the trick is to use it using the correct mode. Generally a cipher mode that doesn't require padding such as the aforementioned GCM mode (which in turn is based on CTR mode) should be preferred.
Actually, only a few modes such as CBC (and the barely mentioned PCBC) and ECB require padding. They are not used too much anymore for new systems by modern cryptographers.


Theory Question with Enigma I have been reading a bit about how the Enigma machine was cracked in WW2.
There was also this wonderful post which highlighted a lot of useful information.
Let's assume I know everything about how the M3 Army Enigma machine works according to Kerckhoff's principle. Now I am wondering, in theory, if say, the Germans decided to design a new rotor, would it become obvious right away?
For example say I am attacking Enigma messages. Would I be able to immediately figure out (through analysis of encrypted messages) that "Oh they must have changed the rotor wiring! Send spies!!".
If so. The followup question is that, would I actually need to send spies in this case or could some sort of analysis be used to figure out the wiring of the new rotor?

A thorough read through of the excellent wikipedia article on the history of enigma cracking does give quite a few times the rotor wirings were deduced without any direct knowledge.
Most of these exploited the operational flaw where the same three character key was transmitted twice at the beginning of each message, giving insight into correlation between letters at fixed intervals apart. Over time, you could compile these small clues and make some assumptions. Given that the same 3 wheels were used for an entire day, you can learn a lot about the rightmost wheel over the course of the day. Sometimes they had captured code sheets, so knew the wheels, but didn't know the wiring. This would certainly help deduce the wiring over time.
My favorite anecdote from that page is this one that describes pretty much exactly your scenario:

Mavis Lever, a member of Dilly Knox's team, recalled an occasion when there was an extraordinary message.
The one snag with Enigma of course is the fact that if you press A, you can get every other letter but A. I picked up this message and—one was so used to looking at things and making instant decisions—I thought: 'Something's gone. What has this chap done? There is not a single L in this message.'
My chap had been told to send out a dummy message and he had just had a fag [cigarette] and pressed the last key on the keyboard, the L. So that was the only letter that didn't come out. We had got the biggest crib we ever had, the encypherment was LLLL, right through the message and that gave us the new wiring for the wheel [rotor]. That's the sort of thing we were trained to do. Instinctively look for something that had gone wrong or someone who had done something silly and torn up the rule book.

So yes, new rotor wirings could be deduced, but practically at the time they relied on a combination of espionage, operational shortcomings, and ingenuity to solve such things.


Given an encrypted file, what are possible ways to find its encryption algorithm? Given an encrypted file, what are possible ways to find its encryption algorithm?

Heuristic ways are okay as well.

One of the important properties of a modern cryptographic algorithm is that it resist distinguishing attacks. Distinguishing attacks are any way to tell the encrypted data apart from random data. So if you can tell what the algorithm used was simply by looking at the ciphertext the algorithm is vulnerable to this attack.

Unless there is a header or such that tells you the algorithm and mode used, or a weak cipher was used, determining the algorithm used from the ciphertext is impossible.


help understanding part of Wiener's attack on RSA w/ small d In this paper, the author writes:

  Now $k\phi(N) = ed - 1 < ed$. Since $e < \phi(N)$, we see that $k <d < \frac{1}{3}N^{\frac{1}{4}}$. Hence, we obtain:

   $\mid \frac{e}{N} - \frac{k}{d} \mid \leq \frac{1}{dN^{\frac{1}{4}}} < \frac{1}{2d^2}$

I am having trouble seeing how these last equalities were found. I see how to get the following:

$\mid \frac{e}{N} - \frac{k}{d} \mid$ = $\frac{k}{d} - \frac{e}{N}$ $< \frac{3d}{dn^{\frac{1}{2}}} $

I do not see how to get from here to $\frac{1}{2d^2}$.
Is anyone willing to explain this to me?

The previous part of the proof in that paper already shows that $\left|\frac{e}{N} - \frac{k}{d}\right| \le \frac{3k}{d\sqrt{N}}$. As $k < d$ we estimate this by $\frac{3d}{d\sqrt{N}}$, where the $d$'s cancel to get $\frac{3}{\sqrt{N}} = \frac{3}{N^{1 \over 2}} = \frac{3}{N^{1 \over 4}}\frac{3}{N^{1 \over 4}}\frac{1}{3}$.

As $d < \frac{1}{3}N^{\frac{1}{4}}$ we also get that $\frac{1}{d} > \frac{1}{\frac{1}{3}N^{{1 \over 4}}} = \frac{3}{N^{{1 \over 4}}}$.

Combining we get that $\left|\frac{e}{N} - \frac{k}{d}\right| \le \frac{1}{3d^2}$, which is even a better bound (the 2 might be the constant in the continued fraction convergents theorem, so that might explain it presence).


FHE Bootstrapping vs. Relinearization In the context of Fully Homomorphic Encryption, what is the difference between Bootstrapping and Relinearization?
Between two of them, which is the more expensive (computationally) and why?

Bootstrapping is the procedure that refreshs a ciphertext by running the decryption function homomorphically. By refresh you should think in something like decrypting and encrypting again, so the resulting ciphertext has little noise on it. Therefore, the main goal of bootstrapping is to manage the noise and it is used to transform a somewhat homomorphic encryption scheme into a fully homomorphic one.

Relinearization is a technique to transform quadratic equations in linear ones (generally, on a different set of variables). It is used to

gain the ability of performing homomorphic multiplications over (algebraic) structures that would allow only homomorphic additions;
reduce the ciphertext's size after multiplication (for instance, in this scheme, the ciphertext's size grows from $n$ to $n^2$ elements after multiplication and relinearization is used to generate ciphertexts again with $n$ elements);
make a ciphertext decryptable under the original secret key: in some (RLWE based) schemes, when we multiply two ciphertexts encrypted under a secret key $s$, we obtain a ciphertext encrypted under $s^2$. Then, relinearization (which is usually called keySwitch in those works) is used to obtain a new ciphertext that encrypts the same product but under $s$. (See, for instance, this work).

  which is the more expensive (computationally) and why?

I think that it depends on the scheme, but, in general, bootstrapping is more expensive because it involves evaluating the decryption circuit homomorphically while relinearization is usually performed just by calculating a inner product. Furthermore, bootstrapping almost always requires squashing the decryption circuit so that it can be evaluated homomorphically, but such changes on the scheme generate a more complex scheme with bigger ciphertexts and keys (which makes everything more expensive).


Are RSA or ECC vulnerable to an attack where the same (unknown) plaintext is encrypted with multiple public keys? I'm not sure what this attack model is called - it's not known-plaintext and also not quite cipher-text-only. It is similar to this question except the general case (not just two keys) and using keys you'd find in the wild.

Say you have one hundred ciphertexts which you know are the result of encrypting exactly the same plaintext with one hundred different public keys. Is there any vulnerability here in terms of figuring out what the plaintext is or what the private keys are, either using an RSA-based system or an elliptic curve-based system?

If there is, what would some valid approaches be to preventing the attack? I'm thinking along the lines of the first four bytes being a seed to a PRNG which modify the remaining bytes in some way so that the plaintexts end up being quite different. I suppose something like OAEP should be enough?

RSA is vulnerable to this attack if an insecure padding scheme is used. Still unsure about elliptic curve cryptography.


Finding keys of modified DES encryption This is a question I had in my exam today, and I'll be glad if someone can help me to find the answer.

A student built an encryption algorithm (something between DES and 3DES), in which the encryption is based on 2 keys, $K_1$ and $K_2$, and calculated this way:

$$Cipher = E_{K_1} (E_{K_2} (plaintext))$$

where $E_{K_i}$ is encryption using the key $K_i$.

An attacker knows:

A single plaintext.
The ciphertext of that plaintext.
The encryption algorithm.
Each key is 56-bit.

How can he find the 2 keys?

Of course there's the brute-force solution, looking in all the possible pairs of keys until we find the correct one.

My question is: Can we find another way, better than the brute-force, in order to find the keys?

You can do this slightly better with an additional $\mathcal{0}(2^{56})$ memory and with $\mathcal{0}(2^{56})$ time.

You can notice that the relation $c \leftarrow E_{k_1}(E_{k_2}(m))$ can be rewritten as $D_{k_1}(c) = E_{k_2}(m)$ (just apply the decrypt function on both sides.

First step consists in the generation of every pair $(k_2, E_{k_2}(m))$ and storing them in table (preferably a hash-table for fast lookups).

Having a table with all the pairs $k_2, E_{k_2}(m)$ you can now try all values for $k_1 = 0,2^{56}$ and apply the decrypt function $D_{k_1}$ on the ciphertext received initally. If the value $D_{k_1}(c)$ exists in your precomputed table then you have found the other key $k_2$ which was used to encrypt the original plaintext.

This method also stands by the name of meet-in-the-middle attack.


Why nobody considers counter re-keying as a standard Block Cipher Mode? One of the simplest possible cipher modes is setting each successive key as a function F of the previous one.

K[0] = Master key
C[i] = E(K[i],P[i]), K[i]=F(K[i-1])

This is similar to the counter mode CTR, but the key is incremented instead of the plaintext.

Obviously this mode is slower than the others, since key schedule takes generally more time than encryption (2 times more for AES). Nevertheless some ciphers have very fast re-keying. Also there is the problem with related keys attacks, and some ciphers are not well protected to them — but still this is not a problem for all ciphers.

I wonder why it is not even mentioned as an alternative block mode nor it has a proper name.
Does it have any security drawback? Is it broken?

A tweakable blockcipher where the tweak is set to a counter, and the plaintext gets encrypted directly has the same properties as your idea.

When these properties are desired, you can use either a specialized tweakable blockcipher such as threefish, or you turn a normal blockcipher into a tweakable blockcipher.

When using AES, a typical choice is XTS, which has higher performance and avoids related keys. Such a mode is useful for disk encryption, TrueCrypt is a prominent example using it. And it's documentation has a description of XTS

I believe the encryption part of OCB can be viewed as a tweakable blockcipher as well.

These modes achieve the same thing as your idea, while avoiding the downsides(performance, related keys), so it's not surprising that rekeying isn't used to construct tweakable blockciphers.

If you don't use AES, but a cipher with a fast re-keying and no related key vulnerabilities, you can simply concatenate key and counter, which is pretty similar to your idea. I believe this would work with the blockcipher underlying BLAKE. Threefish treats key and counter almost the same way, so you can view as using the concatenation of key and tweak as its key.

Another downside of your mode is that it allows a multi-target attack on the key:

When you encrypt a constant file of n blocks (say a zero initialized file), a brute-force attacker can recover your key with $2^k/n$ operations where $k$ is the size of the key, so you should use larger keys, probably 160+ bits or so.

The attacker encrypts the fixed and known plaintext block with varying keys and compares it against all the know ciphertext blocks. This comparison is O(1) using a hashtable. Each attempt has a $n$ in $2^k$ chance of succeeding, since there are $n$ targets. Thus the cost of the attack is $2^k/n$ invocations of the blockcipher.


RSA private exponent primality I know that the public exponent is always a prime, but what about the private exponent? Is it always a prime too?

Actually, the public exponent doesn't have to be prime; any odd number works just fine there.  The most common public exponents (3, 17, 65537) all happen to be prime, but there's no requirement.

Now, it turns out that a prime public exponent does make RSA key generation slightly easier in this respect; when you select primes $p$ and $q$, we need to make sure that $p-1$ and $q-1$ are both relatively prime to the public exponent $e$.  If the public exponent $e$ happens to be prime, then this is equivalent to saying that $p \ne 1 \pmod e$ and $q \ne 1 \pmod e$; these can be easy tests to fold into the prime search.  If $e$ is composite, then the conditions are slightly more complex -- certainly not impossible to accomplish, to be sure.

That said, the private exponent need not be a prime number.  All the private exponent $d$ is is a number such that $de \equiv 1 \pmod{ \operatorname{lcm}(p-1, q-1) }$; $d$ will always be odd, but there's no specific reason why it can't be (say) a multiple of 3.


ChaCha with 64bit integers as a PRNG with streams Can I use ChaCha with four rounds as a good non-cryptographic PRNG with different streams if I use 64 bit integers instead of the standard 32 bit integers? I need a bigger state and this seems the easiest way to do it.

The BLAKE and BLAKE2 cryptographic hash functions use a modified version of the ChaCha quarter round in a HAIFA construction. The modified round function uses a 64-bit word size and has adjusted rotation constants (32, 25, 16, and 11 for BLAKE, and 32, 24, 16, and 63 for BLAKE2.). It's likely that all you'd need to do is use that primitive to construct a 64-bit version of the stream cipher, increasing the number of rounds as necessary to allow for sufficient diffusion. Of course, this construction could easily be fatally broken, and you should never roll your own crypto. However, it appears that this would be sufficient for a non-cryptographic PRNG if it meets all your randomness requirements.

If all you need is a non-cryptographic PRNG, you'd likely be better off using a dedicated high-speed PRNG that is capable of performing well on 64-bit architectures, assuming that is the primary reason you wish to operate on those word sizes. Various versions of XorShift should fit the bill. A large seed state can be compressed using a hash function, so there is no need to modify the algorithm.


Name for crypto algorithm that preserves visual pattern Given some input plaintext and output ciphertext, is there a group of crypto algorithms that mean that a change in the ending x bytes of the input plaintext makes some y change at the end of the ciphertext as well? The point is to conserve the visual pattern, but to still be encrypted.

Name for crypto algorithm that preserves visual pattern

I'm not sure exactly what you're looking for, but one interpretation of your question is that you're looking for a way to 'hide' a message within a picture in a way that the picture isn't obviously changed.
The general technique to do this is known as "steganography"; that has the goal of hiding a message into something innocuous (such as a JPEG) in such a way that it's hard to discern (without the key) that there's a message there.  Steganography isn't an algorithm; instead, it is the general term for any algorithm that attempts to achieve this.
One common (and rather simple-minded) technique is to take the various bits of the message, and hide them within lsbits of various pixels the picture (tweaking the pixels only slightly); which pixels you use would depend on the key.
Standard joke: for more information, see the steganography stack exchange - just be warned, it is very well hidden...


Is this a good communication scheme? I'm writing a wrapper for a chat program to allow for end-to-end encryption. I'm using Python and PyCrypto to accomplish this. I'd like to use a well known library to do this, but to my knowledge, none exist that do what I'm looking for.

Here's the design of the handshake protocol.

Alice and Bob have previously generated long-term RSA-2048 keys $A$ and $B$ for signing. Alice initiates an encrypted connection with Bob by creating a new session RSA-2048 key $S$. Alice signs $[S_{public}, \text{"Alice"}]$ with $A_{private}$ using PSS padding to get $Sig_A$.

$$[A_{public}, S_{public}, \text{"Alice"}, Sig_A]$$

Revision: Alice includes her identity in the signature.

Side note: The generation of a new RSA-2048 key is for forward security. I realize generating a new RSA-2048 key is inefficient, but I have no good way of using ECC or Diffie-Hellman.

Bob then verifies $Sig_A$, rejecting the connection if it fails. Bob then matches $A_{public}$ against a list of known trusted keys. Bob then generates a random 512-bit shared secret $Sec$ and encrypts it with $S_{public}$ using OAEP padding to get $EncSec$. Bob signs $[EncSec, A_{public}, S_{public}, \text{"Alice"}, \text{"Bob"}]$ with $B_{private}$ using PSS padding to get $Sig_B$, and then sends the following:

Revision: $A_{public}$, $S_{public}$, and both party's identities are included in SigB.

$$[B_{public}, EncSec, \text{"Bob"}, Sig_B]$$

Alice verifies $Sig_B$, rejecting the connection if it fails. Alice matches $B_{public}$ against her own list of trusted keys. Alice decrypts $EncSec$ with $S_{private}$ to get $Sec$.

Revision: Alice signs $[EncSec, B_{public}, \text{"Alice"}, \text{"Bob"}]$ as $Sig_C$ and sends this to Bob. Bob then verifies $Sig_C$ and rejects the connection if it fails.

At this point, the users would each get a notification showing the fingerprint of the person they are talking to, and whether or not they have been matched against a known list of trusted keys. Fingerprints are generated as $SHA256(RSAPublicKey)$ truncated to 16 hex characters, with a colon added every 4 characters. This fingerprint can be verified with some hard-to-spoof method, such as a phone call.

Alice and Bob have now verified each other's identities and shared a secret value. They both derive encryption and MAC keys like this.

$$EncKey = HMAC_{SHA256}("0", Sec)$$
$$MACKey = HMAC_{SHA256}("1", Sec)$$

Note that the "0" and "1" are strings of length 1 each, not the literal numeric values 0 and 1.

Encrypting and sending a message happens like this. (Assuming $M$ is the message, and $Rand(x)$ is a cryptographic random number generator that returns $x$ random bits)

$$IV = Rand(128)$$
$$C = AES_{CFB}(M, EncKey, IV)$$
$$MAC = HMAC_{SHA256}(IV || C, MACKey)$$

$IV || C || MAC$ is then transmitted. On the receiving end, $MAC$ is checked, and the message is rejected if it fails. Otherwise, the message is decrypted and displayed.

Are there any problems with this? (Other than the obvious "don't roll your own crypto", as I'm fairly backed into a corner here)

That doesn't hide Bob's identity from eavesdroppers.

(The OP mentioned in chat that the OP isn't trying to do that.)

I can no longer spot any other problems with the key exchange part.

The encryption/decryption of application level data is vulnerable to arbitrary replays

and reflection and dropping.  The public MAC input should indicate direction and

message_number and [number of messages received].  There should be a separate way

for it to securely indicate those three things without sending any application-level message, and a way for it to close_notify with a secure indication of those three things.


the probability of sampling a group element that falls in the subgroup on elliptic curve Given an elliptic curve $E$ on $Z_q$. There is a subgroup $<G>$ on $E$, and the order of $<G>$ is $p$, where $p$ is a prime. And the discrete log problem on $<G>$ is hard. Now we randomly sample a group element $G_0$ of $E$. Let $Q$ be the event that $G_0$ falls in $<G>$. Can we say that the probability that $Q$ happens is negligible?

Yes, every finite group (including an elliptic curve over a finite field) either is a finite cyclic group or is the product (not sum) of at least two (not exactly two) finite cyclic groups, and in the latter case some (or even all) of those subgroups may be relatively small. But for crypto we only use a prime-order subgroup that is large enough to satisfy a  specified security parameter, which in practice is set close to the size of the full group of the curve (and also close to the size of the underlying field, per Hasse's theorem). For example the widely-used X9/NIST/SECG curves over $F_p$ were chosen to have prime order, so the only subgroup is the full group and any point chosen as G has that order; this is also stated as having cofactor 1. Bernstein et al's Curve25519 has a full group of order near $2^{255}$ and uses a subgroup of order near $2^{252}$, also stated as cofactor 8; this is not negligible.
If a cryptographic scheme (or implementation of one) that intends to use such a sufficiently-large but proper subgroup fails to ensure or verify that elements (for EC points) purported to be in the subgroup actually are, an attacker may be able to cause it to use values constrained to one of the small subgroups, and thereby gain an advantage; these are generically called small-subgroup attacks and you will find quite a few existing Qs and As about them. 25519 makes privatekeys a multiple of 8 to block this.
That's why your question makes sense for EC mathematics, but not for EC crypto as practiced.


Remove padding (CBC) from decrypted text I have a bit problem with padding. Everything goes fine when I encrypt the text BUT when I decrypt I see some extra characters. Sometime's one character sometimes more and I dont know how to remove them.

But one question I am really upset with is that why does padding show in my decrypted text BUT now others?

Here's my code (PHP) to generate IV:

if($iv = openssl_random_pseudo_bytes(32)){
        $final_iv = substr(base64_encode($iv), 0, 32);
    //The IV size should be 32 characters
}

Here's example of the paddings:

E¢9Àšæ—–Í

Qcn«ûØ›§Ñ¼waf—®

º„%¬â;¸*Í”¨Ö

First, you have to know what padding you are using. In the padding, you will find the padding length.

Second, you should set the padding type in the library.

Third, removing and validating and using padding is tricky and can lead to some padding oracle attacks. In essential, the attacker modifies a block, which is likely to result in wrong padding and a wrong message, but it might also result in a correct message. Attacker then observes if the message was accepted or not and makes some deduction.

To mitigate the padding oracle attack, the easiest way is using encrypt-then-MAC. As a result, any modified message is rejected and attacker can't observe differences between two garbled messages. (Probability of accepting a garbled message is negligible.)

These padding oracle attacks aren't theoretical. For example, SSL3 was killed by one of padding oracle attacks, i.e. POODLE.


Non-interactive proof that an element is in a subgroup I am just reading the DAA paper (http://eprint.iacr.org/2004/205.pdf, Appendix A). A party $\mathcal{I}$ generates two group elements $g' \in \mathrm{QR}_n$ and $h = g'^r \bmod n$ with $r \in_R \left| \mathrm{QR}_n \right|$. Now $\mathcal{I}$ wants to prove in zero-knowledge that $h$ has been created correctly, i.e. that $h \in \langle g' \rangle$.

In the paper the authors use binary challenges with a non-interactive proof of knowledge. I don't get why? This is quite inefficient so I guess that there is a reason for this. Why not just proving $h = g^r \bmod n$ where $r$ is the secret and using one "big" challenge instead of using only 0/1 as the challenge and repeat the protocol?

edited

I have made some further research. Can someone please tell me, if I am right or wrong. The prover P wants to prove to a verifier V that h = g'^r, i.e. $ZKP\ [(r): g'^r]$. $g', h \in G$. The protocol is something like

         P                                V
--------------------------------------------------
y = g'^k mod n           y
                 --------------->  choose challenge c
                         c
                 <---------------
s = k + c*r mod |G|
                         s
                 --------------->  check if g^s mod n = y*h^c mod n

To prove the zero-knowledge property, we have to define a simulator S which communicates with V (instead of P). If it is an honest verifier ZKP, we can define S as $S(y, c, s) = (\frac{g'^s}{h^c}, c, s)$ with $s \in_R \{0, \dots, |G|-1\}$, right? There are no differences between real transcripts (between P and V) and faked transcripts (between V and S) => so the protocol is zero-knowledge, correct??

Now, we have an dishonest verifier, which doesn't choose the challenge randomly. To solve this problem, we use a non-interactive proof, where the challenge is created by a random oracle (for practical use we use "a hash function H"). Instead of transferring $y$ to V (and getting a challenge back) the prover sets $c = H(y)$. We can take the same simulator as in the "interactive-case", or???

What I still don't get is why the authors in the paper separate the 160-bit Hash into 160 pieces and take each bit as the challenge? Is the reason for this that maybe the prover chooses the base $g'$? In other papers they say that you can prove $ZKP\ [(w): g'^w]$ "directly" without using binary challenge, but in these cases the base $g'$ is fixed.

My guess would be that they have a proof that their scheme has the zero-knowledge property if the challenge comes from the set $\{0,1\}$, whereas the proof doesn't work if the challenge comes from the set $\{0,1,2,\dots,2^{160}-1\}$ -- and they don't know how to construct an alternate proof to show the latter.

If you want to understand why their proof doesn't work for larger challenges, you should start by reading through their proof for small challenges and see if each step remains valid for large challenges.

For instance, you might find there is a rewinding step that works if the challenge comes from the space $\{0,1\}$ but doesn't work if there is a large challenge space.  This is a common phenomenom in rewinding-based proofs.  If the challenge space is $\{0,1\}$, you can rewind the challenger and run the protocol forward, and with probability $1/2$ the resulting challenge will match what you want it to be.  Thus, on average, you only need to try twice, and that's fine.   In contrast, if you used a random 160-bit challenge, the probability of success on rewinding would be only $1/2^{160}$, so you'd need to try $2^{160}$ times, which is not feasible.  As result, many rewinding proofs work fine if you have a 1-bit challenge but fall apart if you have a 160-bit challenge.  This poses a barrier to proving the zero-knowledge property using large challenges, using this kind of proof technique.  If the only way they know to prove the zero-knowledge property is using this sort of rewinding proof technique, then that'd explain why they propose a 1-bit challenge.


Why is RSA encryption version 1.0 not specified in an RFC? I saw that there are three RSA encryption versions, as follows:

RSA encryption version 1.5 (RFC 2313)
RSA cryptography specification version 2.0 (RFC 2347)
RSA cryptography specification version 2.1 (RFC 3447)

Why is there no RFC for RSA version 1.0?

RSA is and was specified by the PKCS#1 specifications of RSA laboratories. PKCS are the "Public Key Cryptography Standards" by RSA Laboratories, now part of EMC2. The RSA PKCS#1 v1.5 is the lowest publicly released version of RSA by RSA labs that can currently be downloaded.

Version 1.0 to 1.4 are working drafts as specified in the PKCS#1 documents themselves and at least the inital PKCS#1 RFC 2313 as well:

Versions 1.0–1.3 were distributed to participants in RSA Data Security, Inc.'s Public-Key Cryptography Standards meetings in February and March 1991.
Version 1.4 was part of the June 3, 1991 initial public release of PKCS. Version 1.4 was published as NIST/OSI Implementors' Workshop document SEC-SIG-91-18.

Although the RSA standards have been defined by RSA Laboratories they are likely to have been influenced by the participants to the meetings and workshops.

The RFC's are simply a reiteration of the PKCS#1 standards that have undergone public scrutiny. They are not in control by a single private party. So the standard may be identical, but it is at least open. In general the RFC's just keep to the PKCS#1 specifications, but at least in principle follow up documents may deviate from the specifications by RSA.


Generate keys with k3d3 / ed25519-java I'm trying to use a java implementation of ed25519.

In the code, I can't find any functions that generate keys.

My experience with cryptography is limited to about three weeks of asking questions on stack.

Does the code generate keys?  If so, which function?

Ed25519 is a specific implementation of EdDSA using the Twisted Edwards curve:

x^2 + y^2 = 1 + (121665/121666) * (x^2)(y^2)

It's known as high speed high security signature algorithm. For using the code you pointed out, you need to feed sk, pk, m, sm.

So first you need to call publickey function with sk, then call signature function with m, sk and pk. PK is byte array returned from publickey function.

An example entry:

9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a:d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a::e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b:

It's sk:pk:m:sm

You can find more info at:
http://ed25519.cr.yp.to/index.html


How to produce a binary output sequence using LFSRs but with increased linear complexity? How to produce a binary output sequence using LFSRs but with increased linear complexity?

I have tried searching but i got confused on equation details. So can anyone help me with rather simple explanation on how to increase linear complexity i.e. with some diagram or so.
Thanks

One standard way is as follows. Given $n$ primitive LFSRs with lengths $L_i,i=1,\ldots,n$ such that $\gcd(L_i,L_j)=1,$ and a nonlinear boolean function $$f:\mathbb{F}_2^n \rightarrow \mathbb{F}_2$$ with $f(x_1,\ldots,x_n)$
you have output linear complexity
$$
f(L_1,\ldots,L_n)
$$
evaluated over the integers, where output of LFSR $L_i$ is input as the variable $x_i$ of the boolean function. This is called the combination generator.

So if, for example,
$$f(x_1,x_2,x_3)=x_1x_2+x_2x_3
$$
with
$L_1=31,L_2=32,L_3=33,$ the linear comlexity becomes $31\times 32+32\times 33=2048 $.

See the book Encyclopedia of Cryptography and Security on page 233 for a good discussion.


Obtain Information about hash algorithm from ECDSA public key I have an ECDSA Public Key in DER Format.
I viewed the file in an ASN1 Editor and there's the OID 1.2.840.10045.1.1 whose superior (1.2.840.10045.1) is ecdsa-with-SHA1. So I thought that SHA1 is used here. But it turns out that a signature generated with the corresponding private key could only be verified with openssl when I used EVP_sha256().

How do I get this information about which hash algorithm is used from the whole key?
This is the whole key:

308201333081EC06072A8648CE3D0201
3081E0020101302C06072A8648CE3D01
01022100A9FB57DBA1EEA9BC3E660A90
9D838D726E3BF623D52620282013481D
1F6E5377304404207D5A0975FC2C3057
EEF67530417AFFE7FB8055C126DC5C6C
E94A4B44F330B5D9042026DC5C6CE94A
4B44F330B5D9BBD77CBF958416295CF7
E1CE6BCCDC18FF8C07B60441048BD2AE
B9CB7E57CB2C4B482FFC81B7AFB9DE27
E1E3BD23C23A4453BD9ACE3262547EF8
35C3DAC4FD97F8461A14611DC9C27745
132DED8E545C1D54C72F046997022100
A9FB57DBA1EEA9BC3E660A909D838D71
8C397AA3B561A6F7901E0E82974856A7
0201010342000448E231AF19DF341C82
63521A9436ACBCA5ACB7E3C56A63187B
F22539BE8242FF82F5521F619977FEE1
3457490123F04915671C7AF755E98465
FD20AECAAF7F58

EDIT:
This is a signature in plain format, verifiable with the public key posted above:

93 ea c4 0a 7e 26 04 dc b9 a1 05 34 b1 52 57 2a
0e 1a c8 d2 d5 fc 96 e5 95 c2 45 3d 71 c7 82 8a
0c ac 72 96 01 8c ef 87 b6 9c e2 55 74 e6 de 2d
c6 a3 5c f0 c6 5e 72 27 3a 30 e0 50 33 16 ed 2d

For the public key there is no hash defined. The hash is a configuration option for the signature generation algorithm but it would work for any EC key.

And your information about the key is, for that reason, also incorrect. SHA-1 is maybe mentioned by a tool, but the OID you gave can be written out in long-form (ASN.1 notation) as:

{iso(1) member-body(2) us(840) ansi-x962(10045) fieldType(1) prime-field(1)}

... there is no SHA-1 in there.

So basically the signature generation is dependent on the application you used to produce the signature.

If it is configurable then the hash algorithm should be included with the signature - not with the key. It would of course be advisable to validate that the signature and hash algorithm are within a pre-configured range if they are configurable: you do not want to verify MD-5 / SHA-1 based signatures anymore.

Note that ECDSA directly use the hash without padding (possibly even using fewer bits than is in the hash). No hash algorithm indication is (or can be) used within the signature format itself. The padding of RSA signatures generally contain a hash identifier that can be viewed modular exponentiation with the RSA public key.


CONIKS Prefix Merkle Tree - is it necessary to change tree-wide constant for each update folks!

I'm digging through CONIKS papers and it seems that it is an absolute must to select new tree-wide constant for each update (and to rebuild the whole tree respectively) to prevent parallel attacks through past versions of the same tree structure (like parallel birthday attack for instance).

Can't understand why does it matter and what is the attack scenario?

How practical is this attack?

For instance, Google Trillian developers don't select new Tree Id for each update (for Map using CONIKS hasher).

Papers Im looking at:

1) https://eprint.iacr.org/2014/1004.pdf

2) https://eprint.iacr.org/2016/683.pdf

Many thanks!

As Gary Belvin from Trillian replied:

  In Trillian we use a tree wide constant for computing hashes (See
  MapHasher) in order to achieve as close to l bit security as possibe
  and prevent attacks between trees and between different locations
  inside of a tree.

  As you've noted, the map does not update the tree nonce for each
  revision of the map. Recomputing the entire map tree for each update
  would be prohibitively expensive and would prevent the Trillian Map
  from being a system that supports near-realtime updates. This tradeoff
  is described in the CONIKS paper, section 3.1

  To attack multiple revisions of the same tree, an attacker searches
  for a collision, and then hopes that a future version of the tree
  contains a node that matches the collision. If every leaf node changed
  at every revision, this would be a lot of new nodes to hope for a
  match against. However, in the map, the number of new nodes is < tree
  depth * updates, which grows linearly, not exponentially.

  Even if every node of the map changed at each revision, we should
  still be safe. If I'm reading Katz correctly, in order to maintain l
  bit security in a multi-instance setting we need l + log(N) bits in
  the hash function, where N is the total number of map revisions. 256
  bits of hash output should be sufficient to maintain 128 bits of
  security for 2^128 revisions.


Is there any definition for "generic attack" in context of cryptography or more specific "hash functions"? I'm searching a definition of "generic attack" in context of cryptography or more specific in context of "hash functions". I searched some books and the web but I did not found any definition for it only the usage like "generic birthday attack".

Does someone have a definition for that or knows where I get one?

A "generic attack" against a cryptographical primitive is one that can be run independently of the details of how that cryptographical primitive is implemented.  The most obvious case is a cipher that takes an $N$ bit key; the generic attack of brute force takes a ciphertext, and attempts to decrypt it with all $2^N$ keys; when we find the known (or plausible) plaintext, we are likely to have found the correct key.  This can be done no matter how the cipher uses the key.

When it comes to hash functions, there are three security assumptions we can make (preimage resistance, second preimage resistance and collision resistance), each with a corresponding generic attack.

When it comes to collision resistance (no one can find two distinct messages that hash to the same value), the generic attack is to hash a huge number of distinct messages until the same hash pops up twice.  This is called the "birthday attack" because, because of the birthday paradox, we expect such a pair after hashing about $\sqrt{2^n} = 2^{n/2}$ messages (where $n$ is the size of the hash).


security of design for sending files let's say I have a protocol to send a file $F$. I am intending to employ AES in CBC mode for encrypting $F$ where the $IV$ is
randomly chosen. For authenticity, I am employing $HMAC$ to compute
a Message Authentication Code ($MAC$). Both the encrypted version of $F$ and the $MAC$ are sent to the receiver.

Is there any flaw in this design?

So here's what you're doing:
$$E_{K_1,IV}(F)||H_{K_2}(F)$$

where E denotes encryption with AES-CBC and H denotes HMAC. This is also known as "Encrypt and MAC".

This scheme potentially has a few issues.

It's (formally) not IND-CPA secure, because an attacker can query the encryption oracle for the challenge ciphertexts and compare the resulting MACs.
The scheme puts higher-than-normal contraints on the MAC, because normally MACs aren't assumed to guarantee not to leak anything about their inputs. With HMAC this isn't a problem though.
The scheme could potentially be vulnerable to POODLE-style attacks if you don't validate your CBC padding properly.

As a secure alternative I highly recommend using AES-GCM if you encrypt less than a few GB per key or AES-EAX if you do. Preferably use some well-known and reviewed implmentation of them because getting AES-GCM right isn't exactly easy. As EAX and GCM are authenticated encryption modes they only expect a unique IV from you and the key and will encrypt and authenticate the message properly.


Encrypting with Asymmetric keys I'm designing a system where the client asked for documents to be encrypted with "asymmetric cryptography".

I've explained them that the best practice is to encrypt the data with a symmetric algorithm using a randomly generating key and then, using an asymmetric algorithm, to encode that key. The entire scheme is "asymmetric" but it uses multiple algorithms. I offered the usual performance/convenience arguments.

However they are insisting that we should only use asymmetric algorithms because they "have read that is better".

I'm preparing a note for them to better explain the topic and I would greatly benefit of official documents. I browsed the NIST, FIPS, RFC documents and so on but they are too wide to be used as a reference for a customer that is not well versed on this topic.

Does anyone have some pointers to authoritative sources that explain the best practices and that I could use to back up my arguments?

The PGP, which is well known, uses what is in your mind, hybrid solution. Here a short documentation for your cause.


Trouble with diffie-hellman groups Is anyone able to point me towards a known-to-be-good diffie-hellman group? I currently use group 24 (RFC5114, 2048-bit MODP Group with 256-bit Prime Order Subgroup). It came to me that this group is not adequate even for AES-128 (this is according to www.cryptopp.com/wiki/Diffie-Hellman)...so far it seems my only options are 1) generating a diffie-hellman group myself, but I don't want to do this when I don't know whether the group I will generate has the ideal properties or 2) Have the application generate a new, adequate diffie-hellman group on the first session start... I would like to avoid this, because it introduces a lot of unnecessary complication on the already complicated system.

In short, my need is to include a pre-generated diffie-hellman group on my application, but I don't want to generate this group myself and include it (and neither do I want to generate a diffie-hellman group on the first session start).

I have also looked into RFC3526 but even the biggest group there (group 16, 8192-bit MODP Group) is not strong enough for my needs according to NIST guidelines (I need at least AES-256) the RFC also doesn't specify the strength of the prime-order subgroup, which further annoys me, it also doesn't specify how, where, when, or under what criteria those groups were generated (RFC5114 got its groups from NIST).

The only groups that satisfy are the elliptic curve diffie-hellman groups, but I do not have the necessary support for elliptic curve diffie-hellman, and already got diffie-hellman implemented.

I seem to have hit a dead end here, can anyone chime in?

Well, the question you should be asking "what are my security goals" and only then start addressing which cryptographical primitives (DH groups) meet them.

I rather suspect that your real security goals fall rather short of "unless someone can perform $O(2^{256})$ operations, they can't break it".

So, the real question is "can anyone who will attack my system be able to break the 2048-bit group"?  Note that the largest published effort in this area was roughly equivalent to breaking a 768 bit DH key (actually, that was a factorization effort; it is believed that using Number Field Sieve, the effort involved with solving a Discrete Log on a similarly sized modulus would be approximately the same).  Note that the US Government allows 2048-bit DH modulii to protect sensitive data; it would appear that that's good enough for them.

In addition, as for RFC 3526, the RFC does give estimates of the strength (see section 8; note that it gives two estimates; that's because no one is quite sure how NFS scales, and different knowledgeable people have estimated the exact strengths differently); as for how those were generated, well, those are all of the form $p = 2^n - 2^{n-64} - 1 + 2^{64} \cdot ( \lfloor 2^{n-130} \pi \rfloor + i )$, where $i$ is the smallest nonnegative integer such that both $p$ and $(p-1)/2$ are prime (and they also list the value of $i$).  As for how that was selected (and the reasoning behind it), see RFC 2412 appendix E.


How to find collisions in a secret-prefix Merkle–Damgård given an adversary that can choose the IV? I am given the following Merkle–Damgård construction:

Let $f \colon (\{0,1\}^n \times \{0,1\}^b) \to \{0,1\}^n$ be a compression function. Fix a string $\mathrm{IV}\in\{0,1\}^n$, and for $M \in (\{0,1\}^b)^+$ define $H(\mathrm{IV},M)$ as follows. Parse $M=M_1 || \cdots || M_\ell$, let
$h_0 = \mathrm{IV}$, and let $h_i = f(h_{i-1},M_i)$ for $i=1,2,\cdots,\ell$.
Then $H(\mathrm{IV},M) = h_\ell$. (Note that this does not mean that all imputs to $H$ have to be the same length.)

I'm also given an algorithm C that takes in a value for any IV, and outputs some messages $X,X’$ such that $H(IV,X)=H(IV,X’)$.

Lastly, I'm given access to a secret-key function $F_K(\cdot)=H(K,\cdot)$.

Using C, how can I find a pair of messages $M,M’$ such that $F_K(M)=F_K(M’)$?

I've looked at the proof for Merkle–Damgård constructions and understand that since $H$ is broken, the underlying compressing function f must be broken. What I don't understand is how we could possibly come up with such an M and M' with no knowledge of the IV?

I know that it is not important to know the IV to create a forgery for this construction, but I'm being asked to produce a collision; not a forgery.

I've been struggling with this problem for quite a while, and would love some help on where to start.

Algorithm C would give you the answer directly, except it needs an IV to start off with, and you don't initially know that.  Here's some hints:

The IV you give algorithm C needn't be the secret IV $K$; instead, it can be the intermediate state of some message
So, how could you use your access to function $F_K$ to find the intermediate state in some message?


How do client and server agree on the values of p and g during DHE exchange? How do the communicating parties using Finite Field DHE agree on the values of the $p$ and $g$ variables? Are their values fixed for each DHE group?
Reading through the TLS 1.3 RFC (8446), the client and server (using the key_share extension) only exchange:

DHE named group and

The value of $Y=(g^X \bmod p)$

But there is no mention of how the parties agree on the values of $p$ and $g$ and I cannot find any resource that explicitly says that $p$ and $g$ are fixed per group.

Are their values fixed for each DHE group ?

Yes, by convention a named group includes at least $(g,\mathbb G,q)$ with $\mathbb G$ being a description of the group parameters (i.e. $(p,a,b)$ for prime elliptic curves or $p$ for FFDH), $g$ being the generator and $q$ being the generator's order.

How do the communicating parties using Finite Field DHE agree on the values of the g and p variables ?

The flow in TLS 1.3 currently is:

Client sends (in supported_groups) a list of 'names' (really code numbers) of the groups it is able and willing to use, which may be any combination of FFDHE and ECDHE, and optionally (in key_share) newly-generated public keys for some or all of these groups; it may send empty key_share if it wants to see the server's choice first, or if it is (also) offering and would prefer PSK-based session resumption.
If xxDHE is selected (i.e. except when the client proposes and the server agrees PSK-only resumption) the server checks in key_share for a group it also is able and willing to use, and if found sends a generated public key in that group. If not, but the server finds an acceptable group in the client's supported_groups, it sends HelloRetryRequest specifying that group (but not yet any public key). If neither,  the server aborts the handshake.
If requested, the client sends a new ClientHello with a public key for the group specified by the server (but other changes strictly limited as per 4.1.2) and the server responds with its public key in that group (no change permitted).

In TLS 1.2 and below the flow depends on whether both systems implement RFC 7919, which was published many years after most TLS 1.2 implementations were written, much less lower versions:

With RFC 7919, the client indicates in supported_groups, which originally was called elliptic_curves, the named groups it supports, either FF or ECC. There is no indication of support for other (arbitrary) FF groups, because that was the default long before this extension was created. For ECC groups/curves, previously (in RFC 4492) there were code values to indicate arbitrary/unnamed curves over Fp or F2^m in the Weierstrass form defined by X9.62 and 63, but this was rarely if ever implemented or used and RFC 8422 deletes this option.
The server for FFDHE always sends the p,g values, plus its public key (and a signature), in ServerKeyExchange in a format defined long before even RFC 4492, whether those values correspond to a named group or another, arbitrary group. An arbitrary group could be generated by the server or its admin, or imported from almost any source. For example, the Logjam researchers found a large number of public servers using one FFDHE group that was coded into some versions of Apache httpd.
The client either accepts the server's choice of group and generates and sends their public key in that group, or aborts the handshake. For example, especially in recent years, some client implementations abort if the server sends a group with p too small to provide the desired security level. (Java makes this a runtime-configurable option: jdk.tls.disabledAlgorithms contains "DH keySize < $number".) But even an FF group that is large enough numerically may be weak for less-obvious reasons; there are existing Qs about that.


Why don't we use bcrypt and scrypt together? Everyone is comparing bcrypt to scrypt. Bcrypt is proven, lots of cryptoanalysis and no vulnerabilities so far, but uses very low memory. While scrypt uses a lot of memory, but it's too early in its life. Is there anything problematic by using them in cascade/together? Like scrypt the password then bcrypt the result. Eg.: bcrypt(scrypt(pwd))

Is this a problematic approach somehow or everyone just tries to solve one problem with one and only one KDF?

Probably because a simple cascade would only be stronger against some attacks, while opening the door to more implementation bugs.

While bcrypt and scrypt are password-hashing functions, much of what is in the answers to this question about combining hash functions applies here. Different constructions give preimage resistance and PRF-ness, and which is desired depends somewhat on the use case. (Password storage is mostly about the former, while the latter also matters if you are deriving an encryption key with scrypt.)

Regarding implementation bugs, if the inner function, which is applied to the raw password, leaks the input through some side channel attack, the outer function may not matter at all. Conversely, if the outer function somehow leaks its output, then using the cascade for encryption keys may be completely broken, and using it for password storage may e.g. allow offline attacks.

With password hashing there's the additional problem of how to divide the time. If you spend the same time on both bcrypt and scrypt, a dedicated attack using ASICs or GPUs could be almost twice as fast as if you spent all that time on scrypt.

All that aside, scrypt is already basically a cascaded algorithm. Internally it uses PBKDF2 to preprocess the input and to produce the final output data. Its preimage resistance should therefore be at least equal to that of a single round of PBKDF2, i.e. HMAC with SHA-256.


What is the difference between "securely realizes" and "securely implements"? In some security proofs it is stated that "a protocol securely realizes an ideal functionality" while in some others "a protocol securely implements an ideal functionality".

Is there a meaningful difference or it is just another verb to say a
similar thing?
Also, is there any difference between emulation and simulation in the context of MPC?

Update:

Example for question 1: Outsourced pattern matching, S. Faust, et al. see Definition 3 and compare with 5PM: secure pattern matching, J. Baron, et al. page 29 definition 5.

Example for question 2: wikipedia article on Universal composability:

  Literally, the protocol may simulate the other protocol (without
  having access to the code). The notion of security is derived by
  implication. Assume a protocol P_1 is secure per definition. If
  another protocol P_2 emulates protocol P_1 such that no environment
  tells apart the emulation from the execution of the protocol, then the
  emulated protocol P_2 is as secure as protocol P_1.

Realizes vs Implements
Given the context of the cited papers, they mean the same thing. That said, I would prefer realizes. Implements has a connotation of a source code implementation. There could be implementation flaws (buffer overflow, etc) that impact security. The protocol design is secure, but the implementation is not. That, to me, is the primary reason to prefer realizes over implements.
Simulate vs emulate
The difference in the wording on the Wiki stems from the difference between the two. I found this description of the general difference between the two to be good.

Emulation is the process of mimicking the outwardly observable behavior to match an existing target. The internal state of the emulation mechanism does not have to accurately reflect the internal state of the target which it is emulating.
Simulation, on the other hand, involves modeling the underlying state of the target. The end result of a good simulation is that the simulation model will emulate the target which it is simulating.

So, the wiki article says that "the protocol may simulate the other protocol", but it doesn't have to simulate it (in terms of modeling the underlying state of the target). All it really has to do is emulate, or mimick the outwardly observable behavior. So, internally, we may be simulating the protocol, or we may be doing something else, as long as as long as the outside observable behavior matches.
Note that in Universal Composability, there is a simulator $S$, that is not called a simulator because it simulates the real functionality, it is called a simulator because

We often call the adversary $S$ a simulator. This is due to the fact that in typical proofs of security the constructed $S$ operates by simulating an execution of $\mathcal{A}$.


How can I quickly generate thousands of letters randomly, and strongly mitigate the risk of any compromise? I want to generate English letters in a truly random manner without resorting to hand-thrown dice, despite their advantages. Rolling dice would be too slow and tiring as I need four thousand letters.

Using commercially available TRNG software is unacceptable. Depending on a computer to generate the letters by itself, without my oversight is absolutely out of the question.  But I still want to use a computer, albeit an air-gapped computer, because of increased speed and ease, that will carry out and/or record a process of random number generation using some sort of attached equipment (via USB) and/or sensor.

I feel confident about the air-gapped device I built.  The real estate on that device is probably clean.  For software, it's basic: TAILS. If either hardware or software are bad, this will not matter (or will it?) because I am going to control all parameters and watch the process of random number generation at work moment-by-moment.  I do not want a process that merely spits out a complete file that I must trust. Not too slow, not too fast, just right. I want to supervise the process from start to finish.

What simple, cheap equipment and/or software can I and Joe Schmoe use, as outlined above, to generate high-quality random numbers in a way that is faster and easier than throwing dice while still strongly mitigating the risk of compromise, especially against a highly engaged, agile attacker who operates in both passive and active modes?

What process, mechanical or otherwise, can I use on an undorked computer that I control, employing such simple, cheap equipment, that will enable me to generate letters in a truly random manner--most importantly, that yields values which are cryptographically sound--for a proper one-time pad?

Upon careful reflection, I suggest the following three alternatives. They are in increasing order of effort.

1.

Get the 4000 bytes from a blocking implementation of \dev\random. That will generate information theoretic secure output within an hour of computer usage as the entropy will come from your mouse and key strokes. You won’t have to do anything other than use the machine. So you type:-

 dd if=/dev/random of=my_letters bs=1 count=4000 iflag=fullblock

and keep surfing/typing till it completes and the random characters appear in my_letters. This took   37 minutes on my machine. Inclusion of an entropy collector like HAVEGE will help greatly, but I don't entirely trust the entropy rate estimation for it.

Stuff about dd here. Caution: dd is short for 'disc destroyer'.

Note. In TAILS, dev/random = dev/urandom and therefore unsuitable for OTP generation.

2.

Take 63 photos a blank wall in a very dark room. This seems like a lot, but isn’t.  It’s just 63 consecutive presses of the shutter. Say 5 minutes.  Try to get the lighting so that the entire view finder is illuminated i.e all pixel values > 0. If you have ISO control, turn that up to the max. It's 99% pure entropy from the many types of noise within all CMOS camera sensors. The cheaper the camera, the better. You simply consider the JPEG encoding of the sensor's image as the post processing component of NIST's generic TRNG architecture, as:-

You then treat it as a bit fixing, block entropy source.   There will be no semantic content within the image, so it's just the efforts of the JPEG algorithm to capture the noise. And that's essentially quantum noise, just like the best laboratory phase based TRNGs.  Typically I would then measure it's entropy with a compression algorithm like cmix, but that'll take hours (so I haven't), and you only need 4000 bytes. You can be confident that the image contains >> 4000 bytes of entropy within any decent camera frame as there's nothing else. The piling up lemma will deal with that. You don't have to open the image raster, just use the raw .jpg.

And then use your favourite programming language to do $  \operatorname{SHA-512}(jpg_i) $ in a loop of 63 file hashes and concatenations. Or do cat jpg_i | sha512sum >> my_letters 63 times which is not as monotonous as it sounds with automatic consecutive image numbering and command recall.

This online TRNG uses this technique.

3.

Acquire a Zener diode (<£3) , some batteries and a hammer.  Don’t laugh – it works perfectly. Build something like:-

and plug it into an Arduino’s analogue to digital converter.  There will be lots of quantum Avalanche noise created (>1Vpp). The Arduino then just forwards the raw samples to a PC for you to follow the hash based extraction procedure described above. This time you’ll have to use cmix (or equivalent) to measure the entropy rate to ensure that you’re hashing more than 1024 bits of entropy. That's to be in lock-step with NIST’s definition of ‘full’ entropy.  I use a safety factor of 3, so hash 3072 bits each time. A little C programming will be required, but Arduino’s are used in schools.

cmix details here, and it's greedy for RAM.

I recommend option 1 for zero effort, but option 3 for maximum fun. And option 3 is not limited to 4000 characters of course.