What causes first block of AES decryption to be garbled, even with correct IV?

For TLS the IV for the first packet is generated from the shared secrets; quoting the RFC 2246:

  To generate the key material, compute

  key_block = PRF(SecurityParameters.master_secret,
                     "key expansion",
                     SecurityParameters.server_random +
                     SecurityParameters.client_random);

  until enough output has been generated. Then the key_block is
    partitioned as follows:

  client_write_MAC_secret[SecurityParameters.hash_size]
  server_write_MAC_secret[SecurityParameters.hash_size]
  client_write_key[SecurityParameters.key_material_length]
  server_write_key[SecurityParameters.key_material_length]
  client_write_IV[SecurityParameters.IV_size]
  server_write_IV[SecurityParameters.IV_size]

I suppose that you have generated these, and checked them?
(You need 6 ·16 bytes in your cipher suite, and the last 32 are the IV's, one for each direction.)

Also, the IV for the next TLS-record is the last cipher text block of the previous record in the same direction. So you need to keep track of these as well. So the first IV is never sent, and you need to keep updating the IV as we get new packets in, or send new ones.


EC scalar multiplication with zero scalar

I saw multiple software implementations with multiple results such that, $[0]G=0$ or $[0]G=G$.

As stated in the comments, we define $[0]G = 0$, anything else is incorrect
I thought I'd outline why we define things we did.
What we want is to have $[a+b]G = [a]G + [b]G$ be true for all integers $a, b$, and all points $G$.
If it is true for all integers $b$, it must be true for $b=0$, hence we must have:
$$[a+0]G = [a]G + [0]G$$
This obviously simplifies to $[a]G = [a]G + [0]G$, and this is true only if $[0]G$ is the group identity, that is, only if $[0]G = 0$


Toy encryption system that provides "hints"

You can try NSA's CryptoKids page (archived here). It's been around for some years and the ciphers have varying difficulty so you might at least get some ideas.

Alternatively you can use plain XOR encryption with a twist: Encrypt multiple consecutive letters with the same character. For example, if $|m|=n$ then $|k|=n/4$ and do $c_i,...c_{i+4}=k_i \oplus m_i,...,m_{i+4}$. That should give good feedback with every correct guess.


Why don't homophones hide multiple-letter patterns?

For starters, you don't have 4 or 5 codes for every letter. The basic idea is, that each symbol in your alphabet for the ciphertext has the same frequency. Most letters will still have only 1 or 2 symbols, and just the more common ones will have 3 or more.

So the frequencies of single symbols is roughly uniform. Let's take your example of a th, which is the most common bigram in english language (the  frequencies are just examples, other sources might have different ones)

$t$ has frequency $0.0894$
$h$ has a frequency $0.0496$
$th$ has a frequency of $0.0271$

Now let's imagine we have a total of 100 symbols in the ciphertext, where we have 9 symbols for the letter $t$ and 5 for the letter $h$, so that each symbol has roughly the frequency $1/100$.

Now there are $9\cdot5 = 45$ possible combinations for $th$. With 100 symbols in the alphabet, the number of possible bigrams is $10000$ and the frequency should be 0.0001 if it is uniform. We know that $th$ has a frequency of $0.0271$, spreding that uniformly over 45 combinations and we get a frequency of $0.0271 / 45 \approx 0.0006$.

So, even if we have the monogram probabilities almost at $1/100$ for every symbol, then those $45$ bigrams for $th$ have a frequency that is roughly 6-times as high as the average bigram should be. In comparison: The monogram $t$ has just a frequency, which is not even 2.5 times higher than $1/26 \approx 0.0385$.


You don't need to change the key at all in terms of it being "overused". The only reason to change a key is when you use it beyond the bounds given in proofs of security. You have to look this up, but if you are using HMAC-SHA256 with a 256-bit key then you can go on for about $2^{128}$ computations, which you will never every do.

Having said that, the reason to replace keys is because of the fear that they may be stolen by adversaries breaching your network. This has nothing to do with crypto, but is related to other risks.


How Shannon’s concept of perfect secrecy is linked with mutual information?

Almost—you changed letters partway through your question, so it's hard to be sure which mutual information you're discussing.

The attacker may know something about the message already: most messages are not uniform random noise, but highly structured.  For example, the attacker may know the message is either ‘DO NOT attack at dawn!’ or ‘YES, DO attack at dawn’.  The entropy of the message, in the attacker's state of knowledge, is exactly one bit; the entropy of the key and the ciphertext, however, had better be at least 176 bits, if the message is encoded in US-ASCII.

What you want is for the attacker's state of knowledge about the message to be the same even if they learn the ciphertext.  So you the mutual information of the message and the ciphertext to be zero: $I(M; C) = H(M) - H(M \mathrel| C) = 0$.  The mutual information of the key and the ciphertext $I(K; C)$ may be nonzero, e.g. in the above case it is pretty much guaranteed to be 1 bit, because knowing the key there's only two possibilities for the ciphertext.


Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?

Braid cryptography?  Knapsack cryptosystems, like Nasako–Murikami?

Lattice-based cryptography tends to work in polynomial rings or modules with coefficients in finite fields, but whose higher-level structure is not a field.

Also: don't forget RSA!  RSA works in a ring, not a field.


How is original plain text length reconstructed after decryption under RSA?

Most importantly, note that for almost all practical applications textbook RSA should not be used to encrypt something. It does not yield an encryption scheme which provides the guarantees one would expect in practice. In particular it does not even provide security against chosen plaintext attacks (IND-CPA).

Instead one would use some padding scheme such as optimal asymmetric encryption padding (OAEP).

Despite the fact that the usage of RSA you describe should not be used in practice, you would typically not pad "XXXXXXXXXXXX" as "XXXXXXXXXXXX000000....". Instead, you would encode "XXXXXXXXXXXX" as a number between 1 and N and use this upon encryption (i.e., you only implicitly prefix it with zeroes).


Where does the meaning of reduction to a hard problem lie?

The idea of proofs by reduction is that it should be possible to turn a real adversary into an algorithm doing some "useful" computation. So yes and yes.

However, sometimes, reductions are weak, in the sense that even if the real adversary is feasible (can be run in reasonable time on reasonable computers), the resulting algorithm doesn't have to be feasible. The algorithm can be constructed as a computer program, but it doesn't really work. So that's yes and no.

Sometimes, we also have even weaker proofs, so-called existence proofs. They only prove that if an adversary exists, then an algorithm doing some "useful" computation exists. Which means that even if we are given an adversary, we don't really know how to construct the algorithm doing that "useful" computation. So that's no and no.

Modern cryptography recognizes all of these differences. Reductions that work are best. Weak reductions are considered solid evidence of security, but leaves something to be desired. The even weaker reductions are sometimes considered evidence of security, and sometimes leave a lot to be desired.


Can I obtain the hashing algorithm if I know both the input and the output?

It is weird to assume a hash function is private. This contradicts Kerckhoffs's principle. If you are talking about keyed hash functions, then I think the answer is no in theory. They are typically used to construct message authentication codes like HMAC, of which the keys cannot be derived from several hash inputs/outputs.


Small solutions to modular arithmetic linear congruence

You can use lattice reduction to solve this problem.

Pick a large constant $S\in\mathbb Z$ and consider the lattice spanned by the rows of the following matrix:
$$
L = \begin{pmatrix}
S a & -1 & 0 & 0 \\
S b & 0 & -1 & 0 \\
S c & 0 & 0 & S \\
S p & 0 & 0 & 0 \\
\end{pmatrix}
$$

Now the crucial thing to notice is that some pair $(x,y)\in\mathbb Z^2$ is a solution to your modular equation if and only if $(0,x,y,S)$ is a vector in this lattice.

Moreover, some vector of the form $\vec v=(Sz,x,y,\pm S)$ must be part of a short basis, since $\begin{pmatrix}S c & 0 & 0 & S\end{pmatrix}$ is the only row of $L$ that is non-zero in the last column. Due to the large scaling factor $S$ in the first column, the vector $\vec v$ will in fact satisfy $z=0$, and therefore you can find a short solution by computing a reduced basis of $L$.

Here's a sage transcript that demonstrates this:

sage: p = next_prime(2**32)
sage: N = 1+floor(log(p,2)) # bit length
sage: S = 10**N
sage: a, b, c = randrange(p), randrange(p), randrange(p)
sage: a, b, c
(2206104035, 3690588304, 373686466)
sage: L = matrix(ZZ, [[S*a,-1,0,0], [S*b,0,-1,0], [S*c,0,0,S], [S*p,0,0,0]])
sage: L
[22061040350000000000                   -1                    0                    0]
[36905883040000000000                    0                   -1                    0]
[ 3736864660000000000                    0                    0          10000000000]
[42949673110000000000                    0                    0                    0]
sage: L.LLL()
[           0        49124        -7835            0]
[           0       -31049       -82479            0]
[-10000000000         2330       -37438            0]
[           0         4276       -42601  10000000000]
sage: (4276*a -42601*b) % p == c
True


Does this algorithm have a name? (Distance between letters)

This answer is expanding on @mentallurg's comment.
One of the important properties of a cipher is that you can decrypt. More precisely that there is an algorithm that takes in the cipher text and the private key and produces the correct plaintext. (Your scheme does not have a key, which is a separate problem with calling it a cipher).
So let's take your ciphertext "CgZcG HcFHs" and try decrypting it.
C = 3
g = -7
Z = 0
c = -3
G = 7

H = 8
c = -3
F = 6
H = 8
s = -19

So I know the distance between the fist and second letter is 3, but I don't know what the first letter actually is. If I knew the first letter then the rest would be uniquely determined. If your alphabet is [a-zA-Z] then there are 52 different plaintexts that would have produced this ciphertext, and the decryption algorithm has no way to know which of the 52 was the intended plaintext.


If we assume that DNS (DNSSEC) and IP (BGP) are well behaved, deployed and used correctly then so far so good. You should be reaching the intended server.

If however there is an adversary between you and this server, then they may interfere with the TLS handshake, including but not limited to altering the chosen ciphersuites and public keys. Any alterations are detectable when we pass the certificate verification, key exchange and authentication steps. However if the client doesn't do all the correct verifications, they may be vulnerable to Moxie's sslstrip tool, which performs various attacks.


Stretching definition of pseudo random number generator

The PRNG definition is quite simple. The following two distributions should be indistinguishable

$D_1() :
   Y \leftarrow \{0,1\}^m$;
   Return $Y;$

$D_2() :
   K\leftarrow \{0,1\}^\kappa$;
   Return $G(K)$;

Here, $G:\{0,1\}^\kappa \rightarrow \{0,1\}^m $is your PRNG function. It is required that the adversary knows everything about G, including the values you refer to. The only thing the adversary does not know is K.

A function is a PRNG if an (polynomial time) adversary who has oracle access to $D_i()$ can not tell if they are interacting with $D_1$ or $D_2$.

So yes, it's OK to have your numbers. They are simply part of the description of the PRNG.


Why is a non fixed-length encryption scheme worse than a fixed-length one?

The encryption scheme in the experiment you describe does not have to be fixed-length. We simply require that the two messages the adversary sends to its oracle have the same length. The restriction is on the adversary, not on the encryption algorithm.

So why do we put this requirement on the adversary? The reason is that in every practical encryption scheme, ciphertexts leak information about the length of the corresponding plaintexts --- the longer the plaintext, the longer the ciphertext. So cryptographers basically threw their hands up in the air and said, "Fine, we'll just concede that length-information leaks. Can we make sure no other information leaks?" Requiring the lengths of $m_0$ and $m_1$ to be the same ensures that the adversary can't guess which one was enrypted simply by looking at the length of the ciphertext it gets back. Therefore the experiment you describe measures an adversary's ability to find some other way that information leaks.


It all has to do with your requirements. If you want the server to have access to the data when the user logs in but not allow the server offline access. Then this scheme seems reasonable.
You have a second key which may or may not be needed. If each user has exactly one password and exactly one random key then you could use the password derived key directly.
You did specify how you encrypt the data, but AES GCM again would be reasonable.
You want to make sure you can verify they password. Use of GCM for the key or use of GCM for the data would suffice.
If the data encrypted is large, a second key allows changing password without reencrypting all of it. For small data I may recommend skipping the second key.
Be sure you use secure random number generators.
Be sure the password is sent to the server over a secure line(e.g SSL).
Some would advocate for doing hashing client side, which makes the server never have the clear text, and the client does the heavy computation, preventing some DOS attacks and some timing attacks.


What is the smallest size of the hash output?

To get a preimage resistance of 40 bits, you need a hash with at least a 40-bit digest. Finding a preimage for an $n$-bit hash typically requires performing $2^n$ attempts. A collision for an $n$-bit hash requires $2^{n/2}$. For a 40-bit hash, a preimage requires $2^{40}$ operations and a collision requires $2^{20}$.

Note that 40 bits of preimage resistance is typically not considered sufficient for most applications!


Peikert's framework for attacks on R-LWE: What "reduction modulo q" means?

Recall that any ideal $I$ of $R$ is in particular an additive subgroup of $R$, and that the quotient $R/I$ is the collection of cosets $a + I = \{a + i : i \in I\}$ for each $a \in R$.  Two cosets $a+I, b+I$ are equal iff $a-b \in I$.  The map that sends $a \in R$ to $a + I \in R/I$ is called "reduction modulo $I$," and often written "$a \bmod I$."  The quotient $R/I$ is a ring via the induced ring operations from $R$ itself: $(a+I) + (b+I) = (a+b) + I$ and similarly for multiplication.

Now suppose we have some ideal divisor $J$ of $I$, i.e., $J \supseteq I$.  The "natural" or "reduction mod $J$" homomorphism from $R/I$ to $R/J$ simply sends $a+I$ to $a+J$.  This is well defined because if $a+I = b+I$, then $a+J=b+J$ because $a - b \in I \subseteq J$.  (You can easily check that this is both an additive and multiplicative homomorphism.)

In the present setting, we have $I=qR$ and an ideal divisor $J = \mathfrak{q} \supseteq I$.  For a Ring-LWE sample $(a_i, b_i = s \cdot a_i + e_i)$, we should view $a_i \in R/qR$ as the coset $a_i + qR$.  Reducing it modulo $\mathfrak{q}$ just means sending it to the coset $a'_i = a_i + \mathfrak{q} \in R/\mathfrak{q}$.  Similarly, we send the coset $b_i + qR$ to the coset \begin{equation} b'_i = b_i + \mathfrak{q} = (s \cdot a_i + e_i) + \mathfrak{q} = (s \cdot a'_i + e_i) + \mathfrak{q}. \end{equation}
Note that the last equation holds because $s \in R$, $\mathfrak{q}$ is an ideal, and $(a_i - a'_i) = \mathfrak{q}$, so $s \cdot (a_i - a'_i) \subseteq \mathfrak{q}$.

The upshot of all this is that we can transform "mod $qR$" Ring-LWE samples $(a_i, b_i)$ into "mod $\mathfrak{q}$" samples $(a'_i, b'_i)$.  However, as the paper notes, if the error distribution $\psi$ is very "smooth" modulo $\mathfrak{q}$---i.e., if $e + \mathfrak{q}$ is very close to uniform for $e \gets \psi$---then the resulting sample is useless: $(a'_i, b'_i)$ is just uniform junk, and it's impossible (information theoretically) to recover anything about $s$ from it.


Yes there  are. The search term you are looking for is either "dishonest majority" (which doesn't necessarily mean n-1, but often that is the case) or "full-threshold". The SPDZ protocol is one that works in the malicious model that would meet your description.


Vulnerabilities if encrypting the same data with 2 different keys

You basically ask the following question: Is there a weakness anywhere if I encrypt the same message independently with 2 different keys?  To answer this, please consider the following:

The cipher text coming from a perfect encryption algorithm is indistinguishable from random data.
Practical encryption algorithms have some flaws, leading to ciphertexts that are not truely random.
Any hint in the encryption process (including implementation flaw, input data processing, ciphertext output etc) that would provide some statistical bias away from a "chaotic" process flow may help an attacker.
It is well established that using the same key to encrypt different messages may provide some hints regarding the encryption process. Looking from a "system" perspective, this is due to a strong bias in the input variables - the encryption key has no random differential value any more.
In your case, different keys but same message also have an input factor with no random differential value, namely the plaintext. So yes, this may provide some cryptanalysis hints to Eve.
The practical question would be - how strong is this hint? should I be concerned? well, if your are a researcher, then you can write a paper on this and present it in some conference. But if you are talking about real security in the field, I would say that this is still secure: AES 256 is well known cipher, and the attacks based on (4) above may reduce its strengh from 256 bit to several notches below that (and only if you encrypt insane amount of messages with the same key), but still it stays resistant (read: infeasible) now and in the foreseeable future to any breakage due to these input biases - especially when you talk about a fairly limited number of key sharing in your application.


Had to use the BP-Tools to clarify the output I am getting so as to know the main difference between the DUKPT-PIN and the DUKPT-DATA.

For the DUKPT-PIN: The entered PEK value will be XOR-ed with the value of 00000000000000FF 00000000000000FF (see ANSI X9.24-2004 Appendix A, A.5, page 42) as part of the processing.

For the DUKPT-DATA: As part of the processing, if the data variant key = tdesEnc(key, key);is checked XORing it with  0000000000FF0000 0000000000FF0000

All i need to do was just to comment out the  key = tdesEnc(key, key); which serves the same function as that of the Data Variant which is not used in the process of carrying out DUKPT-PIN


I like the didactic approach in this answer. But for something that behaves more like a hash function should, we might define $H$ for strings of digits $s$ as: $H(s)=(((1||s)\bmod 97)||s)\bmod 99991$ where $a||s$ is the number resulting from prepending the decimal representation of $a$ to the string $s$.

Worked out example for $H(012345678)$
$=(((1||012345678)\bmod 97)||012345678)\bmod 99991$
$=((1012345678\bmod 97)||012345678)\bmod 99991$
$=(37||012345678)\bmod 99991$
$=37012345678\bmod 99991$
$=77082$.

With some math insight and very little extra computational effort, one can exhibit a collision; a "brute force" search for collision is also feasible with simple use of a spreadsheet.


What kind of adversary is a compromised party?

I believe what you are describing is somewhat orthogonal to typical MPC adversary models. Typically in MPC we let the adversary know all information that corrupt parties know (so if a corrupt party learns the output, the adversary is allowed to learn the output). What we care about in MPC protocols is that the adversary is not able to learn any additional information (e.g., inputs of uncorrupted parties, intermediate computation results, etc).

So, if the adversary has corrupted Alice, and Alice is intended to get the results, then the adversary is allowed to know the result and that is okay by the definition of MPC. In that case, the adversary could very well indeed be a passive adversary. You could consider it an adaptive adversary if they don't know to attack Alice in the beginning, but figure that out during execution, corrupt her, learn the output.

So, say for example we are using MPC to tally votes and the vote tally is revealed to Alice at the end of the protocol. The fact that the adversary corrupts Alice and learns the vote tally at the end is okay and still meets the security definitions of MPC. What she shouldn't be able to learn is an individual's vote.

To fix this, say let Alice learn the vote tally only if she is not corrupt, then we need some way of detecting whether or not she is corrupt.


What kind of information in cryptography is called semantic information?

I'm not an expert but...

Semantic analysis is a concept not from cryptography but more from machine learning. The goal is for an AI to learn semantic information from some base set of inputs. For example we might train an AI to detect whether a arbitrary image contains a dog.

For the purposes of encryption an AI might learn to recognize an individual from a camera, microphone, and/or other inputs. In this case the "semantic information" would be the individual's characteristics necessary for an AI to identify that person from such external data.


Time-locked Puzzles & Dead Man's Switch Intervention

Creating a function that can’t be solved in N time
Some assumptions need to be addressed to adequately answer this question; the first is to establish that there are different protocols provided a scenario with an honest/dishonest Bob. In a scenario where Bob only acts honestly the solution, to creating a function that can’t be solved in N time, is less of a cryptographic discussion and more of a software portability issue. In addition it will be assumed that all encryption and decryption methods are public information.
The definition of a dead man’s switch
Now I’ll assume that when you refer to a dead man’s switch you’re referring to a system that executes some task when there is the absence of user interaction, and that this particular system is implemented in software. Most non-mechanical dead man’s switches are limited by the reliability of the power source and energy storage, and thus become uninteresting.
Assuming a dishonest Bob
Now in this scenario we will assume that Bob will try to cheat and find a method to decipher the message in time less than N. Being able to decipher the message in time greater than N is of no particular interest or even an issue.  So then the burden falls to Alice to prove that her particular decryption method is the fastest that exists, and to ensure that in the event that a faster method is discovered, that she is able to identify the cheating party. Furthermore Alice must ensure that her decryption system is sequential in so far as it can’t easily be run in parallel on a distributed computer network.
Discovering a cheating party is matter of recording the time stamp immediately after generating the message with expected decryption time of N, and by then calculating the time differential after the receipt of the decrypted message. Now assuming Alice has discovered a cheating party she must infer the capabilities of the attacker.

Did Bob discover a faster decryption method?
Possible

Does Bob have more computational resources?
Possible

Did Bob execute a pre-computation attack?
Not Possible :)

In addition Alice must assume at all times there is the possibility of silent failure: Where Bob could have completed two of the previously mentioned attacks, decrypted the original message before there was any system intervention, and is sitting on the cryptographic equivalent of a dirty-bomb.
Alice’s system intervention
As I understand your question you’re interested in a system where Alice could actively manipulate the expected decryption time N. In which case Bob would need to be interacting with a system where Alice has read/write access. Bob would also need a method to know when decryption was successfully completed without knowing the required decryption time N, or the original message that was encrypted. Alice also would need a method for periodic intervention WITHOUT changing the original encrypted master secret.
This is based on the assumption that the dead man switch would be used to distribute a static master secret (MS). Alice encrypts a message (M) with expected decryption time X, and issues cipher (C) to Bob. At some point before the expected decryption time X Alice needs to change the decryption time X by Y. Now this is just a bad idea because it will be more complicated to predict the computational capabilities of Bob, which is pretty much the only point of this exercise….but I digress. Then Alice computes the new cipher (C’), and issues the new value to Bob. But as Daniel pointed out Bob could just as easily continue to decrypt the original cipher (C) to recover the original message (M) independently of the new cipher (C’). So it’s likely that the secret key would be some variable time value (T’) to recover a non-secret and non-random message (M’).
This would be the indicator message to relay to Bob that decryption was completed. Bob would then use the variable time value (T’) and attempt to decrypt some master secret (MS). If decryption was unsuccessful Bob would continue to decrypt the most recently distributed cipher (C’). The issue is that Alice could just as easily distribute the master secret (MS) without having to distribute all the false variable time (T’) secrets for decrypting the master secret (MS). The triggering system would remain unchanged, and thus there would be no reason for variable time (T’) values. As such all continued interaction between Alice and the dead man switch would serve only to distribute the master secret (MS).
Third Party
A system where the master secret (MS) is delivered to a trusted third party would be possible only when implemented in a completely mechanical system. Given the fallibility of humans and the inherent possibility of system compromise. The United States Postal Service would be the best delivery method.
tl;dr
This system will provide no fail-safe for Alice. If this is wrong please edit.


Elliptic Curves and Finite Abelian Groups

Let $E$ be an elliptic curve over a finite field $K$ with an order $n$ such that $n =p_1^{a_1}\dots p_k^{a_k}$. The order is the number of rational points of the curve.
There are various point for a curve to be secure;

Discrete logarithm
The basic security of ECC is the Dlog that is given a base point $G$ and another point $P$ with $P= [x]G$
There are many Dlog algorithms, however, two of them are important here

Pollards' Rho and this defines the bound; that is a curve with $n$ elements the cost of Pollard's $\rho$ is $\mathcal{O}(\sqrt{n})$, therefore a curve with $n$ point cannot be secure than this.

Pohlig-Hellman is applicable if $n$ is a smooth integer. It has  $$\mathcal O\left(\sum_i {a_i(\log n+\sqrt {p_i})}\right)$$ time complexity where $\prod_i p_i^{a_i}$ is the prime factorization of group order $n$.

To mitigate this attack this attack a prime order must be selected than is has same worst-case complexity as $\mathcal{O}(\sqrt{n}\log n)$-time. Or the order must have at least one large factor where DLog is hard.
If you are looking an example then this curve $E(F_p) : y^2 = x^3 + 7x + 1$ with $p = 9254331510119 $ is a concrete case for Pohlig-Hellman.

Co-factor
Co-factor $h$ is defined as $h = \#E(K)/n$. We want the cofactor small or equal to 1. If not, then;
The attacker may choose one of the small sub-group to use the Lim–Lee active small-subgroup attacks. This attack is very effective if the $n$ has many small factors. Then, the attackers can use CRT to combine the results.
For each query the attacker can reveal by $[a]P$ is at most $\lceil log_2 h\rceil$ bits. To mitigate this a curve with co-factor is small or 1 or a strict point validation is required.

The above are the obvious security issues when the order is of the form $\prod_i p_i^{a_i}$ for some distinct primes $p_i$ and $a_i \in \mathbb{Z}^+$. The list, however, is not complete;

The twist security
From the factorization, one can say that our curve's one of the primes is large enough to be secure against DLog. If the attacker sends a point on the twist with low order, then can use Lim-Lee's attack to combine the results. To mitigate, a curve with a large prime factor of the twisted order is required as in Curve25519 and point validation!

And, more see in safecurves


Does the MixColumns step come before or after AddRoundKey in AES decryption?

InvMixColumns is a linear operation. And because of that it follows:

InvMixColumn(x+RoundKey) = InvMixColumn(x) + InvMixColumn(RoundKey)
                                             ^^^^^^^^^^^^^^^^^^^^^^
                                         "new" round key for decryption

So, the structure on the right is compatible with the structure on the left as long as you use different round keys. The idea behind this is to make the decryption structure look like encryption structure with just a couple of "Inv"s in there. But I'm actually not sure what the benefit of this is. For a block cipher like Anubis (which is similar to AES) it makes much more sense because each operation is an involution. The only difference between encryption and decryption for Anubis are the round keys. So, you can reuse the encryption code for decryption which is a nice property.


What's the perfect chain length : number of chains ratio for rainbow tables?

I'm building a SHA-1 rainbow table to crack basic passwords (i.e. up to 10 character, 0-9,a-z), but I can't seem to calculate that golden ratio that would give me the most coverage. What ration of chain length to number of chains should be chosen?

That choice is not really about coverage, but (mainly) about how much space you are willing to use. You should choose the number of chains based on how much space you can use, since each chain uses a constant amount independent of its length. Then you can choose the chain length to get the coverage you need or based on the amount of computational effort you can spend on creating the table.

  Also is there anyway to estimate the coverage of the table?

Yes. You will find a formula for the probability of success in the seminal paper by Philippe Oechslin (pdf):

  The probability of success within a single table of size $m × t$ is given by:

  $$P_{table} = \Pi_{i=1}^{t} (1 - \frac{m_i}{N})$$
  where $m_1 = m$ and $m_{n+1} = N (1 - e^{-\frac{m_n}{N}})$

Note that in your case you will likely not be able to generate a rainbow table with good coverage unless you invest quite a bit of effort. Your search space is larger than $35^{10} \approx 2^{51.3}$, so to get even 50% coverage you would need to compute more than $2^{50}$ hashes, taking several years of CPU time with a typical desktop CPU.

As long as your coverage is low you can get a decent approximation by assuming you have no collisions, i.e. just divide the product of chain count and chain length by the size of the search space.


Rainbow table for DES with all-zero plaintext?

Given a function $F: A \rightarrow B$ and functions $R_1, R_2, \dots, R_k:B \rightarrow A$, we can create a chain of length $k$ from a starting point $a_0$ to an end point $a_k$ using $a_i = R_i(F(a_{i-1}))$.

A rainbow table for $(F, R_1, \dots, R_k, k)$ is a collection of chains with end points $(a_0, a_k)$ organized so that searching for chains ending at $a_k$ is cheap.

We use a rainbow table to (try to) invert $F$ as follows. Given $b$, we compute $u_{11}, u_{12}, \dots, u_{1k}, u_{22}, u_{23}, \dots, u_{kk}$ using the equations $$u_{ii} = R_i(b) \qquad\text{and}\qquad u_{ij} = R_j(F(u_{i,j-1})).$$ After computing each $u_{ij}$, we check to see if there is a chain $(a_0, u_i)$ in the rainbow table. If there is, we compute $a_1, a_2, \dots, a_k$ as above and check if $F(a_j) = b$ for some $j$. If so, we have found a preimage of $b$ and we are done. Otherwise, we continue until we have checked all $u_{ij}$.

The idea is that the $R_i$ are very cheap to compute (compared to $F$), so generating a rainbow table for $(F,R_1, \dots, R_k, k)$ with $L$ entries requires storing $2L$ elements of $A$ and costs essentially $kL$ evaluations of $F$ plus the cost of organizing the table ($O(L \log L)$ or something similar?).

Each lookup costs at most roughly $k^2$ evaluations of $F$ plus the cost of $k^2$ table lookups (each $O(\log L)$ comparisons of elements of $A$ or something similar?).

The total cost for $n$ attempted inversions should be dominated by $kL + k^2n$ evaluations of $F$.

The tricky part (the part where I don't immediately know the answer) is determining fraction of elements of $A$ for which $F$ can be inverted. This is determined by the total number of distinct elements present in the chains in the rainbow table.

It would seem that if the $s$ first chains cover a fraction $\epsilon$ of $A$, then the $s+1$th chain will contain an expected $(1-\epsilon) (1-\epsilon/k)/(\epsilon/k)$ "new" elements of $A$ (or $k$ if $\epsilon/k$ is small). (The second term in the product is the expected number of iterations in the chain before it collides with a previous chain at the same index. The first term is the expected number of repetitions.)

This should mean that a rainbow table can cover a significant fraction of $A$.

When $kL$ is not too big compared to $|A|$, I would guess that the probability of inversion is close to $kL/|A|$.

If you are ok with a probability $\epsilon$ of inverting $F$ significantly smaller than $1$:

A rainbow table with parameters $k$ and $L = \epsilon |A|/k$ inverts $n \epsilon$ elements using $\epsilon |A| + k^2n$ evaluations of $F$ and storage of $2\epsilon |A|/k$ elements of $A$.
A straight-forward table for a fraction $\epsilon$ of the elements of $A$ inverts $n\epsilon$ elements using $\epsilon |A|$ evaluations of $F$ and storage of $\epsilon |A|$ elements of $A$ and $B$.
A sequence of brute force searches for a fraction $\epsilon$ of the elements of $A$ inverts $n\epsilon$ elements using $\epsilon |A|$ evaluations of $F$ and negligible storage.

Suppose you have $n=2^{10}$ target keys and have $2^{40}$ octets of fast memory available for the table. A pair of DES keys requires 14 bytes, which gives us $L \approx 2^{36}$. Choosing $\epsilon = 2^{-10}$, we find that $k=2^{-10} \cdot 2^{56} / 2^{36} = 2^{10}$, which means a total work factor of $2^{46} + 2^{30}$ DES evaluations. (If you use slow memory, memory access time will probably be much higher than DES evaluation time.)


What is a man-in-the-middle attack (for instance in Diffie-Hellman)?

in diffie-hellman key exchange algorithm vulnerability's is good defined by RSA lab :

"The Diffie-Hellman key exchange is vulnerable to a man-in-the-middle attack. In this attack, an opponent Carol intercepts Alice's public value and sends her own public value to Bob. When Bob transmits his public value, Carol substitutes it with her own and sends it to Alice. Carol and Alice thus agree on one shared key and Carol and Bob agree on another shared key. After this exchange, Carol simply decrypts any messages sent out by Alice or Bob, and then reads and possibly modifies them before re-encrypting with the appropriate key and transmitting them to the other party. This vulnerability is present because Diffie-Hellman key exchange does not authenticate the participants. Possible solutions include the use of digital signatures and other protocol variants."

and some simple example of mitm attack :

Alice "Hi Bob, it's Alice. Give me your key." →     Mallory     Bob
Alice     Mallory "Hi Bob, it's Alice. Give me your key." →     Bob
Alice     Mallory     ← [Bob's key] Bob
Alice     ← [Mallory's key] Mallory     Bob
Alice "Meet me at the bus stop!" [encrypted with Mallory's key] →     Mallory     Bob
Alice     Mallory "Meet me in the windowless van on 22nd Ave!" [encrypted with Bob's key] →     Bob


Maintaining validity of ZKP throughout re-randomization of homomorphic ciphertext without linkability to previous ciphertext

First (if it's not the case) you have to read carefully the original Groth-Sahai paper : https://eprint.iacr.org/2007/155.pdf

We can focus on a concrete example to understand why it's possible: in the "SXDH" setting for example (page 24);
Let suppose we have a commit $\vec{c_1}$ for a vector of elements of $G_1$ and
a commit $\vec{c_2}$ for a vector of elements of $G_2$. And a proof $(\vec \pi, \vec \theta) $

You can change randomize the commitment $c_2$ (by adding $R'\vec{u}$ to $\vec{c}$ for example), but if you do this the proof will be no more valid.

Then you have to add also the corresponding randomness to the proof, here it means you have to add to $\vec\pi$ $R'\Gamma c_2$.

More generally you have to randomize the commitment and the proof in the same time (Notice that in the groth sahai model commits are not considered as cipher but as part of the proof).


What is the impact of a server not fully verifying the data in the Client Finished packet of a TLS connection?

Suppose the server does not check the Client Finished value.  This means that the MITM could change some handshake messages and the server would not know this (e.g., downgrade, as you mentioned).  So, you could use this to fool a server that doesn't check the Client Finished value.

If n bits are checked by the server, you have a 1/2^n chance of getting the Client Finished value right by random chance.  You might be able to predict the remaining client messages and then use brute force to try different random handshake modifications offline until one generates the correct finished bits in the n locations that the server will validate.  This will take about 2^n tries, which for small n is feasible.  By sending this handshake sequence you can fool the server into thinking the client sent the modified handshakes.

Now, the server sends back a Server Finished message, which includes a hash of all the messages the server has seen, including the Client Finished value.  Your modified handshakes will completely change the hash value for the Server Finished.  As a result, you're stuck having to brute-force all the bits that the client checks in addition to those the server checks.  If the client is lazy and only checks m bits, then overall you're looking at 2^(n+m) tries, which might be feasible.  However, if the client validates the full server finished, you'll have to break all 12 bytes, or 96 bits, which won't be easy to brute force before the connection times out.

Security (defined here as the number of brute force attempts to get the two Finished messages to validate) depends roughly on the total number of bits the client and server check, so if the server does not check any bits then the security relies, as you said, on the client's validation of the Server Finished message.

You mentioned changing the master secret.  This could allow the MITM to create a valid connection to the server (e.g., if RSA key exchange is used).  However, the MITM does not know the master secret the client is using, since the server private key is required, so for the Server Finished message you have the problem of determining the encryption and MAC keys.  If you negotiate a weak cipher suite with the client, this might be easier than brute forcing the Server Finished message.

Other attacks may be possible based on the configuration of the client and server, so it's best if the server fully validates the Client Hello to mitigate them.


Speeding up partially known plaintext preimage recovery attack on MD5

It sounds like you're pretty much out of luck.

Yes, there are a few tricks you could use to speed up a brute force search; for example, if we fix everything other than DWORD 3 of B, we can precompute everything up to round 10 of MD5, and compute what the value of the internal 'b' variable of round 52 of MD5 must be to generate the expected hash; this reduces the total number of rounds we compute to 42 (plus a few extra checks that we occasionally do if 'b' happens to be the value we expect, plus redoing the precomputation when we've gone through all possible values of DWORD 3 of B, and we need to try another value for DWORD 1,2,4).

However, such tricks don't come anywhere close to giving you a practical solution.  In fact, even if we were to optimize the time to test a value of 'B' to one CPU clock cycle, and ran the test on one billion CPUs, find a value of B that gives the specified hash would take an expected time considerably longer than the age of the universe.

What you would need is to have a cryptographical weakness in MD5 which would allow you to find such a value without doing an exhaustive search.  Yes, there are a number of weaknesses known with MD5; there's none that gives you this.


Cryptopals challenge - not understanding the padding details

This is expected behavior when you try to display the byte 0x04, which is not a printable ASCII character.

Padding schemes like pkcs7 operate on byte sequences, not ASCII strings. In general, ciphers and padding routines only care about byte sequences; whether a specific byte corresponds to a printable ASCII character is not important.

The routine uses the byte 0x04 as opposed to the ASCII character 4 (0x34) because it doesn't know or care about ASCII. Also, using decimal digits 0-9 would mean padding can be at most 10 bytes long.

When viewing byte strings in python, you should avoid casting to a string, just keep it as a byte array instead. For debugging, you can do something like

 print pad_pkcs7(buffer, 20).__repr__()


What's the difference between "HashX-512" and "HashX-1024"?

Internally, Skein-1024 uses the Threefish-1024 compression function and is extended to 1024 bits of internal state whereas Skein-512 uses the Threefish-512 compression function. There are a few additional changes but they are very similar (just like SHA-256 and SHA-512 are, for instance).

The tweak handling is, however, the same since all Threefish variants have the same 128-bit tweak size, so if you do have access to the Skein-512 source code, you should be able to modify it so that it calls Threefish-1024, make the necessary length adjustements, and it should work without too much pain.

Other than that, no, there is no parallel between the two functions that will let you compute a Skein-1024 hash from a Skein-512 one. The two Threefish functions have different constants & number of rounds.

Why do you need Skein-1024, by the way? Unless you really need the 1024-bit internal state, which is unlikely and overkill, you can just use the "arbitrary output length" feature of all Skein variants, which allows you to produce a digest of arbitrary length. It is described in the Skein paper and is hopefully available within your Skein implementation. If it isn't, the implementation is incomplete.


The security - assuming you can validate the correctness of $K$ - is 56 bits (not even counting any attacks on DES itself, assuming to test all keys). This is because you can brute force $K_{BT}$ without even looking at $K_{AT}$ in your particular scheme.

[EDIT] I'll explain: lets assume that the correctness of the AES key $K$ can be verified by looking at known plaintext / ciphertext pairs. Knowing $K_{BT}$ unlocks the key $K$, which can then be verified. Hence brute forcing $K_{BT}$ is enough to find the right $K$. And $K_{BT}$ has a security level of 56 bits. You can completely ignore $K_{AT}$, it doesn't offer any additional security at all. Minor note: this will cost you at least 5 decrypts (4 DES encrypts or decrypts for retrieving the AES key and one AES encrypt or decrypt to verify correctness).

2 key triple DES on the other hand would at least offer over 80 bit security. So this scheme is certainly not the best option available if you have 112 bits of entropy for your key.


RSA - source and image - all are possible?

If you're asking whether the power map $x\mapsto x^a \pmod n$ is injective, it suffices to take $a$ with $1 < a < \phi(n)$ and $\gcd(a,\phi(n)) = 1$.

Edit:  I couldn't complete the answer earlier. As mentioned in the comments $gcd(a,n)$ is enough, but for computational efficiency one might as well take $a \pmod n$ as the exponent. In the RSA setup, $n$ is square free thus the function is bijective.

To see this, note that after all $e,d$ have similar roles and if one of them, say $e$, satisfies $\gcd(e,n)=1,$ then there is an integer $f$ such that $ed+fn=1$ (by the fact that they are inverses) thus demonstrating $gcd(d,n)=1.$)


That depends on how you define sufficient. AES achieves full diffusion after only two rounds, where diffusion is defined as the ability for every bit in the state to affect every other bit. That does not mean that a mere two rounds can protect against cryptanalysis. The number of rounds necessary to avoid fatal cryptanalysis is something that can only be chosen by studying the cipher and attempting to break it. During the AES standardization process, the cipher Rijndael, which became AES, was given 10 rounds for the 128-bit key size because the best attack against it could break 6 rounds. The extra rounds were considered to be a safety net, or security margin, against future advances in cryptographic attacks.

Is this always going to be sufficient? We don't know. Right now, no attack more efficient than exhaustive search is known that can break every round in the cipher in order to violate its security properties. Some have argued that 10 rounds is not enough, and even suggested that it be raised to 18 or 24 during the AES process, but that never happened and it was standardized as 10, 12, and 14 rounds for each key size. However, as the years have passed, we still do not have any cryptanalysis that breaks every round.


How to create and send a symmetric key using GPG

First of all let me answer your specific points:

No, generating a symmetric RSA key makes no sense. RSA is not symmetric. It is a public key algorithm.
There is a HUGE difference between the public and private key. The public one can only be used to encrypt and the private one is needed for decryption.
Usually in a public key setting you keep the private key private and don't send it anywhere.

I'm afraid I have to disagree with your statement that you are pretty familiar with public key cryptography. You should probably read up on the difference between symmetric crypto and public key crypto again.

Even if you use public key crypto, you need to somehow verify that the person whose public key you are using is actually the person you want to reach. Otherwise anybody could give you their public key and MitM your connection. If you know somebody only over the internet how do you know who they are anyway?


Recovering public key with small R parameter

It is error in my recovery procedure, or signing should be bad for nonce which generate small $r$ parameter?

The issue happens because the recovery procedure is a simplified version of the standard method, attributed to Daniel R. L. Brown of Certicom.
Problem happens I guess when in signing, r does not match p.x.value; that is when p.x.value lies in $[n,p)$, where $n$ is the Elliptic Curve group order, and $p$ is the field order.
That has probability about $1-n/p$ to occur by chance. With non-toy parameters that's negligible, e.g. $\approx2^{-127.65}$ for sepk256k1.
If that needed to be avoided for small parameters, we could use the full method, or I guess fix the signature to fail (thus be retried with a different nonce) when the problematic condition arises. Just replace r==0 with p.x.value >= CurvePoint16::ORDER (and perhaps move that up one line).


Say you have the value $n$ which is the size of the alphabet (i.e. the range of characters that make up your plaintext and ciphertext). And say $m = x \times n$ is the largest value you have that is not higher than $y$ where $y$ is the largest size produced by your random number generator.

For each character:

Take values from the random number generator until you have a value smaller than $m$, call this value $r_i$;
Calculate $s_i$ which is simply $r_i \bmod n$;
Calculate $p_i$ which is the location of the current character in your alphabet;
Calculate $c_i = (p_i + s_i) \bmod n$
Take the character at location $c_i$ of the alphabet and display.

To reverse:

Take values from the random number generator until you have a value smaller than $m$, call this value $r_i$;
Calculate $s_i$ which is simply $r_i \bmod n$;
Calculate $c_i$ which is the location of the current character in your alphabet (the first character in the alphabet is on position 0);
Calculate $p_i = (c_i - s_i) \bmod n$
Take the character at location $p_i$ of the alphabet and display.

In the above calculations I presume that the random number generator produces numbers from $0$ up to $y$ (so without $y$). The characters are in an alphabet where they have an index from $0$ up to $n$ (so without $n$).

If $y = n$ (the maximum value of the random number generator is the same as the size of the alphabet) then the scheme is of course simpler. You can just take the next value of the random number generator and call it $s_i$, skipping the first two steps.

Example implementation in Java (sorry, don't know Python that well):

import java.nio.charset.StandardCharsets;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;

public class StreamCryptUsingAlphabet {

    private String alphabet;
    private int n;
    private int y;
    private int m;

    private SecureRandom rng;

    public StreamCryptUsingAlphabet(String alphabet, int y) {
        this.alphabet = alphabet;
        this.n = alphabet.length();
        if (y < n) {
            throw new IllegalArgumentException("y is too small");
        }

        this.y = y;
        // % is the remainder operator, same as modulus for positive numbers
        this.m = y - y % n;
    }

    public void init(byte[] seed) {
        try {
            rng = SecureRandom.getInstance("SHA1PRNG");
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException("RNG not available");
        }
        rng.setSeed(seed);
    }

    private int nextS() {
        int r;
        do {
            r = rng.nextInt(y);
        } while (r >= m);
        return r % n;
    }

    public String encrypt(String plaintext) {
        String ciphertext = "";
        for (int i = 0; i < plaintext.length(); i++) {
            int p = indexInAlphabet(plaintext.charAt(i));
            int s = nextS();
            int c = (p + s) % n;
            ciphertext += characterInAlphabet(c);
        }
        return ciphertext;
    }

    public String decrypt(String ciphertext) {
        String plaintext = "";
        for (int i = 0; i < ciphertext.length(); i++) {
            int c = indexInAlphabet(ciphertext.charAt(i));
            int s = nextS();
            // Java's remainder requires me to add n first
            int p = (c - s + n) % n;
            plaintext += characterInAlphabet(p);
        }
        return plaintext;
    }

    private int indexInAlphabet(char c) {
        String s = String.valueOf(c);
        return alphabet.indexOf(s);
    }

    private char characterInAlphabet(int i) {
        return alphabet.charAt(i);
    }

    public static void main(String[] args) {
        byte[] key = "Khan".getBytes(StandardCharsets.US_ASCII);

        StreamCryptUsingAlphabet sc = new StreamCryptUsingAlphabet(
                "abcdefghijklmnopqrstuvwxyz", 80);

        sc.init(key);
        String ct = sc.encrypt("owlstead");

        sc.init("Khan".getBytes(StandardCharsets.US_ASCII));
        String pt = sc.decrypt(ct);
        System.out.println(pt);
    }
}

The next part explains what is usually done if a key stream which is a stream of pseudo random bits...

Normally, if you've generated a random key stream, then we use XOR to encrypt the plain text. For this the plaintext needs to be binary as well. So if the plaintext is actually text, we need to perform character encoding on it. Commonly used encodings are US ASCII and UTF-8. This will however result in a binary ciphertext, so if you want to represent it as a string, you can use base 64 encoding.

To decrypt you first base 64 decode the data you've received to retrieve the ciphertext. Then you decrypt, and afterwards you use character decoding to retrieve the text from the binary plaintext.

So the above is what is usually done within computers.


Why does a transcript which is indistinguishable from a fake one show zero knowledge?

The information that the verifier gets is all contained in the real transcript. On the other hand, the verifier generates the simulated or fake transcript without interacting with the prover, so all information contained in such a fake transcript is nothing beyond the given fact that "the statement to be proved is true". Now if the real transcript is indistinguishable from the fake one for any adversary with reasonable resources, then clearly these two transcripts contain the same amount of information. Therefore, the real transcript does not leak any information beyond the given fact, i.e., it is zero-knowledge.


How long would it take to crack a double hash if salt and final hash are public?

A SHA3-512 hash outputs 512 bits. If you use that as input to the second application of the hash then it takes $2^{511}$ tries - on average - to brute force it. This is obviously far out of range of a practical attack.

The one thing that could be performed is to try to guess the input of the first hash: the file content. If this can be guessed then the scheme would be broken. The file could be very short or it may just not contain enough entropy, regardless of the size. For instance, if you'd use the copy of the MP4 version of Kill Bill 1 and somebody knows that you like the movie, the hash may be relatively easy to guess.


Multithreading PBKDF2 or javascript alternative

Yes, this would improve security. In fact, you do not even need to use individual salts. Simply concatenating the thread number as a counter with the input key would be enough:

Input: k, a short key to be strengthened with a KDF
Output: h, the final output hash

spawn_thread(h0 := slow_KDF(k || 0))
spawn_thread(h1 := slow_KDF(k || 1))
spawn_thread(h2 := slow_KDF(k || 2))
...
spawn_thread(hn := slow_KDF(k || n))

wait_for_all_threads()

h := fast_hash(h0 || h1 || h2 || ... || hn)

However, this is not particularly efficient. Every time you double the number of threads (assuming each thread is truly independent and not sharing any resources), you add the equivalent of one bit of security. A single extra byte added to the input provides the equivalent increase in difficulty as running this on a system with 256 independent hardware threads. Assuming you will not get more than 8 parallel KDF instances, you will never increase security by more than a mere 3 bits...

Instead, you should be using a KDF that is memory-hard, preventing an attacker from using a GPU or ASIC from parallelizing an attack against PBKDF2. An example would be Argon2, which natively supports parallelism in addition to a configurable amount of memory.


Maximum allowable correlation for a random sequence to be useful?

There is no limit as to the amount of correlation you can have from an entropy source for it to be useful, but correlation then places a restriction on how you extract the entropy.

The restriction is this:  you have to individually process an entropy block of a size that exceeds the length of correlation.  Thus no correlation between blocks.  For a Geiger tube you might have a slight settlement time after each reading that might be of length (n + 10).  That means you have to deal with blocks of readings greater than 10.  I use a web cam that outputs 25KB images, so I have to treat that as a full 25KB block (n+25K) to extract the entropy.  If I try to process the image on a byte by byte basis, I fall foul of the JPEG file format that envelops the true entropy within the image.

Correlation is  impossible to remove programmatically as that requires a complete theoretic model of the underlying physics of the source.  My suggestion is to side step it and consume entropy in blocks greater than any possible length of auto correlation.  If you're reading noise it might only be at most (n+2) anyway.

From your blog post that initiated all this:-

  /dev/urandom is a pseudo random number generator, a PRNG, while /dev/random is a “true” random number generator.

I would argue that both random and urandom are pseudo random number generators, and you are just comparing like with like and getting differing results!  /dev/random breaks my no more entropy out than in rule from this post hence I think that it's not a TRNG at all.


Diffie-Hellman: Does the size of the prime modulus depend on the potential size of the secret?

Well, for one thing, you are not using a "One Time Pad".  A "One Time Pad" means, by definition, that someone generates a pad of numbers using true randomness (and not algorithmicly), and that no potential adversary has any information on what that pad may contain.  Then, that pad is given to both the sender and the receiver, and then the sender uses it to disguise the plaintext, in a way that the receiver (with the pad) can recover the plaintext, but the adversary, who doesn't have the pad, gets no information about the plaintext (because with the ciphertext and any potential plaintext, there is a possible pad that makes that possible, and the adversary has no way of deciding which potential pad is more likely.

Instead, you are performing a series of Diffie-Hellman operations to generate shared secrets, and then using those shared secrets to perform a stream encryption.

Here is why this is distinction is important; you state:

  the only way to break this is through exhaustive search; since OTP cryptext contains no information about the original message

This would indeed be true, if you were using an OTP; the attacker would literally have no information beyond the ciphertext, and the ciphertext would indeed reveal no information about the plaintext.  However, the ciphertext is not the only thing the sender and receiver are exchanging, you mention previously that:

  the user and the server exchange their public keys

That is, there is information available to the attacker in addition to the ciphertext that he can use.  That is, instead of being informationally secure (which OTP is), you also hope that the attacker cannot use the public keys to recover the shared secret (pads), that is, you hope that the problem of recovering the shared secret is just too difficult for the attacker.  In other words, you hope that you are computationally secure.

Here, in that light, when you ask:

  is there a problem with the prime modulus being so small?

The question you are asking is "is Diffie-Hellman computationally secure, even if the modulus is tiny".  The answer to that is "no, it is not".  For MODP groups (which are the groups you are using), it appears that DH can be broken unless the modulus is at least 800 bits (actually, attacks against modulii that size haven't actually been demonstrated, but there have been attacks against related primitives, and we believe those attacks can be converted into attacks against Diffie-Hellman).

There are other groups that can be made smaller and still are believed to be secure (for example, an elliptic curve group is probably pretty secure even if the curve is only 200 bits or so); however you won't get anywhere close to "an ASCII value".

When we use Diffie-Hellman like this, what we generally do is perform a single Diffie-Hellman operation to generate a single (large) shared secret, and then give that shared secret to a Key Derivation Function; the output of that KDF may be then presented to a Stream Cipher, whose output is then used to actually encrypt the data


C# implementation of curve25519 to ed25519 conversions

In a Ref10 based implementation, the conversion should look something like this:

public static void EdwardsToMontgomeryX(out FieldElement montgomeryX, ref FieldElement edwardsY, ref FieldElement edwardsZ)
{
    // montgomeryX = (edwardsZ + edwardsY) / (edwardsZ - edwardsY)
    FieldElement tempX, tempZ;
    FieldOperations.fe_add(out tempX, ref edwardsZ, ref edwardsY);
    FieldOperations.fe_sub(out tempZ, ref edwardsZ, ref edwardsY);
    FieldOperations.fe_invert(out tempZ, ref tempZ);
    FieldOperations.fe_mul(out montgomeryX, ref tempX, ref tempZ);
}

public static void MontgomeryXToEdwards(out FieldElement edwardsY, ref FieldElement montgomeryX, ref FieldElement montgomeryZ)
{
    // edwardsY = (montgomeryX - montgomeryZ) / (montgomeryX + montgomeryZ)
    FieldElement tempY, tempZ;
    FieldOperations.fe_sub(out tempY, ref montgomeryX, ref montgomeryZ);
    FieldOperations.fe_add(out tempZ, ref montgomeryX, ref montgomeryZ);
    FieldOperations.fe_invert(out tempZ, ref tempZ);
    FieldOperations.fe_mul(out edwardsY, ref tempY, ref tempZ);
}

public static void EdwardsToMontgomery(ArraySegment<byte> montgomery, ArraySegment<byte> edwards)
{
    FieldElement edwardsY, edwardsZ, montgomeryX;
    FieldOperations.fe_frombytes(out edwardsY, edwards.Array, edwards.Offset);
    FieldOperations.fe_1(out edwardsZ);
    EdwardsToMontgomeryX(out montgomeryX, ref edwardsY, ref edwardsZ);
    FieldOperations.fe_tobytes(montgomery.Array, montgomery.Offset, ref montgomeryX);
    montgomery.Array[montgomery.Offset + 31] |= (byte)(edwards.Array[edwards.Offset + 31] & 0x80);// copy sign
}

public static void MontgomeryToEdwards(ArraySegment<byte> edwards, ArraySegment<byte> montgomery)
{
    FieldElement montgomeryX, montgomeryZ, edwardsY;
    FieldOperations.fe_frombytes(out montgomeryX, montgomery.Array, montgomery.Offset);
    FieldOperations.fe_1(out montgomeryZ);
    MontgomeryXToEdwards(out edwardsY, ref montgomeryX, ref montgomeryZ);
    FieldOperations.fe_tobytes(edwards.Array, edwards.Offset, ref edwardsY);
    edwards.Array[edwards.Offset + 31] |= (byte)(montgomery.Array[montgomery.Offset + 31] & 0x80);// copy sign
}

You should be able to use these together with my implementation at github.com/CodesInChaos/Chaos.NaCl. If all you need is crypto_box_beforenm except with a Ed25519 format key, you can simply use the existing Ed25519.KeyExchange method.

A few warnings:

I'm planning some breaking API changes
I'm not happy yet with the test coverage yet, so be careful
The Montogomery form Curve25519 functions don't ignore the last bit of the public key.

This means that you must manually mask out that bit via publicKey[31] &= 0x7F before passing it to MontgomeryCurve25519.KeyExchange. I will change this property with the next update of the library.
The key exchange functions hash their output, matching crypto_box_beforenm.


Public key encryption schemes and security of an uncommon use

Assuming that you're using the same definition of "secure" for both schemes1, then yes, it is indeed trivially true that modifying a public key encryption scheme by restricting the distribution of the public key will yield a scheme that is "at least as secure" as the original.

Specifically, consider an attacker who wants to break the modified scheme.  We don't really care what the attacker wants to do (although, usually, someone attacking an encryption scheme would want to extract some information from an encrypted message), just that it's something that the modified (and the original) scheme is designed to prevent.  There are two possible cases:

Either the attacker knows the public key, or can somehow determine it from other information that they have.  In this case the two schemes are, from the attacker's viewpoint, equivalent, and therefore equally secure.
Alternatively, the attacker may not know the public key.  In this case, if they were given the public key, that would make the two schemes equivalent from their viewpoint.  Since giving the attacker extra information cannot make the scheme harder to break, that means that the modified scheme cannot be easier to break than the original.

Therefore, in neither case can the modified scheme be easier to attack than the original.

It is, however, quite possible for the two schemes to be equally secure.  For many real world public-key encryption schemes that is indeed likely to be the case, if only because such schemes are usually not designed to hide the public key in any way, and thus may allow attackers to easily learn it.

In general, public-key crypto is designed with the assumption that the public key is public, and trying to make it otherwise rarely if ever yields any significant benefit.  While it may be possible to repurpose some crypto algorithms originally intended for public-key encryption for other uses, in some of which the "public key" might in fact need to be kept secret (as e.g. in this question I asked before), that generally invalidates much of their original security proofs and requires reanalyzing the whole algorithm from the ground up with the new assumptions on what's public and what isn't.

1) Specifically, the definition of what would constitute a successful attack should be the same for both schemes, and should not make reference to anything that would differ between the schemes.  In particular, for the purposes of this argument I'm excluding "the attacker learns something that isn't already public" as an admissible definition of a successful attack, since the two schemes differ in what they consider to be public information.


Checking if a sentence is English after decryption

Try tokenizing the plaintext using an English dictionary. Give higher scores to bigger words to prevent your analyzer from favoring a bunch of one to two letter words. Total the score up and take the highest.

I'm not trying to plug, but there's an (badly written) example in this repo:
https://github.com/wildcardcorp/samson

Here's the code for the analyzer itself:
https://github.com/wildcardcorp/samson/blob/master/samson/analyzers/english_analyzer.py

Example of usage:

>>> from samson.analyzers.english_analyzer import EnglishAnalyzer
>>> message = bytearray(b'stopcollaborateandlisten')
>>> analyzer = EnglishAnalyzer()
>>> analyzer.analyze(message)
105605.2045585186
>>> import random
>>> random.shuffle(message)
>>> message
bytearray(b'nisoabtpenaltdlecoslrato')
>>> analyzer.analyze(message)
22361.397837608132


Is it safe to store AES encrypted string and the original string in plaintext next to each other?

What you're talking about is called a known plaintext attack, and any block cipher worth its salt will be resistant to it. So yes, it should be safe.


What is meant by the base256 encoding of an integer?

It splits an integer $x$ into bytes, a byte is 8-bit that can represent 256 numbers. That is why actually $n$ is set as the smallest positive integer satisfying $2^{8n} > x$. The bytes are little-endian encoded.

  Do $x_1,x_2,\ldots, x_n$ all contain the same bytes, or do they contain different bytes split across them?

No, the x is split into bytes.

  Does enc8 effectively mean big-endian?

A byte has no little-endian or big-endian encodings. Here, it is just a byte encoding but in reverse. Second steps do the little-endian. In the end, all bits are reversed. See a bigger example below.

  After the enc8 bytes are concatenated, are they transformed back into a number or binary or...?

It is a byte array and in general in cryptographic implementations, the programming codes are processing with byte arrays. The output of the hash function will be byte to. It is up to you to convert into hex or base64.

A nice example from cryptologie.net

left_encode:

            0001 0000 | 0011 0001 | 0111 1110 input
            0111 1110 | 1000 1100 | 0000 1000 value reversed
1100 0000 | 0111 1110 | 1000 1100 | 0000 1000 length encoded. the size 3 in reverse

right_encode:

0001 0000 | 0011 0001 | 0111 1110               input
0111 1110 | 1000 1100 | 0000 1000               value reversed
0111 1110 | 1000 1100 | 0000 1000 | 1100 0000   length encoded


What is a Non-Interactive Zero Knowledge Proof?

A non-interactive ZK proof is when you play with yourself. Or, more accurately, with an impartial version of yourself.

In a normal ZK proof, the prover first issues a bunch of commitments, then the verifier issues challenges that the prover complies with; this proves anything only as long as the verifier is assumed to issue challenges normally without any prior understanding with the prover.

In a non-interactive ZK proof, the verifier is replaced by a hash function (or something similar) which is computed over the whole set of commitments: the hash function result is the challenge. If the hash function is really a random oracle then the prover cannot guess its output before trying it, i.e. before having produced his commitments, and that's where the security comes from.


Is a hash function used to expand the key after ECC shared secret is complete?

First of all, you would probably want to put the shared secret into a KDF even if you have enough bits to use it in a symmetric encryption algorithm. Check these two related posts: Key Derivation Function (KDF): Can a key derived from KDF be considered as a secure key? and How to derive a symmetric key from ECDH shared secret?

  So, the question: Is there a NIST standard or a paper that
  specifically describes how this situation should be handled?

For a standard way to handle this situation you can check the IEEE Std 1363-2000 document, particularly section 9.2.2 which show the steps of key agreement operation. The algorithm given in that document uses the shared secret as an input to a KDF function which generates the agreed key (could be the symmetric encryption key in your case).


In theory, someone could do this, but in practice nobody really uses random, sketchy third party cryptography software. Most, if not all, of the commonly used cryptography functions are well understood and tested. Most of them also openly reveal precisely how they work so anyone can implement them. This means lots of people can analyse the algorithms for built in weaknesses like the one you described.

The case you described is a good reason to stay away from unknown and untrusted third party cryptography software.


"hash trail", iterative hash function that can be traced back along many steps

SHA-256 or any at least as wide unbroken cryptographic hash will do, if the elements can be that wide (except the first A which is unconstrained). With a $w$-bit ideal hash, probability of entering a cycle in $n\ge1$ steps are $p<n^2/2^{w+1}$, by the Birthday problem. E.g. $w=256$, $n\le2^{100}$ gives residual odds of entering a cycle $p<2^{-57}$, and that's good enough in practice.

Things are not quite as easy when $w$ must be smaller; e.g. for $w=160$. In this case, we want a hash function less likely to iterate than random; that's not a common beast (to be continued after thinking about it).


If you want to do this manually as stated in your question the approach would be similar to this:

choose an input difference $\alpha$ compute the active input sboxes $n_0$ as the number of sboxes that have a non-zero input difference,
when $\alpha$ is the input difference
choose an plaintext $p_0$ and $p_1 = p_0 \oplus \alpha$

compute one round of encryption to get $t^1_0$, and $t^1_1$
compute $\gamma_1 = t^1_0 \oplus t^1_1$, which is the output difference after one encryption round.
compute the active sboxes after one round $n_1$ as the number of sboxes that have a non-zero input difference, regarding $\gamma_1$
repeat for number of rounds $r$ you want to cover

the number of active sboxes for input difference $\alpha$ is $n(\alpha) = \sum_i n_i$
repeat the full procedure for every possible $\alpha$
the minimum number of active sboxes is $\min_\alpha n(\alpha)$.

Of course, there are more sophisticated ways than this, but if you want to do this manually, it might be a good start to understand the concept.


Breaking RSA when some bits of one prime are known

The attack here is a simple factoring of the modulus. If you know the first 80 bits of a prime, you have 20 bits of search space using the most naïve trial division method, and 19 bits by just throwing out even numbers. Now you could use more advanced factoring techniques, but for only 19 bits of search space, you have 524288 candidates to test, which would take most modern processors a couple of seconds at the very most, so unless you have a large number of bad RSA keys to break, not much more effort than that needs be invested.

After factoring the modulus, you can decrypt at will.

The simplest approach is to make a counter, start at 1, and increment by two every iteration. Add the counter to the known starting point, and try to divide the modulus. If there's a remainder, continue the loop.

If the known bits are anything but the large end, its only slightly more complicated, and the search space is larger as we can't automatically throw out even numbers, so you have just over a million candidates to test. Here we use a counter then shift the bits into a mask to add to the known bit vector.


To be honest, I think all of them do NOT make much difference, since Caesar Cipher is a weak cipher. You can see Breaking the cipher on Wikipedia.
It uses a method called frequency analysis, which ignores key strength.

Also, the three methods you mentioned all have their weaknesses. You should use a secure random generator.


Why is AES-128 considered secure while RSA needs a 1024-bit size to be considered secure

It's because with the key to determining the secret private key in RSA is to factor the public modulus into its two prime factors p and q and need a very large number (2^1024, 2^2048) to make this is computationally difficult.


Usually, $^\top$ denotes the transpose of a matrix or vector.
Common variants include $^t$ and $^T$.

Hence $(c_1,c_2)^\top$ is just $\begin{pmatrix}c_1\\c_2\end{pmatrix}$. Such notation is often used to fit column vectors neatly into text.


Why does CTR mode become insecure after $2^{0.5 \times n}$ blocks?

The security proof and bounds, such as those on page 18 of BDJR's 97 paper, can be read to derive some understanding of what going beyond the bound means.

At a high level, the notion is that you model the adversary as querying an oracle who either performs encryption of the provided data with CTR or returns random values.  If the adversary can not distinguish between the two then the scheme is argued to be secure.

Now with respect to the bound you mention, if you give me $2^n$ blocks of zeros to encrypt and I give you back $2^n$ distinct blocks then you should feel confident I used CTR mode. After $2^{n/2}$ blocks of random values you have a good probability of having observed a duplicate if I am giving you random values.


Which one is better using DSA, or MAC and encryption?

Which is better depends on context.

Reasons to choose 1 (MAC with a key that was generated by client and sent encrypted under public key of server)

Shorter messages from server to client (a MAC is at least 4 times shorter than a DSA signature).
Much faster verification of messages by client (DSA signature verification is slow; that can be improved with ECDSA, and much improved with RSA signature instead of DSA; MAC is the speed king).
Much faster preparation of messages on server, after the initial key establishment (DSA signature generation is slow compared to a MAC; that can be improved with ECDSA, RSA tends to make that worse; again, MAC is the speed king).

Reasons to choose 2 (DSA signed messages)

No need for any communication from clients to server.
Conceptual simplicity.
No need for a CSPRNG on clients (these are hard to get secure).
No secret whatsoever in the clients (keeping a secret secret and unaltered is harder than keeping a public information unaltered).
No need for encryption at all (which is harder to get secure than signature verification).
Less secrets on server (option 1 requires the server to keep the client-unique MAC key secret).
The same signed message can be sent to all clients (most useful for multicast, but not much of an argument for unicast).


Why are the constants so simple in Keccak?

As fgrieu pointed out, the constants are defined in terms of a binary Linear Feedback Shift Register. Because LFSRs can be represented very efficiently using standard logic gates they have been used for pseudorandom number generation computers for decades. They have fallen out of favor for use directly as secure stream ciphers due to advances in cryptanalysis. But the round constants for Keccak are not being relied upon to provide all the properties of a cryptographically secure pseudorandom generator.

By defining them in this way, the designers of Keccak achieve a few things:

NIST specifically asked for functions for which the number of rounds could be extended. This definition of round constants provides an unlimited supply should more rounds need to be added later.
The constants are efficient to implement as an LFSR in hardware. You don't have to embed a table in ROM with 2304 bits of square and cube roots like SHA-2.
Because the constants work out to be mostly zeroes, an fully unrolled pipeline implementation could possibly be even a bit more efficient than a LFSR for every stage. Super-linear scaling FTW.
The designers show that they have not hidden any subtle weaknesses into the choice of round constants because there is not enough information content there to conceal one. NIST has had problems with this in the past: http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115
The designers stake out the claim that the security of Keccak is not heavily dependent on having perfectly statistically unbiased round constants. This may sound petty, but saving your peer reviewers from needless unproductive discussions in advance seems to be a direct benefit to public cryptanalysis. It seems to have worked for Keccak anyway.

What's really fascinating is just how closely related all these reasons become under information theory. http://en.wikipedia.org/wiki/Algorithmic_information_theory


Summarize the mathematical problem at the heart of breaking a Curve25519 public key

Six-word summary: the elliptic-curve discrete log problem.

$\newcommand{\F}{\mathbb{F}}\newcommand{\Z}{\mathbb{Z}}$Summary with math: Given $x(A)$ and $x(P)$ for two points $A$ and $P$ on the elliptic curve $y^2 = x^3 + 486662 x^2 + x$ over the field $\Z/(2^{255} - 19)\Z$, find an integer $a$ such that $A = [a]P$, where $[a]P$ is scalar multiplication on the curve.  We pick $a$ (in your notation, $k$) uniformly at random from $2^{251}$ possibilities, so that the best algorithms for computing it from $x([a]P)$ (in your notation, $b^k$) cost about $2^{125}$ arithmetic operations, more than any adversary can ever hope to carry out.

Or, more precisely, we rely on the computational elliptic-curve Diffie–Hellman problem: Given public keys $x(A)$, $x(B)$, and $x(P)$, find $x([ab]P)$ where $A = [a]P$ and $B = [b]P$.  But it seems to be not much easier than the ECDLP.

In a little more detail:

The number $p = 2^{255} - 19$ is a prime, so every integer that is not a multiple of $p$ has an inverse modulo $p$, and thus the integers modulo $p$ form a finite field $\F_p = \operatorname{GF}(p) = \Z/(2^{255} - 19)\Z$.  A field is necessary to define an elliptic curve.  The number $p$ is convenient because it is under $2^{256}$ but not too much under, and very close to a power of two.  Thus:

Every set of integers that are congruent modulo $p$ has a representative that can be written in 256 bits = 32 bytes (= 64 hex digits, as you have noticed).  In fact, it takes only 255 bits, which leaves one extra bit that turns out to be handy for encoding curve points.
To reduce an integer $u \geq p$ to an integer $\overline{u} < p$ congruent to $u$ modulo $p$, you can exploit the fact that $2^{255} \equiv 19 \pmod p$, so if $u = 2^{255} u_\mathrm{hi} + u_\mathrm{lo}$ for $u_\mathrm{lo} < 2^{255}$, then $u \equiv 19 u_\mathrm{hi} + u_\mathrm{lo} \pmod p$.

In other words, you can shift $u$ right by 255 bits, multiply it by 19, and add it to the low 255 bits of $u$; then the result differ will from the input by a multiple of $p$—with no need to compute general integer division, which makes crypto engineers happy because fast integer division that doesn't leak the values of the inputs to an adversary with a stopwatch is hard to do.

There are two main equivalent ways to view Curve25519.

One view of Curve25519 is that it is the set of all roots of the polynomial $$y^2 - x^3 - 486662 x^2 - x$$ over $\F_p$, each point written as affine coordinates $(x, y)$, together with an additional point written $\mathcal{O}$ called the point at infinity that does not have a representation in affine coordinates.

Another view of Curve25519 is that it is the set of all lines of roots of the polynomial $$Y^2 Z - X^3 - 486662 X^2 Z - X Z^2$$ over $\F_p$, each line written as homogeneous coordinates $(X : Y : Z)$ for $X, Y, Z$ not all zero, where $(X : Y : Z)$ represents the same line as $(\lambda X : \lambda Y : \lambda Z)$ for any nonzero $\lambda$.  The point at infinity has homogeneous coordinates $(0 : 1 : 0)$, and thus need not be treated separately as it is in affine coordinates.  Any other point with affine coordinates $(x, y)$ can be written with homogeneous coordinates $(x : y : 1)$, and any line with homogeneous coordinates $(X : Y : Z)$ for nonzero $Z$ can be written with affine coordinates $(X/Z, Y/Z)$.

The elements of Curve25519 form a group under a somewhat elaborate definition of addition (summarized on Wikipedia, and derived from a long rich history of mathematical theory contributing to the proof Fermat's last theorem, to fast algorithms for factoring large integers, and to dreams of a grand unifying theory of mathematics) defining a point $P + Q$ given points $P$ and $Q$ on Curve25519, for which the point at infinity is an identity so that $P + \mathcal{O} = \mathcal{O} + P = P$ for every point $P$, and for which there is an inverse $-P$ with $P + -P = P - P = \mathcal{O}$.

From this, we can define the scalar multiplication $[n]P$ of a point $P$ by an integer $n$ as $[n]P = P + \dots + P$, the $n$-fold addition of $P$ to itself, which has the property that $[n]([m]P) = [nm]P = [mn]P = [m]([n]P)$ for any other integer $m$, where $nm = mn$ is the product of two integers.

For any given $x$ coordinate, there are at most two possible points on Curve25519 with that $x$ coordinate, corresponding the two roots of the quadratic polynomial $y^2 - x^3 - 486662 x^2 - x$ in $y$.  There may not be any such $y \in \F_p$, if $x^3 + 486662 x^2 + x$ is nonsquare, or a quadratic nonresidue, modulo $p$, but we can augment $\F_p$ with a fabricated element $\sqrt{2}$ and all formal terms $a + b\sqrt{2}$ for $a, b \in \F_p$, giving the extension field $\F_{p^2}$ in which every nonzero element of $\F_p$ has exactly two square roots.  (If you augment $\F_p$ with roots for all polynomials, you get $\overline{\F_p}$, the algebraic closure of $\F_p$, and most elliptic curve theory in algebraic geometry is developed over algebraically closed fields such as $\overline{\F_p}$ and $\mathbb{C}$.)  The points on Curve25519 with coordinates in $\F_{p^2}$ are called the $\F_{p^2}$-rational points, and for every $x \in \F_p$ there are exactly two $\F_{p^2}$-rational points with that $x$ coordinate.

It turns out that for any $\F_{p^2}$-rational point $P$, if $x(P) \in \F_p$ then $x([n]P) \in \F_p$ too for all integers $n$, if we prescribe the abuse of notation that $x(\mathcal{O}) = 0$.  (This is Theorem 2.1 of the Curve25519 paper, with some details omitted.)  And this particular form of curve, a Montgomery curve—as opposed to, e.g., a short Weierstrass curve $y^2 = x^3 - a x + b$ for some $a, b \in \F_p$—admits very fast arithmetic to compute $x([n]P)$ given $n$ and $x(P)$ using only $X$ and $Z$ coordinates, in constant time independent of the values of $n$ and $x(P)$ so that someone who can time the computation from start to finish learns nothing about those values.

X25519 is a public-key key agreement scheme made out of elliptic-curve Diffie–Hellman over a group of $\F_p$-rational points of Curve25519.  Alice's private key is a secret integer $a$ chosen uniformly at random from $2^{251}$ possibilities.  Her public key is the $x$ coordinate in $\F_p$ of a point $A = [a]P$, where $P$ is a point with $x(P) = 9$.  If Bob's public key is $x(B)$ for some point $B = [b]P$, their shared secret is $$H(x([a]B)) = H(x([a][b]P)) = H(x([b][a]P)) = H(x([b]A))$$ which as you can see can be computed either by Alice or by Bob from the information known to each of them, where $H$ is some standard hash function mapping $\F_p$ to octet strings.

(For the full details of how to choose $a$ and how to encode secret scalars and public keys as octet strings if you wanted to implement X25519, see the Curve25519 paper or RFC 7748.  Note that when it was introduced, the name ‘Curve25519’ meant just the DH function.  The names have since been changed so that ‘Curve25519’ now means the curve, and ‘X25519’ is the DH function.  A birationally equivalent curve in twisted Edwards form, sometimes called Ed25519 or loosely just Curve25519 in twisted Edwards form, is used for signatures now too.)

The computational elliptic-curve Diffie–Hellman problem is to find $x([ab]P)$ given elements $x([a]P)$, $x([b]P)$, and $x(P)$ of $\F_p$.  The best known ways to do this are all by way of the elliptic-curve discrete log problem, which is to find, given two elements $x(P)$ and $x(A)$ of $\F_p$, an integer $a$ such that $A = [a]P$—that is, to find the secret scalar of a scalar multiplication.

The best generic ways to do this, knowing only how to compute the group operation, are Pollard's rho and kangaroo algorithms, which cost about $2^{125}$ group operations—likely more than anyone will ever compute.  If the base point $P$ had composite order—that is, if the smallest integer $n$ such that $[n]P = \mathcal{O}$ were composite—then the Pohlig–Hellman algorithm could compute $a$ faster by computing it modulo each factor of the order of $P$ independently.  But $P$ has prime order $p_1 = 2^{252} + 2774231777737235353585193779088364849$, so Pohlig–Hellman doesn't help, just like it doesn't help much in finite-field Diffie–Hellman over a safe prime of the form $2q + 1$ for prime $q$ or if the FFDH generator has prime order.

In the Lim–Lee attack (adapted to elliptic curve groups), if the attacker sends Alice the $x$ coordinate of a point $Q$ that is not a scalar multiple of $P$—possibly not even an $\F_p$-rational point but only an $\F_{p^2}$-rational point—and has small order $k$, then since $[a]Q = [a \bmod k]Q$, by checking which of $k$ possible derived shared secrets Alice uses, the attacker learns a little about $a$, namely $a \bmod k$.  But the only possible small orders of elements of points with $x$ coordinates in $\F_p$ divide 8, and Alice always chooses $a$ so that $a \bmod 8 = 0$—that is what (part of) the bit-twiddling at the beginning is about.

The number 8 is the cofactor of Curve25519, because the group of $\F_p$-rational points has order $8p_1$.  The group of $\F_{p^2}$-rational points with $x$ coordinates in $\F_p$ and $y$ coordinates not in $\F_p$ but in $\sqrt{2}\F_p$, called the twist of the curve, has order $4p_2$ for a large prime $p_2 = 2^{253} - 5548463555474470707170387558176729699$.  No legitimate public keys are on the twist, but the attacker can feed in what look like public keys that are.  This is the subject of twist security, and is the reason why $\F_p$ was not the only actor in the story of fields above.

There is more to the elliptic curve security story.  Further reading:

Everything else at SafeCurves.
A gentle introduction to the basics of algebraic geometry and computing with it:
David Cox, John Little, and Donal O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3rd ed., Springer UTM, 2000.  ISBN: 978-0-387-35650-1.
Throw yourself into the deep end of algebraic geometry with:
Robin Hartshorne, Algebraic Geometry, Springer GTM, 1977.  ISBN: 0-387-90244-9.
For the specific topic of computing with elliptic curves:
Joseph H. Silverman, The Arithmetic of Elliptic Curves, 2nd ed., Springer GTM, 2009.  ISBN: 978-0-387-09493-9.
For a comprehensive survey of everything you ever need to know about elliptic curve cryptography up to 2006:
Roberto M. Avanzi, Henri Cohen, Christophe Doche, Gerhard Frey, Tanja Lange, Kim Nguyen, and Frederik Vercauteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall/CRC, 2006.  ISBN: 978-1-58488-518-4.


Public Key Encryption using ECDHE and AES-GCM

I assume the recommended approach is to use a KDF function like HKDF, but what is the security implication of taking an SHA-256 hash and using it directly for AES-256 or truncating it for AES-128 (Alice and Bob are using Java which doesn't have a native implementation of HKDF and I don't think it is a good idea to try and write your own).

HKDF(-Expand) is easy to implement if you have access to HMAC, since for short keys it is just HMAC(s, 0x01) with s the shared secret; an optional context string can be prepended to the 1-byte. However, just a hash is fine as well.

  What advantage does ECDSA provide in this scenario or am I mixing things up?

If you only need to guarantee privacy and authenticity, there is no need for adding ECDSA into the mix. AES-GCM with the shared secret from the ECDH-exchange is sufficient. However, there are two other scenarios that may make ECDSA useful here:

First, ECDSA is one way for Alice and Bob to authenticate the ephemeral keys used in the key exchange, like you suggest in the comment. If they already know each other's ECDSA keys, they can use them to sign and verify the ephemeral keys.
If they require non-repudiation, they can use ECDSA to sign the messages before encryption. With only ECDH and AES-GCM there is no way to prove if Alice or Bob wrote a particular message, since either can encrypt under the same shared key. A signature would allow Alice to prove to others that Bob said something. (Whether you want non-repudiation or want to avoid it depends on the use case.)


Homomorphic encryption allows you to perform operations on the ciphertext that are reflected in the plaintext. These operations are not used to keep the plaintext confidential, that's performed by the homomorphic encryption itself.

Homomorphic encryption usually has little to do with obfuscation techniques, which is probably what you're looking for. "just looking for a light version" as you explain in your comments probably rules out homomorphic encryption techniques to accomplish obfuscation.


No.  As far as I can tell, this does not appear to produce a bent sequence.  (Or, if it does, that fact requires proof/justification.)

According to Wikipedia, a "bent sequence" is a sequence of the form $(-1)^{f(x_0)}, \dots, (-1)^{f(x_{2^n-1})}$ where $x_0,\dots,x_{2^n-1}$ is the sequence of $n$-bit values in lexicographic order and $f$ is some bent function.  That's different from what you are mentioning.  If what you're mentioning happens to fit this definition, that fact is far from obvious.

I don't know if this is the same definition of "bent sequence" you are using.  If it isn't, I suggest editing your question to include the definition you are using.


Are there benefits for using Static Diffie-Hellman over Ephemeral Diffie-Hellman?

The "advantage" of static DH is that the server doesn't need to compute an exponentiation each time. This advantage is, however, not worth it, in the sense that the static DH problem is easier than the DLOG problem (to the best of our knowledge). In the paper The Static Diffie-Hellman Problem (PS) by Brown and Gallant, they show an attack on the static DH problem for Elliptic curves that is significantly faster than the best known for ephemeral DH.

Note: I would not call static DH "standard"; on the contrary, in my mind, ephemeral is the "standard" version.


These are different messages. The first is encrypted, and inside that there might be more information, but

$ gpg -vvv one.asc
gpg: using character set `utf-8'
gpg: armor: BEGIN PGP MESSAGE
Version: GnuPG v2
:pubkey enc packet: version 3, algo 1, keyid 8D136ECEBD8F1671
        data: [2047 bits]
gpg: armor header:
gpg: public key is BD8F1671
:encrypted data packet:
        length: 405
        mdc_method: 2
gpg: encrypted with RSA key, ID BD8F1671
gpg: decryption failed: No secret key

The second is a signed message, not encrypted. The message that is signed is in plain text

ba2c254d75426db8e8ac6cb59020a82633731ad9

and the signature is in the PGP SIGNATURE part


Is the One Time Pad (OTP) considered a cryptographic hash function?

No, OTP would not be considered a cryptographical hash function.

OTP takes a key; cryptographical hash functions don't
It's generally expected that the output of a hash function be of fixed length, independent of input length.  The output of OTP is the same length as the input.
Hash functions are deterministic (that is, if you give the same input twice, you get the same output); if your hash-like OTP function uses a new portion of the keystream for every message, than the exact same input will yield different outputs if you call it repeatedly.


Is there an efficient way to hide the encrypted plaintext length with a block cipher?

Counter mode (CTR mode) seems like it will do what you want.  The length of the output is equal to the length of the input, plus the length of the IV.  If this is not what you want, you'll need to explain your question/requirements more clearly.

In practice, I recommend you use an authenticated-encryption mode, such as EAX or GCM etc.


I think that it's more proper  for your title to be named "Why hashing the shared value to get session key?" Next I'll answer your question in my understanding.

The basic problem is to establish a shared key between Lecturer  and undergraduate office securely. In the original Diffie-Hellman key-exchange protocol, Alice and Bob use the $g^{ab}$ as their session key. This basic DH protocol is based on CDH assumption, but CDH assumption alone can not ensure that we can use all the bits of $g^{ab}$ securely, it can only make sure that we can obtain  a hard core bit which is unpredictable. So the straight idea is to run the protocol $k-times$ to get secure $k$ bits. But it's undesirable and inefficient. So, in order to make the weak bits of $g^{ab}$ as strong as others, usually we hash the shared value to get the final session key.

But another problem you need to consider is the key-exchange protocol's security, so  that you can establish a session key between  lecturer and undergraduate office. I think key-exchange protocol's security is more important. And it's vulnerable to kinds of attacks.As your question is not about it, so I just answer you question in my view.


Yup, should be possible.  Look at multiparty secure computation protocols.

In particular, you might want to look at secure protocols for private set intersection.  $P_1$ and $P_2$ can use such a protocol to find the individuals that are in the intersection of a set known to $P_1$ and a set known to $P_2$.  Then, they can let $S$ know whether there is any intersection and what the correspondence between IDs is

Specifically: $P_1$ has a set of individuals ($f_1^{-1}(a)$), and $P_2$ has another set ($f_2^{-1}(b)$); now a private set intersection protocol lets us check whether these sets have any elements in common, without revealing anything else about the sets.  In such a protocol, the set of individuals never leaves $P_1$ or $P_2$, but we still have a way to learn whether $P_1$'s set $P_1$ has any overlap with $P_2$'s set.  The details are, well, detailed, but if you are interested, look up any reference on private set intersection.

This approach scales beyond pairwise comparison of individual IDs; if the server has a set of IDs on $P_1$ and a set of IDs on $P_2$, you can use this approach to find whether there is any overlap between these sets and if so, what the correspondence is between the IDs.


ElGamal signature - exploiting fallacious implementation

As Wikipedia’s Chinese remainder theorem article states:

  The Chinese remainder theorem is a theorem of number theory, which states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

Using that, you can solve this by finding a $\gamma$ satisfying

$$\gamma \equiv 0 \pmod{p-1}$$

and

$$\gamma \equiv \alpha^x \pmod{p}$$

and you’re done.


Behold! The slides from the presentation, as pulled from the Black Hat 2013 iSEC Partners page. The presenters are not cryptographers — they're security researchers. You can find more information about the presentation at the Black Hat website, including a brief biography of the researchers in question.

It appears that the presentation focused on advancements in the discrete logarithm problem, particularly by Joux, and less on factoring itself; instead, the argument was that since advances in the discrete logarithm problem tend to lead to advances in factoring (and vice versa), and since Joux has been making some particularly good progress in that area, RSA is thus in imminent danger.

I'm ambivalent on the matter.

To answer your question directly, I'm not sure which two "devastating attacks" the article in question is talking about. The slides, as linked above, contain links to many different results (see page 26 and onward). However, if I had to guess, I would suspect they are talking about

Joux's A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic, published on Feb. 20, 2013, and
Barbulescu et al.'s A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, published on Jun. 18, 2013.

These two papers are cited in the slides on pages 26 and 28, respectively.