Disadvantages of one-way accumulators? One-way accumulators are built upon a (quasi)-commutative one-way function. With quasi-commutativity, I refer to the following property:

For $f : X \times Y \to X$, it is true that $f(f(x, y_1), y_2) = f(f(x, y_2), y_1)$.

Although accumulators seem like a very useful cryptographic building block, I don't see them often in practical applications (in fact I can only think of Zerocoin). I suspect that this is because the scheme has certain disadvantages.

I wonder what these disadvantages are (if this is indeed the reason): is the function $f$ weak in terms of eg. collision-resistance, is it not efficient enough...?

The accumulators that I know of (note: I don't really know a lot about them, so this doesn't say much), seem to be based on number-theory (unlike conventional hash functions). This makes them a lot slower.

For example, Wikipedia describes the following function:

  One trivial example is how large composite numbers accumulate their
  prime factors, as it's currently impractical to factor the composite
  number, but relatively easy to find a product and therefore check if a
  specific prime is one of the factors. New members may be added or
  subtracted to the set of factors simply by multiplying or factoring
  out the number respectively. More practical accumulators use a quasi-commutative hash function where the size (number of bits) of the accumulator does not grow with the number of members.

As they mention, this is clearly not practical because of the size of the output values.

Another example I have seen is $f(x, y) = x^y \pmod n$ where $n = pq$ (with $p$ and $q$ both safe primes). Even though this doesn't have the problem of the Wikipedia example, it is still not very efficient (even though you can do the exponentiations using the square-and-multiply method).

An advantage of a cryptographic accumulator and actually the reason to use them is that due to the quasi commutativity you can compute witnesses for
membership of values in the accumulator where the accumulator and the witnesses are of constant size.

Say you
have a set $Y=\{y_1,y_2,y_3\}$ and compute the accumulator as $acc=f(f(f(x,y_1),y_2),y_3)$ you want to compute a witness for a value say $y_2$, then by quasi commutativity, the value for your witness is $wit_{y_2} = f(f(x,y_1),y_3)$ and you can check given $y_2$ and $wit_{y_2}$ whether $y_2$ is in the accumulator $acc$, you can check whether $acc=f(wit_{y_2},y_3)$ holds.

Furthermore, existing accumulator schemes (CL02, C+09, N05) come with zero-knowledge proofs of accumulator membership (you do not have to reveal the value $y_2$ and the witness $wit_{y_2}$ directly, but you provide a zero-knowledge proof of knowledge of such a pair - which makes them attractive for privacy-preserving applications). Such accumulators are typically also dynamic, i.e., allow update of witnesses in the public if the accumulator is updated. Furthermore, there are also so called universal accumulators, which also allow to produce witnesses for non-membership of a value in the accumulated set (see A+09 or L+07).

All known efficient accumulators are based on number theoretic assumption, but I would not say that they are
inefficient. Note that in your last RSA example, the membership check requires one exponentiation, which is not really very expensive.

  is the function f weak in terms of eg. collision-resistance, is it not efficient enough...?

For a secure accumulator one requires collssion-freeness, i.e., it is computationally infeasible to find a witness for some value that is not accumulated in the accumulator. For RSA accumulators that requires that you only accumulate primes (so you have to map your values to accumulate to primes with some deterministic algorithm). Otherwise, you could factor your value into two factors and exponentiate one onto your witness and provide the second as value to be checked and the check would work. This is ruled out if you take primes. There are however, other secure pairing based accumulators that do not suffer from this problem.

Accumulators are used for various purposes, such as timestamping (the original application), membership testing, distributed signatures, redactable and sanitizable signatures as well as for revocation in group signatures and anonymous credential systems.

There are constructions for accumulators based on bloom filters (see Nyberg, Fast accumulated hasing, FSE 1996), but
they are rather impractical (but do not rely on number theoretic assumptions).


Order of target group in pairing Let $N=pq$, where $p$ and $q$ are prime numbers, and order of $G_1$ and $G_2$ is equal to $p$. Suppose that $e(G_1, G_2)=G_t$ is a pairing of composite order. I know that, usually the order of target group $G_t$ is $p$.

Is it possible to set the order of target group to $pq$? In other words, is it possible to set order of target group be bigger that the order domain groups?

(I write $G_n$ for an abelian group of order $n$.)

Well, you can always embed $G_p$ into a group of order $pq$ as a subgroup, but that is probably not what you want.

Besides such trivial cases, this is impossible: The universal property of tensor products uniquely factors any bilinear map
$e\colon\ G_p\times G_p\to G_{pq}$
as
$$e\colon\;G_p\times G_p\twoheadrightarrow G_p\otimes_{\mathbb Z}G_p\xrightarrow{\bar e}G_{pq} \text;$$
note in particular that $\bar e$ has the same image as $e$.
However, since $p$ is prime, $G_p$ is cyclic and $G_p\otimes_{\mathbb Z}G_p\cong G_p$ via the map $a\otimes b\mapsto ab$; thus $\operatorname{im}e=\operatorname{im}\bar e$ has order dividing $p$.

This essentially shows that any such pairing $e$ is either degenerate or given by a pairing $G_p\times G_p\to G_p$ followed by an embedding.

Here is a more elementary proof, using only basic group theory and bilinearity:
Let $e\colon\ G_p\times G_p\to G_{pq}$ be a bilinear pairing and $g$ a generator of $G_p$. Since $e(g^n,g^m)=e(g,g)^{nm}$ for any $n,m\in\mathbb Z$, the element $e(g,g)$ is a generator of the image of $e$. But
$$e(g,g)^p=e(g,g)^p=e(g^p,g)=e(1,g)=e(g^0,g)=e(g,g)^0=1\text,$$ thus the order of $e(g,g)$ divides $p$. This implies (as $p$ is prime) that the image of $e$ is either trivial or isomorphic to $G_p$; in particular $e$ is never surjective.


Clarification on Size of an Encryption Key Given a key with a certain key size (e.g., 64bits). Would I be correct to interpret this as 8 characters (since each character would be 8 bits under ASCII encoding)?

Because the ASCII scheme is limited to just 127 characters, this would mean that characters not included in the English language are not considered. Could it be instead that 64 bits has to be interpreted based on an encoding scheme such as unicode that includes many more characters? -- This would mean that 64 bits contains a much smaller number of characters since a unicode character takes more bits.

Yes, 64 bits is equivalent to 8 bytes, because there are 8 bits per byte.

"Could it be instead that 64 bits has to be interpreted based on an encoding scheme such as unicode that includes many more characters? "

No - the key does not need to be encoded as either ascii or UTF. Typically crypto algorithms operate either on an array of unsigned characters, or larger words when required (i.e. unsigned long long for 64 bit words).


Not-So-Simple Substitution Cipher? The first go-to weakness when talking about substitution ciphers is frequency analysis. It assumes that there's a simple 1 to 1 character mapping between the plain text and the cipher text.

Could a frequency analysis be thwarted if this were a 1 to Many mapping?

For example, what if the input text contained say 30 characters: 26 letters, space, period, question mark, and exclamation mark. Enough for most communication needs between two people. The output could be quite a bit larger, like the 95 printable characters. E could be mapped to multiple output characters that appear at unusual frequencies in the cipher text that don't look like E on a frequency analysis. This mapping could also map space to 1 or more characters so you can't analyze word length or word frequency.

Every character could map to at least 3 output characters and knowing that some characters are already pretty rare they may not even need to be mapped to that many. Perhaps just 2 or even 1 that way other more frequently used characters could map to 5 or 6 cipher text characters.

Is there a different kind of analysis that could target a cipher like this?

This is called homophonic encryption, and has been around for a long time.

In terms of cryptanalysis of such ciphers, there is a nice thesis from SJSU on this topic which is available here. The attacks tested in that cipher were based on hill climbing and local optimization techniques. The conclusion states:

  We designed and implemented an efficient attack on the homophonic substitution ciphers.
  The attack is based on the hill-climbing heuristic technique. The proposed algorithm has
  a multi-layered architecture with three nested loops to solve the challenges imposed by
  the homophonic substitution ciphers and the hill-climbing technique. The algorithm was
  successfully tested on simple substitution ciphers and many instances of homophonic
  substitution ciphers with variable ciphertext sizes and cipher symbol sizes. [..] For the ciphertexts having minimum 3000 characters and
  maximum 75 cipher symbols, the algorithm was able to break at least 85% of cipher
  symbols.

So, homophonic substitution increases the required ciphertext length, as expected, for a high rate of success of correctly decrypting plaintext characters. If 55 ciphertext symbols are used (to flatten the frequency distribution) the success rate increases from about 10% for a ciphertext length of 300 characters to about 80% for a ciphertext length of 4000 characters.

If 95 ciphertext characters are used, at 4000 character ciphertext length, the success rate is around 50%.


Is Discrete Logarithmic assumption enough to design a secure searchable encryption scheme? I have a basic question in my mind which is "Can we develop a scheme based on Discrete Logarithmic (DL) assumption only? "

Most of the "Searchable Encryption" schemes use assumptions like Decisional Bilinear Diffie–Hellman (DBDH) in their formal security proofs, (e.g. "Protecting Your Right: Verifiable Attribute-Based Keyword Search with Fine-Grained Owner-Enforced Search Authorization in the Cloud" by  Sun et al. SE). Can the formal security proof of my designed scheme be based on DL assumption only?

If you only use the group in a black-box way (meaning, if you wish to rely on the discrete logarithm problem on an arbitrary group), we do not know of any encryption scheme (searchable or not) whose IND-CPA security reduces to the discrete logarithm problem. What we can do from the discrete logarithm problem directly is quite limited. In particular:

you can design a commitment scheme whose binding property reduces to the discrete log problem, this is the famous Pedersen commitment scheme.
The key-recovery security of the ElGamal encryption scheme (i.e. the hardness of computing its secret key given only its public key) reduces to the discrete logarithm assumption.

However, in some specific groups, it is known that the computational Diffie-Hellman assumption is equivalent to the discrete logarithm assumption - this was shown by den Boer in this paper.

Furthermore, we know how to construct advanced types of encryption schemes from the computational Diffie-Hellman assumption. For example, using the Goldreich-Levin harcore predicate and the ElGamal encryption scheme, one can construct an encryption scheme whose IND-CPA security reduces to CDH. IND-CCA secure cryptosystems from CDH where given in this paper.

Very recently, in a breakthrough result, Garg and Döttling have shown that identity-based encryption can be obtained assuming CDH only.

In a follow up to the previous paper, this result was extended to anonymous IBE. Furthermore, it is known that encryption with keyword search can be constructed from anonymous IBE - see this paper. Combining all of the above, this gives you a CDH-based searchable encryption scheme.

All these schemes are secure under the discrete logarithm assumption when instantiated in the groups identified by den Boer. However, it should be noted that the dlog-based keyword-search scheme obtained this way is extremely inefficient and only of theoretical interest.


Deriving a Set of Seeds from a Seed I need a set of seeds $S=\{s_1,..., s_n\}$, for pseudo-random function where seed $s_i$ is used to generate a set of pseudo-random values. Obviously I need to be able to regenerate the sets of pseudo-random values, but I do not want to keep the seeds. Thus, I'd like to use a master seed to generate the other seeds.

Question: Would it be secure if I generate a seed for pseudo-random function and then use it to generate a set of seeds?

If not what a solution would be?

By secure I mean the pseudo-random values should not be distinguished from random values.

I believe it seems similar to random and urandom function in unix/Linux system. Once the physical entropy/seed is not enough, one would block and the other would generate the seed based on current ones. From security point of view, pure random entropy should be better choice, but in practical, I don't see the problem with seed generation. It should be indistinguishable to some extent if your initial seeds are pure random.. like from physical entropy.


How to salt PBKDF2, when generating both an AES key and a HMAC key for Encrypt then MAC? When using Encrypt-then-MAC with AES and HMAC by password, and given 128 bits of payload with the ciphertext to store a random salt, which would be more secure:

Using PBKDF2 with then entire 128 bit random salt and generating 512 bits of derived data to split into a 256 bit AES Key and a 256 bit HMAC key.

or

Using PBKDF2 separately for each key using two 64 bits salts to generate a 256 bit AES Key and a 256 bit HMAC key.

or

Better option?

I'd use HKDF's "expand" step to generate multiple keys from one masterkey.

Use PBKDF2 to derive that masterkey from the password and salt. i.e. replace the "extract" step of HKDF with PBKDF2.

//Extract
MasterKey = PBKDF2(salt, password, iterations)

//Expand
AES-Key = HMAC(MasterKey, "AES-Key" | 0x01)
MAC-Key = HMAC(MasterKey, "MAC-Key" | 0x01)

(where | denotes concatenation)

Having PBKDF2 output more than its native size is a bad idea IMO. It increases the cost for the defender considerably (multiple key derivations with thousands of iterations) but doesn't increase the cost for the attacker(he can verify correctness of his password guess after one key was derived, he doesn't need both).

If you use a 512 bit hash, such as SHA-512 in PBKDF2 (PBKDF2-HMAC-SHA-512) you can also get away with simply splitting those 512 bits into two parts, using one for encryption and the other for MAC. But IMO the HKDF approach is cleaner.


Security difference between $\mathrm{Keccak}(k\mathbin\|x)$ and $\mathrm{Keccak}(x\mathbin\|k)$ $\require{begingroup}\begingroup
\DeclareMathOperator{\keccak}{\mathrm{Keccak}}
\DeclareMathOperator{\concat}{\|}
$According to Keccak's website, $\keccak(k \concat x)$ is safe:

  Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.

My question is, is $\keccak(x \concat k)$ safe?

I read Why is $H(k\mathbin\Vert x)$ not a secure MAC construction? but I guess it doesn't apply to Keccak.
$\endgroup$

See chapter 5.11.2 of the paper “Cryptographic sponge functions” (the link can be found here):

  Note that one can also define a MAC function by taking as input the message followed
  by the key: $t = \left\lfloor {F(M \mathbin\Vert K)} \right\rfloor _n$.  In this case, an adversary has the advantage that she can try
  to generate inner collisions offline, i.e., without having to query the keyed sponge function. Additionally, she can try to construct a path to a state that occurs in the absorbing of a target
  message, leading to a second message with the same MAC.


Found a mistake in a proof about when GGH will decrypt incorrectly The proof is here on page 66, lemma 20. I found the same mistake in other sources also.

It claims that GGH decryption will fail only if $\lceil R^{-1}e\rfloor \not =0$. Here $R$ is the "good" private basis for the lattice and $e$ is the small random vector. Rounding symbol means just that every coordinate of the vector will be rounded to the nearest integer.

In the proof they use the "fact" that $B^{-1}R$ is an unimodular matrix. They come to this conclusion from the fact that the two bases are connected by a unimodular matrix $U$ like this

$$B=UR.$$

This is correct. However from this they deduce that $$U^{-1}=B^{-1}R.$$ This is clearly false. Actually $$U^{-1}=RB^{-1}.$$ There is no guarantee that $B^{-1}R$ is unimodular.

Have any of you come across another way to prove this result?

Okay, this was a really stupid mistake by me. I got confused because some sources use notation where $R$ and $B$ have the basis vectors as rows. However Goldreich, Goldwasser and Halevi have the basis vectors as columns so
$$B=RU\implies U=R^{-1}B.$$ Hence the matrix is unimodular and the proof works. Sorry about the inconvience.


Should we use exponent 3 in RSA-OAEP? As I understand it the proof that RSA-OAEP is secure in the random oracle model is much tighter for exponent 3.  Does that mean that exponent 3 should be chosen?

For any reasonable RSA-based encryption (or signature) scheme, exponent $e = 3$ is a perfectly good choice and provides the best performance for the public-key operation short of qualitatively different Rabin-type schemes.

Don't use RSAES-PKCS1-v1_5.
RSAES-OAEP of PKCS#1 v2 is reasonable in this sense, though it is unnecessarily complicated.
RSA-KEM is even more reasonable and much simpler.

But there are people out there who have PTSD from decades of bad crypto engineering with horrible flaws that are sort of halfway patched over by using larger exponents like $e = 65537$.  So some auditors might summarily reject $e = 3$ when they see the letters R, S, and A, without looking at the elephant in the room of what specific encryption or signature scheme you're using that involves RSA.


complexity of iterative squaring in relation to factorization I've run into a question dealing with the number of

modular multiplications of O(n) bit numbers in the following situation:

Given two n bit primes p,q define m=pq.    Choose some 'a' so that  $2<a<m\hspace{-0.04 in}-\hspace{-0.04 in}2$

and look at a^(2^t) for some integer t.    This is done using iterated squaring.

The question asks about the number of modular multiplications needed for the

case of not knowing the factorization of m and the case of knowing the factorization.

The question hints at using t and n to quantify things.

Me question is, what does the factorization of m have to do with this?

The trick in integrated squaring is using the 'on bits' of a b (call them bi for i: 0 -> n) to calculate a^b by multiplying all (a^(2^i))^bi. I don't quite understand where this question is headed.

Could anyone shed a little light on things?

Let $m = pq$.  Computing $A := a^{2^t} \pmod m$ requires $t$ $2n$-bit modular multiplications.

Now if you know the factorization of $m$ (i.e., $p$ and $q$) then you can evaluate $A = a^{2^t} \pmod m$ from  $A_p := a^{2^t} \pmod p$ and $A_q := a^{2^t} \pmod q$ using Chinese remaindering:
$$
A = A_p + p\bigl[i_p (A_q-A_p) \bmod q\bigr]\quad\text{where $i_p = p^{-1} \bmod q$}
$$

The computation of $A_p$ (resp. of $A_q$) requires $t$ $n$-bit modular multiplications.  Assuming that $i_p$ is pre-computed, the computation of $A$ thus requires $(2t+1)$ $n$-bit modular multiplications.


How to get the datapacket from wireshark? I have a pcap of my twitter traffic using wireshark. The cipher suite TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 method is used for for encryption data.. I have a tweet of 42 characters are traced in the pcap. How can i get the application data packet with the length of my tweet data.

It is expected that is not possible to

  get the application data packet with the length of my tweet data

in clear even if it was additionally obtained all long-term secrets involved. Exceptions involve exploiting deficiencies (e.g. a poor Random Number Generator, some side channel..), or going from passive eavesdropping to performing an active attack (this requires obtaining a rogue certificate, which at least is difficult for most except state actors).

That's because TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 specifies negotiation of an ephemeral session key using Elliptic Curve Diffie–Hellman key Exchange (ECDHE). That session key is used for AES encryption of the session (including the tweet), then forgotten. This prevents deciphering the application data packet.

But is possible to get at the length of the data packet containing the tweet (wireshark displays packet length), and from that to estimate the tweet length.  Per Dave Thompson's analysys, the packet size minus 24 bytes gives the tweet size (assuming no compression or fragmentation).

In captures of two experiments made with a short then with a long tweet, the packet with the tweet can be identified as the one which size grew by the difference in tweet size.


AES Message Authentication Vulnerability My securities instructor recently posed this question to the class and I am bending my brain in half trying to figure it out.

  Suppose $y_1 = AES(K, x_1)$ and $y_2 = AES(K,x_2)$, and suppose you know the pairs $(x_1,y_1)$ and $(x_2,y_2)$.  Without knowing $K$, how can you construct a new pair $(x_3,y_3)$ such that $y_3 = AES(K,x_3)$?

It seems like that shouldn't be possible.... right?

If this is simply the AES permutation on a single block, it's hard to find such a pair.

If it's AES-ECB with multiple blocks, you can pick each block from either (x1,y1) or (x2,y2), producing a new message that contains parts from each of them.

With other modes it depends on that mode, but with many modes there will be a similar mixing attack as for ECB.


How do they implement MAC in TLS? I recently read questions about "MAC then Encrypt/Encrypt then MAC" which made me curious about how they actually use the algorithm.

MAC only calculated once either case (according to what I read). However, in my experience surfing website via HTTPS, I think we should check the authenticity in every chunk of data received.

For example if I assume the MAC was appended at the end of encrypted data, how a browser is so confident so they execute Javascript before the HTML complete downloading.

Further more when downloading large file via HTTPS the browser seem to write the decrypted data to the harddisk before receive all portions of the file.

I think we should use updatable MAC in this case and verify each chunk of data received. However, with this approach it still vulnerable if the objective of an attacker is to discard some portion of data for example "the attacker want the first Javascript to be executed but the second one".

So, I want to ask what scheme browser used to make it sure enough to perform some operation without receive all portions of the file? Or is my info wrong at some point?

($\hspace{.02 in}$packet $\approx$ chunk)

They put a packet number into the plaintexts, and mac-then-encrypt the packets separately.


Trying to understand MixColumns with Hexadecimal matrix I am trying to read and understand the textbook's exercise questions. The sample solution at the end the textbook has a final answer and it does not clarify how it got the result. I am trying to workout the question but I am not successful. Any help would be appreciated.

Questions: Show the value of State after MixColumns:

$\begin{bmatrix}7C & 6B & 01 & D7\\F2 & 30 & FE & 63\\2B & 76 & 7B & C5\\AB & 77 & 6F &67\end{bmatrix}$

Answer: Final answer of textbook:

$\begin{bmatrix}75 & 87 & 0F & B2\\55 & E6 & 04 & 22\\3E & 2E & B8 & 8C\\10 & 15 & 58 & 0A\end{bmatrix}$

My answer:

I used the path that has been mentioned here to find $2\times 0x7C$ and $3\times 0xF2$.

$\begin{bmatrix} 2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{bmatrix} \times  \begin{bmatrix}7C \\ F2 \\ 2B \\ AB\end{bmatrix} = \begin{bmatrix} ?\\?\\?\\?\end{bmatrix}$

    7C = 0111 1100
2 * 7C = 1111 1000

    F2 = 1111 0010
2 * F2 = 1110 0100
3 * F2 = 0001 0110

    2B = 0010 1011
    AB = 1010 1011
-----------------------

Now find value for Cell (1,1)

    2 * 7C = 1111 1000
    3 * F2 = 0001 0110
        2B = 0010 1011
XOR     AB = 1010 1011
        --------------
             0110 1110 = 0x6E <-- is not equal to 0x75

you can done the multiplication operations for the mixcolumn matrices by two methods: either by using the x-time of shifting steps as it you mentioned in your questions or by straightforward multiplication module the (11b) that represent the first irreducible polynomial in the list of polynomial with degree eight for more details see these two manuscripts may be find what you need: (The Euphrates Cipher) and (The New Block cipher Design (Tigris Cipher))

Best regards


Ephemeral Diffie-Hellman in a symmetric crypto context I'd like forward secrecy in a case where the two sides have a shared long-term symmetric key. I intend to use AES in GCM. It looks like ephemeral Diffie-Hellman is the best way to generate the session keys. My question is, is it sufficient to just encrypt the key exchange using the long-term key, or should that be also authenticated?

The key exchange should also be authenticated. $\:$ GCM mode would mostly do that;

however, you should authenticate an indication of which message is for Diffie-Hellman.

(For example, you could use associated_data = 1 for the Diffie-Hellman messages and associated_data  =  0 || application's_associated_data for application-level messages.)


What role does Representation Theory play in Cryptography? Shannon said that every cryptosystem can be expressed as a system of linear equations with a large number of unknowns of complex type. In cryptography groups are used since they are a natural representation of objects that satisfy known relations, this let us to build cryptosystem based on these relations that maintain the scalability when using a decent amount of resources.

Since representation theory is used to represent groups in linear algebra, the aforementioned relations can be also expressed in terms of linear algebra. This theory can lead to representation of cryptosystems as a matrix algebra, thus a system of linear equations can be build to express the cryptosystem's operations.

Q: Is it necessary to study representation theory to analyze cryptosystems based on group theory?

Q: If representation theory is not the point behind group-based cryptanalysis, then what techniques are used here?

Let me answer this question in the context of braid group cryptography since braid groups form the group based cryptosystems which I am most familiar with. Keep in mind that today, most if not all braid based cryptosystems have been successfully attacked. On the other hand, braid group cryptography has not been thoroughly explored and mathematicians still need to investigate braid group cryptography some more. Braid groups are very deep and interesting structures connecting diverse areas such as algebraic topology, quantum computation, and even very large cardinals, so even non-applied mathematicians should appreciate braid group cryptography enough to investigate it further.

There are several well-known representations of the braid groups including the Burau representation (which is not faithful but has a small kernel), the Lawrence-Krammer representation, and several unitary representations used in topological quantum computation. Furthermore, there are several important actions of the braid groups such as the Hurwitz action or the Dynnikov action (these actions are non-linear though). The Hurwitz action generalizes to an action of positive braids on self-distributive algebras and the Burau representation is a special case of the Hurwitz action. The Burau and Lawrence-Krammer representations can be used to attack braid based cryptosystems by first solving the problem (the problem, for example could be the conjugacy search problem) in the matrix group and then lifting the solution back to the braid groups.

The Hurwitz action on braid groups gives very easily computable strong invariants of braids which can in almost all cases distinguish braids in nearly linear time (in a sense, the Hurwitz action gives a 'hash' of a braid). The Dynnikov action can be used to solve the word problem in braid groups using only linearly many integer addition and comparison operations.

There are several ways to analyze braid based cryptosystems which have little or nothing to do with the representations of braid groups. These attacks include length-based attacks, attacks against the conjugacy search problem based on summit sets, and other attacks. Summit sets arise from the Garside normal form and Birman-Ko-Lee normal form of braids which have little to do with their linear representations. Length based attacks are based on length functions which could arise from one of the normal forms of braids. Dehornoy's handle reduction technique and its generalizations are used to minimize the length of a braid and reveal the data that braid based cryptosystems attempt to hide.

I must mention that the attacks against braid based cryptosystems are generally heuristic algorithms, so one will need to program quite a bit in order to properly evaluate these cryptosystems and to evaluate whether an attack against braid based cryptosystems is successful or not.

Since braids are related to a wide array of mathematical structures, it is easier and more direct to understand just braid groups, braid group cryptography, and how braid groups relate to certain areas of mathematics than to be an expert in all of these mathematical disciplines related to braids.

All of these representations and results about braids could be found in the standard references of braids including the survey Braid Group Cryptography by David Garber, the book Braids and Self-Distributivity by Patrick Dehornoy, the book on braid groups by Kassel and Turaev, and the book Ordering Braids by Patrick Dehornoy.


Correctness of RSA variation using CRT to decrypt? Consider RSA variation with public key $(e,N)$ where we take $e=3$ and $N=pq$ where:

$p \equiv 1 \text{(mod 3)}$ so that we don't have $\text{gcd}(e,(p-1)(q-1)) \neq 1$

$p \equiv 7 \text{(mod 9)}$  so that we can compute a cubic root of x by doing $x^{\frac{p+2}{9}} \equiv 1 \text{(mod p)}$

For decryption take $d_p = \frac{p+2}{9}$ and $d_q = \frac{q+2}{9}$. Compute $x_p = y^{d_p} \text{(mod p)}$ and $x_q = y^{d_q} \text{(mod q)}$. Finally recover $x = CRT(x_p,x_q)$ where $CRT$ is the function that computes the isomorphism given by the Chinese Remainder theorem.

We know that we can have three different cubic roots for each number in a field. So how is it that given $x_p$ and $x_q$ I can compute $x$ with Chinese Remainder Theorem?

What you have won't necessarily give you the original value of $x$; it'll give you an $x$ where $x^3 \equiv x_{orig}^3$, however, it isn't necessarily the original value.

To demonstrate this, let us take as an example $p=43$ and $q=61$.

Consider $x_{orig}=5$.  Then, $y=125$, and $x_p = y^5 \bmod 43 = 8$ and $x_q = y^7 \bmod 61 = 52$; this gives us a $CRT(8, 52) = 1943$, which is not the original $x$.  Now, $1943^3 \bmod (43*61) = 125$, and so it also does give the ciphertext, it's just not the same plaintext that you started out with.


Can a Deterministic Signature Algorithm be paired with a Probabilistic Encoding Method? I'm working with a C++ library and I’m currently investigating the changes needed to accommodate Deterministic DSA and ECDSA Signatures (RFC 6979). While the RFC 6979 changes are specific, I'm trying to understand more about the breadth of the potential changes to some of C++ classes involved in the implementation.

Is it possible to pair a “Discrete Log/ElGamal”-alike signature scheme (like – for example – DSA/ECDSA), adorn it with determinism (the deterministic $k$), and then pair it with an encoding method which uses randomness (maybe like something found in a PSS, perhaps with a salt)?

I realize RSA-PSS is a different class of signature schemes. I'm less clear or some of the unique or unusual pairings that may be experienced in the field with lesser known schemes.

This question on pairing primitives is about extensibility planning in software. It leaves open the mathematical questions of correctness and proofs. We often have to ask a theoretical crypto question here to ensure the cryptography is well represented, even though it could be off-topic.

Here's a question that touches on similar: Why use randomness in digital signature algorithms?

  De-randomization can be used to turn a randomized signature scheme
  (such as RSASSA-PSS of PKCS#1v2 parameterized with significant random
  salt) into a deterministic one ...

First, some clarifications.

A randomised signature scheme is a signature scheme that produces randomised signatures, that is, if you sign the same message twice, you are not likely to get the same signature twice.

We can "derandomise" a signature scheme by replacing the randomness with pseudo-randomness generated as a function of the messaget to be signed and a secret key. The result is a deterministic signature scheme, where if you sign the same message twice, you will get the same pseudo-randomness and therefore the same signature. If the randomised scheme was secure and the derandomising was done correctly, the deterministic scheme will also be secure.

A padding scheme is a way to encode messages in one "format" as messages of a different "format", typically arbitrary bit strings as bit strings of length divisible by some number, or short bit strings as long numbers, or ... Usually, these schemes are in some sense injective, in that if you encode two distinct messages, you never get the same padded message.

A randomised padding scheme is a padding scheme that if you encode the same message twice, you are not likely to get the same padded message twice. Such schemes can sometimes be used to turn certain somewhat insecure signature schemes into secure signature schemes, typically by turning the message to be signed into a random-looking message that can be safely signed by the insecure scheme.

Now, the answer: Given the way we define "secure signature scheme", composing a secure signature scheme with any padding scheme cannot result in an insecure scheme (just a pointless scheme). So:

Derandomising DSA results in a deterministic signature scheme.
Since we believe DSA is secure, derandomised DSA should also be secure.
Since we believe derandomised DSA is secure, derandomised DSA composed with a padding scheme like PSS should also be secure (but pointless).

So the answer to your question appears to be yes.

However, one caveat. DSA involves a hash function: you hash the message and then the hash is included in some number-theoretic computations that results in a signature. The hash is an integral part of DSA. If you replace the hash with (say) PSS, you have not composed a secure signature scheme with a padding scheme, but modified a secure scheme. And when you modify schemes, the composition result I mentioned does not apply, and you may end up with something insecure.


Which is the irreducible polynomial in GF(2^256) used in AES256-GCM? I was able to find the irreducible polynomial used in AES128-GCM: $x^8+x^4+x^3+x+1$.

But I cant' find the one for AES256, I'm searching in OpenSSL implementation of AES256 but with no luck so far.

The AES block cipher supports various key sizes of 128, 192, and 256 bits, and a single block size of 128 bits. The degree-8 polynomial $x^8+x^4+x^3+x+1$ is the one used in AES-{128,192,256} for MixColumn and SubBytes.

There is no $\operatorname{GF}(2^{256})$ in GCM because GCM only supports block size of 128 bits. The degree-128 polynomial $x^{128}+x^7+x^2+x+1$ is the one used in GCM.


Can "collisions" occur with encryption algorithms? For a given Key $K$ and two messages $m_1, m_2$ is it possible for an encryption algorithm (say AES-256) to produce this: $AES(K, m_1)$ = $AES(K, m_2)$?

I understand that the output has to be unique (aka every input has to be mapped to a different output) so that it can be decrypted, but it just seems so bizarre to me that it is possible for an algorithm to consistently map every single bit of input to a different output such that $AES(K, m_i) \ne AES(K, m_j)$ where $m_i$ and $m_j$ are numbers  $<2^{256}$.

Do I just have to dive deep into the maths?

For a given Key K and two messages $m_1$, $m_2$ is it possible for an encryption algorithm (say AES256) to produce this: $AES(K, m_1) = AES(K, m_2)$.

Not if $m_1$ is different than $m_2$. Assuming you are talking about AES as a block cipher, and $m_1$ and $m_2$ as input blocks, this is not possible. Every different input block will have a unique output block. Take this cropped image as an example of a 4-bit block cipher with a fixed key, with 16 plaintexts and 16 ciphertexts:

As you can see, 11 encrypts into 12, and thus 12 decrypts to 11. If, as per your example, 13 also encrypted to 12, how would you correctly decrypt 12? Also, how would you decrypt 9?

Well, you couldn't, because a block cipher is a bijection, that is the amount of plaintexts and ciphertexts are composed of sets of equal size, and there is a one-to-one mapping between them, with all of them being paired.

The following behaviors of a block cipher are possible:

$AES(K_1, m_1) = AES(K_2, m_1)$
$AES(K_1, m_1) = AES(K_2, m_2)$
$AES(K_1, m_1) = m_1$

As fgrieu pointed out, a mode of operation with a third input (such as an IV or a prior block) may cause this to happen within a group of blocks, but since the decryption process depends on that third input as well, it will decrypt properly.


Concept of "guessed ID" in Authenticated Identity-Based Encryption In Authenticated Identity-Based Encryption by Ben Lynn, in Proof of Integrity (section 4.3) and Proof of Security (section 4.4), I cannot grab the concept of "guessed ID" . Because encryption differs according to "guessed ID", I am unable to know how it works.

Is there anyone who can help explain this term and how it affects the proof?

"Guessed ID" means ID that the oracle guesses the attacker algorithm $A$ will attack.


Is the only use for the private key of a root certificate signing certificates issued by it? A root certificate can be used to issue intermediate certificates.

The private key of the root certificate is needed in order to sign any intermediate certificates.

However, after that, we only need the public key of the root certificate to verify the signature of intermediate certificates.

Similarly, the private key of an intermediate certificate is needed to sign the public keys of SSL certificates issued by it but after that we no longer seem to need the private key of the intermediate certificate for anything other than issuing and signing more SSL certificates.

Does the private key of a CA certificate have any uses other than signing the certificates issued by it?

It could be used to sign a Certificate Revocation List, for instance. Generally it is not used for anything other than certificate related actions, and some private keys belonging to root and intermediate certificates are therefore stored off-line to enhance security of the private key.


Is what i'm trying to do safe? What both parties have:

Server
Master Secret (MS)
Server supported versions (Svers)
Agreed upon version (ver)

Client
Master Secret (MS)
Client supported versions (Cvers)
Agreed upon version (Ver)

What I am planning on doing:

Client sends Cvers to Server.
Server checks what version to use (the highest version the 2 share will be selected)

then computes

Rand = Generate crypto random number
SessionID = SHA256(MS, ver, Rand) "<- though the hash will most likely be dependable on the selected version"
SessionKey = KDF(MS, SessionID)
EncryptionKey = KDF(SessionKey, Rand)
IV/nonce = Generate crypto random number

Server sends message to client: SessionID, Ver, Rand, IV/nonce
Client checks if the returned version he got from the server is actually a version he has (just to be sure). Then the client computes:

SessionKey = KDF(MS, SessionID)
EncryptionKey = KDF(SessionKey, Rand)

If we were to need an extra key (for HMAC) we would simply send over an other random number.

Then finally the client would create a random message and encrypt this message in the propper way according to the selected version. It would send this random message and the ciphertext to the server, the server will either decrypt it or do the same as the client and compare the results. If the results match it will send an OK message back to the client and the communication can commence.

I have a few questions regarding this:

Obviously, is this secure?
Do i need the session key or can i derive the encryption key directly from the MS? (provided the Rand is different each time)
Is the generation of the SessionID ok this way or should a simple random number suffice?
Should the client create a random message and send this over in plain text or should both the server and the client have a message which is 'hard coded' and always use that (it will be the same every session).

I hope it is ok to ask these kind of questions here.

Disclaimer
Lets start of by saying, yes i know making an own protocol is bad mkay. I have discussed this (at length) with my supervisors but (they made a 'fair' point) there is no TLS implementation small enough that can fit on our devices (not much remaining code space). So here I am implementing (it hurts saying this) my own small TLS-ish protocol.

Also, the versions do not correspond to TLS, version 1 might be AES-CBC version 2 might be AES-GCM version 3 might met TDES-CBC (etc.)

This is a very difficult question. But first the standard information:

Don't roll your own crypto if anyhow possible. (which isn't the case here)
No protocol should be considered secure until formally proven secure. (TLSv1.2 is)

That being said I can still provide "ad-hoc" security argumentations why it's likely that your handshake is (in)secure.I can't prove protocols secure. For this need you have to consult special companies or cryptographers who have actually published such proofs.

If a protocol downgrade (which is trivial here) doesn't hurt you you should be safe.
Your encryption key currently is $EK=KDF(KDF(MS||SHA_{256}(MS||Ver||Rand))||Rand)$. I think that just deriving this key like $EK=KDF(MS||Rand)$ is equally secure and a bit faster and you can expand it to $(EK||AK)=KDF(MS||Rand)$ with $AK$ being the authentication key.
The generation of the session ID like this is a nice idea to authenticate the random value at the same time (maybe using the suggestion below).
I'm not fully sure what you mean by this question. But the Rand value is essential to be different each time to get different session keys (what your protocol tries to achieve), so hardcoding them would be a very bad idea.

Some other notes:

You mentioned HMAC for authentication. Please use a standard AEAD construction (->GCM,EAX,...) if anyhow possible.
You may want to consider, if sending the SessionID, that you check the SessionID on the client side, as it is an "authentication tag"
You may also want to consider using a different IV/Nonce for each message and exclude it from the handshake as it doesn't seem to provide any purpose. However, after the handshake it's an interesting idea to exchange random messages to check the key exchange worked.
You may further want to consider replacing the SHA-256(MS||Ver||Rand) by $HMAC_{MS}(Ver||Rand)$ and thus "authenticate" the random value and the version to defend against tampering, this means you also need to actually transmit the tag (which you were already doing).
You may want to consider using a TLS-PSK cipher suite, like TLS_PSK_WITH_AES_256_GCM_SHA384, but then you'd loose the session key property of having different keys as all session keys will be equal (somewhat defeating the purpose of your protocol), but you could use the "other_secret" field to insert some random negotiated data (using your above protocol) and be confident that you use "fully" TLSv1.2 and have key-freshness.


Security of a parallelizable block cipher mode This is the scheme of a parallelizable block cipher mode of operation:

$IV$ is the initialization vector.
$BN$ is the zero-based index number of a block in a stream of data.
$BT$ is the tweak that is used in the encryption process of each block.
$K$ is the key.
$PT$ is a plaintext block.
$CT$ is a ciphertext block.

Encryption and decryption are as follows:

$BT = IV \boxplus BN$
$CT = \mathrm{Encrypt}(K, PT \oplus BT)$
$PT = \mathrm{Decrypt}(K, CT) \oplus BT$

What is obvious to me about this scheme:

It is parallelizable.
It does not suffer from the drawbacks of ECB mode.
There is no cascading effect as seen in CBC, PCBC, and OFB modes of operation.

Are there any security drawbacks with this scheme?

Update: I've considered the criticism and now $BT = \mathrm{Encrypt}(K, IV \boxplus BN)$. What impact does this have on the security?

One of the basic security requirements of a block cipher mode of operation is that it is indistinguishable under chosen plaintext attack (IND-CPA).  Essentially, this means that, if an attacker chooses two messages $m_A$ and $m_B$ and the defender randomly returns either $\text{Encrypt}(K, m_A)$ or $\text{Encrypt}(K, m_B)$ (with $K$ kept secret from the attacker), the attacker should be unable to determine whether the defender chose $m_A$ or $m_B$.

This scheme is not secure under that definition.  Here's how an attacker can win (assume $n$ is the block size).

The attacker submits $m_A = 0^n \| 0^n$ (two zero blocks) and $m_B = 0^n \| 0^{n-1}\|1$ (a zero block, and a block that is all zeros except the last bit).
If the defender chooses $m_A$, it will return $E(K, 0^n \oplus BT_0) \| E(K, 0^n \oplus BT_1) = E(K, IV) \| E(K, IV \oplus (0^{n-1} \| 1))$.  In other words, the output blocks will be different.
If the defender chooses $m_B$, it will return $E(K, 0^n \oplus BT_0) \| E(K, (0^{n-1}\|1) \oplus BT_1)$, where $E$ is the block cipher.  This simplifies to $E(K, 0^n \oplus IV \oplus 0^n) \| E(K, (0^{n-1}\|1) \oplus IV \oplus (0^{n-1}\|1)) = E(K, IV) \| E(K, IV)$.  In other words, the output blocks will be the same.

The attacker can easily distinguish which plaintext the defender chose.  This violates IND-CPA, which often leads to vulnerabilities in real-world systems.

Counter mode seems to offer similar benefits without the security problems: parallelizable, random access, etc.


What telltale signs would indicate that quantum computers are about to become dangerous to classical cryptography? What would be telltale signs that quantum computers become imminent and sizable danger to classical cryptography in commercial applications ?

Make classical cryptography consist of symmetric algorithms (block ciphers, hashes), and asymmetric algorithms assuming hardness of factorization or discrete logarithm in $\Bbb Z_p$ or Elliptic Curve, with parameters large enough to reach security against classical algorithms run on world-class classical computers. Perhaps, assume access to all results in the field of quantum computing (even secret ones: you are CIA analyst with eyes everywhere).

I suggest "imminent" to be 2 years and "sizable" to be something worth betting for if winnings are 100 times the bet; but feel free to parametrize or change that.

Please develop rational arguments (preferably quantitative) e.g. based on categorizing what's achievable using various breeds of quantum computers, what inherently limits progress in the field, and comparison to other technical advances.

Motivation: this May 18, 2018 article quotes the director of a research lab involved in the development of quantum computers:

  "Anyone that wants to make sure that their data is protected for longer than 10 years should move to alternate forms of encryption now"

and based on that source, the journalist writes:

  Quantum computers will be able to instantly break the encryption of sensitive data protected by today's strongest security (..) This could happen in a little more than five years because of advances in quantum computer technologies.

There are three main standard quantum threats to traditional cryptography:

Shor's algorithm.  Spend $O(\log \ell \cdot \log \log \ell)$ quantum gates and $O(\log \ell)$ additional qubits in a quantum circuit to compute the period of a function $f$ bounded by $\ell$.  The number of quantum gates to compute $f$ is about the same as the number of classical gates, and the number of qubits is about double the number of classical bits to be reversible.

Standard examples:

Fix a group $G$ of order $q$, say $(\mathbb Z/p\mathbb Z)^\times$ for prime $p$, or the $k$-rational points $E(k)$ on some elliptic curve $E/k$ over a field $k$.  For $g, h \in G$, define $f(x, y) := h^y g^{-x}$.  If $h = g^n$ for some integer $n$, then $f(x, y) = g^{n y - x}$ and any period $(\delta, \eta)$ of $f$ satisfies $g^{n y - x} = g^{n (y + \delta) - (x + \eta)}$ for all $x$ and $y$ including zero, so that $0 \equiv n \delta - \eta \pmod q$, from which we can recover $n \equiv \eta \delta^{-1} \pmod q$.  Hence by finding a period $(\delta, \eta)$ of $f$, Shor's algorithm computes discrete logs.
Let $n = pq$ be a product of two secret large primes $p$ and $q$.  If for random $a \in \mathbb Z/n\mathbb Z$ the period of $f(x) = a^x \bmod n$ is $2r$ and $a^r \not\equiv -1 \pmod n$, then $\gcd(a^r \pm 1, n) \in \{p,q\}$, yielding a nontrivial factor of $n$.  If not—if the period of $f$ is odd, or if $a^r \equiv -1 \pmod n$—then try again with another $a$.  Hence by finding a period $2r$ of $f$, Shor's algorithm factors integers.

The current record for Shor's algorithm in 2012 computed the period of $x \mapsto 4^x \bmod{21}$, which is (spoiler alert!) 3, by reducing the machine to a single qubit and a single qutrit and computing bits of the period one serially, rather than two control qubits and five work qubits as the algorithm would generally require for integers of that size to give the answer all at once.

This record is not much of an improvement over the first report of Shor's algorithm in 2001, which computed a period of 2 or 4 for $x \mapsto a^x \bmod{15}$ using seven qubits without the qubit recycling that enabled the 2012 record to use fewer qubits.

To scale this up to numbers of thousands of bits, we would need a much larger quantum computer than that.  There are various estimates of how many qubits and quantum gates we need[cetacean needed].  Allegedly IBM has made a 50-qubit quantum computer, and Google has made a 72-qubit quantum computer, but nobody has reported successfully running Shor's algorithm on them.  Evidence that quantum circuits can be scaled up to run Shor's algorithm beyond a handful of qubits to find periods larger than 4 will be a necessary first step before it threatens cryptography based on abelian hidden subgroups.  The adiabatic quantum computer of D-Wave is unfit to run Shor's algorithm.  But:
Quantum annealing to factor by optimization.  Given $n = pq$, write $n = \sum_i n_i 2^i$, $p = \sum_i p_i 2^i$, and $q = \sum_i q_i 2^i$.  Knowledge of the bits $n_i$ of $n$ yields a system of quadratic constraints for the unknown bits $p_i$ and $q_i$ of $p$ and $q$.  This is a system of $O(\log n)$ equations in $O(\log n)$ unknowns.  Use classical computation to optimize away some of the unknown variables to reduce the system of constraints.  For example, we can posit that $p_0 = q_0 = p_{\lambda-1} = q_{\lambda-1} = 1$ since the factors are odd and of known size, where $\lambda$ is the size of the factors, typically 1024 for a 2048-bit modulus.  Then use quantum annealing on an adiabatic quantum computer to find the values of $p_i$ and $q_i$ minimizing $(n - pq)^2$ with $O(\log^2 n)$ qubits.

The current records for factoring by annealing in 2018 use 94 qubits to encode this optimization problem for 376289, along with >1000 additional qubits to implement the optimization on the D-Wave 2000Q.  The paper's estimate for the number of qubits to factor the current classical RSA-768 record with this method is 147456, in contrast to this ‘RSA-19’ problem taking 94 qubits—and that doesn't count the additional >1000 qubits needed to implement the program on the D-Wave machine.  (It is unclear to me whether those are counted in the $O(\log^2 n)$ growth curve advertised for this method, but I assume they are.)

One paper pointed out that other integers have been accidentally factored by the same method ‘without awareness of the authors’ of the prior method, but all this means is that the other integers turn out to have essentially the same set of constraints; it implies nothing about the cost of a high probability for success at factoring random semiprimes as chosen in RSA key generation.

D-Wave's computers seem to be getting bigger, but to my knowledge it remains unclear whether they actually provide quantum speedup at all vs. any specialized hardware to solve optimization problems.  Even if they do, it is unclear what the scaling of the time-to-solution will be as a function of the number of variables or constraints, which nobody seems to have attempted to address short of fitting a curve to small samples of experiments.  Answering these questions—is quantum annealing faster than classical annealing on specialized hardware, and how does time-to-solution scale for optimization-based factoring?—is a necessary first step before this technique will even begin to threaten cryptography based on factoring.
Grover's algorithm.  Spend $O(2^{n/2})$ time evaluating a boolean circuit in quantum superpositions of inputs to find a preimage among $O(2^n)$ possibilities.

There's some literature on experimental realizations[cetacean needed], including combining it with optimization-based factoring in a quantum circuit rather than on an adiabatic quantum computer[cetacean needed], but I'm out of time to bloviate about this for now.

Mitigations for Grover's algorithm are widely known, if excessively conservative[cetacean needed], by increasing symmetric key and hash sizes.  Grover's algorithm could in principle threaten factoring-based cryptography using Grover-ECM[cetacean needed], again requiring doubling of the prime sizes, but to my knowledge it doesn't improve attacks on modern elliptic-curve cryptography[cetacean needed].


An ECDSA signature works the following way:

We work in a sub-group of a curve. The generator is $G$ and it has order $q$ (a prime number). With most curves, $G$ actually generates the whole curve.
Private key is $x$, and corresponding public key is $Q = xG$.
To sign a message $m$:

Hash message $m$, with result being truncated/reduced modulo $q$: $h = H(m)$.
Generate a random $k$ modulo $q$ (or a non-random one, if using deterministic ECDSA).
Compute the point $kG$ and get its $X$ coordinate. The first half of the signature is $r = X \pmod q$.
Second half of the signature is $s = (h+xr)/k \pmod q$.

To verify a signature:

Hash message $m$ again, to get $h$.
Compute $w = 1/s \pmod q$.
Compute point $whG + wrQ$ and check that its $X$ coordinate, when reduced modulo $q$, yields $r$. Indeed, if the signature was properly computed, this expression recomputes the point $kG$ that was produced during signature generation.

There is no known forgery attack on ECDSA when expressed as above. The email you quote implicitly considers the case of ECDSA without the hash function. Or, said otherwise, whether one can make a forged value with $h$ considered as "message input".

For instance, take the point $Q$ (the public key) and extract its $X$ coordinate; call that $r$. Then set $s = r$. The $(r,s)$ pair is a valid signature for a message $m$ such that $h = H(m) = 0 \pmod q$. Indeed, it fulfills the verification equations: $w$ will be equal to $1/r \pmod q$, so $wrQ$ will yield simply $Q$, and since $h = 0$, then the $whG$ component will simply vanish. So the verifier will end up with point $Q$, whose $X$ coordinate indeed yields the $r$ value from the alleged signature.

Now this is not a true forgery in that you get a value which is a valid signature for a message that you do not know: the signature is valid for message $m$ which is such that $H(m) = 0 \pmod q$. But good luck with finding a matching $m$...

None of this is new, but it highlights the important role of the hash function in the process: ultimately, the preimage resistance of the hash function is crucial for resistance against forgeries.


Does chaining random number generators lead to loss of randomness? Assume you chain random number generators, i.e use the result of one PRNG as the seed for the next. What kind of errors can that introduce in the randomness of the numbers generated?

The practice you describe is acceptable and secure.  As long as each of the cryptographic PRNGs has no weaknesses and you use a seed of sufficient size, this is safe.

Whether it is desirable is a separate question.  Do you really have a valid reason why you need to do this?  If not, it's just adding unnecessary complexity and extra "moving parts" that can go wrong somehow.


Is possible that find numbers where the product of 3 numbers is congruent modulo to 1? It is possible that find the $a, b, c$ randomly in here?
$$
abc \equiv 1{\pmod {\varphi (N)}}
$$
Instead of
$$
de \equiv 1{\pmod {\varphi (N)}}
$$
in the RSA Algorithm.

It is possible that find the a, b, c randomly in here?  $abc \equiv 1{\pmod {\varphi (N)}} $

The most obvious way is to select $a, b$ randomly (relatively prime to $\phi(N)$), and then compute $c = (ab)^{-1} \bmod{ \phi(N) }$.  It is easy to show that if $a, b$ are chosen uniformly and independently from $\mathbb{Z}_{N}^*$, then $c$ is also chosen uniformly.


averaging attack at Google's RAPPOR I am reading the paper - "RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response".

I don't understand how the averaging attack works.

I searched for "average attack" but couldn't find a related explanation.

Can someone explain it to me?

Thank you!

If someone has a large set of values:

$$B + \epsilon_0, B+\epsilon_1, B+\epsilon_2, …, B+\epsilon_n$$

One can average all these values together.  If the values of $\epsilon_0, \epsilon_1, \epsilon_2, …, \epsilon_n$ are independently distributed with a mean of 0, the average of these values will be closer to $B$ (essentially reducing the size of the error value by a factor of $\sqrt{n}$ on average).

So, if the attacker has access to a sufficiently large set of values, he can get an arbitrarily close idea of where the underlying $B$ is.

So, what Google is mandating is that you don't get the adversary access to such an independent set of $\epsilon$ values; if you always use the same error vector each time for a specific $B$ value, this averaging tells the adversary nothing he didn't already know.


Possible to guess RSA public key $e$ using $n$ and $\phi$ We know that if $n$ and $\phi$ is known, then it is possible to find $p$ and $q$ (initial prime numbers). I have following the questions:

Assume the public key $e$ is not known, how difficult would it be to guess the public key using $n$, $\phi$, $p$ and $q$?
Assuming we have $c_1$, $c_1 = m^e \bmod n$ is it possible to find out $m$ without knowing $e$ and $d$ ?
From my point of view $ed = K*\phi(n) + 1$ it is difficult to guess $e$ and $d$ product. Will it fall into the factorization problem ? Is this the only equation with $n$ and $\phi$ that involves $e$ and $d$ ?
Can we use some algorithm for guessing $e$ and $d$ ?

I know $e$ needs to be published publicly but if $e$ is lost how can it be identified?

Assume the public key $e$ is not known, how difficult would it be to
  guess the public key using $n$, $\phi$, $p$ and $q$?

$e$ can be chosen completely arbitrary and independently of the modulus and related variables ($\phi,p,q$). You can't learn anything about $e$ (assuming $d$ isn't given) only with the modulus given.

  Assuming we have $c_1$, $c_1 = m^e \bmod n$ is it possible to find out
  $m$ without knowing $e$ and $d$ ?

To recover $m$ you need to know $d$ (by the RSA assumption), so there's no way to recover $m$ without $e$ or $d$.

  From my point of view $ed = K*\phi(n) + 1$ it is difficult to guess
  $e$ and $d$ product. Will it fall into the factorization problem ?

You can arbitrarily choose either $e$ or $d$. The other one is a direct result of the above equation. You can't learn the $K$ either (how would you?) so even the ability to factor won't help you. Even if you'd know $K$ factoring the product would still be quite infeasible as this would be of the same size as the modulus, for which factoring is considered infeasible.

  Is this the only equation with $n$ and $\phi$ that involves $e$ and $d$ ?

Yes, this is the only RSA related equation involving, or rather this is the only equation: $ed\equiv1\pmod\phi$.

  Can we use some algorithm for guessing $e$ and $d$ ?

If you're lucky, you can indeed. $e$ usually takes the values $3,17,65537$ and if those don't yield the correct messages, you can still try each possible (small) $e$ value until you hit a good one. If $e$ is larger than $\approx 2^{40}$ you'll have a hard time finding this value.


PBKDF2 for login key, scrypt for encryption key I need to derive two keys from a single password client side.
One for in-browser login, the other for encryption.

Is the following secure ?

login key      = pbkdf2(password, salt1, lowN)
encryption key = scrypt(password, salt2, highN)

Explanation:

Server shouldn't know plain password
salt1 is retrieved from server upon login
User logs in using login key, download data + salt2, then decrypt it using encryption key client side.
I would love to just use scrypt (stronger), but the only vetted key derivation JS library I found is pbkdf2 by SJCL. Plus I need user to be able to login to website from mobile devices.

Server shouldn't know plain password

If the user types their password into a web page in a browser, the server that hosts that web page always has the opportunity to see what password was entered.  There's no cryptographic mechanism that can prevent that (at this point in time).

To get around this limitation, you need to build a downloadable application instead (e.g. you could use NW.js and Cordova to package up HTML/JS/CSS into desktop/mobile apps).  If you don't do this, there's essentially no point in trying to hide the password from the server.  More about that in this article.

If you've done that (again, no point in continuing if you haven't), I would recommend against using a JS implementation of PBKDF2 or scrypt, if possible.  A JS implementation of either will be slower and force you to use a lower iteration count (since users will only wait so long).  Attackers will have access to a highly optimized C implementation, so this would give your attackers a significant advantage.  Note that most languages have wrapper libraries for C implementations of PBKDF2 or scrypt (e.g. node-scrypt).

To derive the keys, I recommend taking the following approach on the client:

Derive one 256-bit master key using scrypt (PBKDF2 is also acceptable).  Use security parameters that are as high as practical, but keep in mind that mobile devices might have a rough time.  I recommend using a unique salt for each user.
Use HKDF-SHA256 to derive a login key.  HKDF allows you to safely derive keys from a master key such that it is infeasible to determine the master key (or other keys) from the derived keys.  In the context or info parameter, use the string "server-login-key".  128 bits of output should be adequate.
Use HKDF again to derive an encryption key.  Be sure to derive the encryption key from the master key, not the login key.  In the context/info parameter, use the string "client-encryption-key".  Generate a key long enough to match whatever encryption algorithm you plan to use (e.g. 256 bits for AES256).

When storing the login keys on the server, be sure to treat them like passwords (store only the salted hashes).  You may use PBKDF2/bcrypt/scrypt here again, but it's not critical since the key has already been stretched.  Additional stretching is a good thing, but it won't help if the server is actually malicious.

An important difference between this and your design is that it invokes PBKDF2/scrypt only once, instead of twice.  This allows you to double the security parameter (i.e. one invocation with 2N iterations instead of two invocations with N iterations each).

If users don't have strong passwords, then the server will be able to crack the password based on the login key (dictionary attack), so give careful thought to this as well.

Note: The "Extract" step of HKDF is optional in this case because PBKDF2 and scrypt already output cryptographically strong keys, but it won't hurt.


Is the HNF basis the worst basis for a lattice? I am researching lattice problems and some methods for solving them. I read some books that mentioned Babai's algorithm for finding the Closest Vector Problem (CVP) cannot be successful with a "bad" basis for a lattice.

Which begs a question: what is the worst basis for a lattice?

Is the HNF basis the worst basis for finding CVP in a lattice?

Whether an algorithm succeeds or not for solving e.g. CVP depends on the quality of the basis, which for instance can be measured in terms of the sum of the norms of the basis vectors. Your question could therefore be interpreted as: does the HNF give you the basis of the lattice with the worst quality?

The answer has to be no to this. Suppose w.l.o.g. that the lattice lives in $\mathbb{Z}^n$, and the sum of the norms of the basis vectors of the HNF basis is $M$. Now clearly there can only be finitely many bases of the lattice for which this quality measure is less than $M$, as we can just enumerate all possible such bases. On the other hand, there are infinitely many bases for each lattice, and so there must be a basis with even worse quality. It all depends on how you define "quality", but for most sensible definitions there is no "worst quality" - you can always get a worse basis.

More concretely, given a basis matrix $B$, you can obtain another basis $B' = U \cdot B$ by multiplying $B$ with any unimodular matrix $U$. By taking a $U$ with huge entries, $B'$ will likely be a much worse basis than $B$.


You are correct—you do want to find a small root of [*]
$$
  f(x) = M \cdot x + (65537^a \bmod M) \bmod N
$$
modulo a divisor $p$ of $N$. In other words, you want to find a divisor of $N$ in the residue class $M \cdot x + (65537^a \bmod M)$. This is explicitly accomplished by the Coppersmith/Howgrave-Graham method, as long as the appropriate restrictions are respected.

However, Coppersmith's method to find such roots traditionally expects a monic polynomial as input. So, to make it monic we simply divide it by the coefficient associated with $x$, that is, $M$:
$$
  g(x) = \frac{1}{M}f(x) = x + \frac{65537^a \bmod M}{M} \bmod N\,.
$$
The roots of $g(x)$ are the same as $f(x)$; to see this decompose the polynomial into its factorization:
$$
   f(x) = (x - \alpha_0)(x - \alpha_1)\dots(x - \alpha_n)\,,
$$
$$
g(x) = \frac{1}{M}(x - \alpha_0)(x - \alpha_1)\dots(x - \alpha_n)\,,
$$
and notice that both have the same roots $\alpha_i$. The Coppersmith method finds the appropriate root modulo a factor of $N$ once you guess the correct $a$.

[*]: The ROCA paper uses alternative $M'$ there, but this is irrelevant here.


Usefulness of blockchain technology in private sector I understand that blockchain technology works for cryptocurrency.
But I don't get why it should be used in private sector.
For example, I often read that it is useful to monitor the supply chain of food.
But why is that? If a company uses blockchain technology for that, how does it work?
From my understanding, in that case it is hard to get a distributed blockchain.
But with a non-distributed blockchain, I only see disadvantages.
Why not use a good old standard database in such cases?
Am I missing something?

Why not use a good old standard database in such cases?
Am I missing something?

No; you understand it perfectly well! It's nothing more than a particularly strange form of data integrity assurance (that, as you quickly realize, is trivially bypassed if not distributed across multiple nodes). If you're not using it as a resistance to adversarial peers, and you're not using it for consensus-building purposes, then there's little benefit to be wrung from prefacing each $\text{block}_n$ with $H(\text{block}_{n-1})$.
Even distributed systems such as highly-available and fault-tolerant hypervisors that have to "solve" the Two Generals Problem accomplish their task perfectly fine with non-blockchain-based consensus algorithms.
(However, as the commenters note, this is much more of a systems engineering question than a cryptographic one.)

I will amend this answer to note that Merkle trees per se can be useful in situations where you require, for instance, the public to be able to easily audit or assure themselves that some log has remained append-only, such as in the Certificate Transparency security addition to HTTPS. But (again a nod to Peregrinus) these aren't "blockchains"* since they're not being leveraged for consensus: the scheme itself imposes no restrictions on the whole thing being rewritten; all the auditors can do is sound the alarm if they see a fork in the tree.
(*As evidenced by the fact that a quick search turns up a whole host of schemes proposing blockchain-based augmentations of CT.)


Second generator for secp256k1 curve I want to get a group element $h$ on the elliptic curve secp256k1. The important thing is that no one should know the discrete logarithm of $h$ with respect to $g$. That is, $h$ should be created from a public beacon and not by exponentiating $g$. What's the best way to do this?

You want to hash the existing generator $g$ then coerce that hash to a curvepoint. This will result in a generator which is uniformly independent of $g$ (well, in the random oracle model anyway) and also commits to $g$ so that neither generator can be changed (say, to introduce a correlation) without changing the other.

The "obvious" way to avoid correlations, which is deriving $h$ from a nothing-up-my-sleeve (NUMS) number, suffers from the problem that the SECG generator $g$ does not have a clear origin -- it is not NUMS -- so it is possible that somebody knows the discrete log of $g$ with respect to some NUMS point. (Thanks Adam Back for pointing this risk out to me.)

To coerce a hash function to a curvepoint you can use functions from this paper (thanks Greg Maxwell for this link), for example... or you could just take the hash as the $x$-coordinate of your point and keep incrementing it by small integers until you are able to produce a valid curvepoint.


Is it necessary to use single hash function for signature generation and HMAC? I am trying to figure out if we need to use single hash function across all the places in a ssh session. i.e – signature generation/verification and HMAC calculation/validation. Is it possible to use two different hash function for signature and HMAC?

I am planning to implement SHA-256 for signature generation/verification in an embedded system. But I am concerned that if I use SHA-256 for HMAC also then there will be much impact on performance considering the lesser CPU capacity of the embedded system. I am new to cryptography so I am not much aware of these things. It will be great if anyone could help.

As both of us recently learned, the public key signature hash algorithm is negotiated completely separately from the MAC algorithm. DSA and RSA use SHA-1, ECDSA uses SHA-2, and Ed25519 uses, um, Ed25519.

I'm skeptical that SSH crypto performance will be a serious issue for you. I suspect you would have to be transferring a lot of data on a really bad CPU for it to be a problem, that any performance issues you have will probably be elsewhere, and that tinkering with SSH won't make a big difference. Nonetheless, HMAC-MD5 should be the fastest HMAC variant. On the other hand, SHA-1 or SHA-2 are only like twice as slow as MD5, and using one of them may save you from having to implement two different hash functions.

SSH supports other MAC schemes that don't use HMAC at all, and are likely faster. OpenSSH supports UMAC, and there are two AEADs available as well: the standard AES-GCM (implemented incompatibly by OpenSSH) and the new and OpenSSH-only ChaCha20-Poly1305. Without hardware support, ChaCha20-Poly1305 would probably be faster than AES-GCM, and definitely easier to implement safely.

I'd also caution you that writing crypto code is extremely dangerous, with many sharp edges and ways to shoot yourself -- and, worse, your users -- in the feet. It would be better to rely on well-vetted, preexisting software if at all possible.

(Hi e-sushi. :-)


How does the Blowfish algorithm key initialization work I'm having some trouble understanding the Blowfish encryption algorithm.  From the Wikipedia article...

  The secret key is then, byte by byte, cycling the key if necessary, XORed with all the P-entries in order

Can someone explain this in more detail?  For example, the first few P entries are 0x243f6a88, 0x85a308d3, 0x13198a2e, 0x03707344,...

Supposing the secret key is abcd, how would I implement this part of the algorithm?

The quoted passage of the Wikipedia article is wrong does not at first reading seem to match Blowfish as in Bruce Schneier's Description of a new variable-length key, 64-bit block cipher (Blowfish) (in proceedings of the first FSE conference, held Dec. 1993) which for this same operation reads:

  XOR P1 with the first 32 bits of the key, XOR P2 with the second 32-bits of the key, and so on for all bits of the key (possibly up to P14). Repeatedly cycle through the key bits until the entire P-array has been XORed with key bits. (For every short key, there is at least one equivalent longer key; for example, if A is a 64-bit key, then AA, AAA, etc., are equivalent keys.)

In C++, if P and key are arrays of 32-bit words, and keylen (from 1 to 14) is the key size in 32-bit increments, this can be implemented as shown in the wikipedia article:

for (int i=0 ; i<18 ; ++i)
   P[i] ^= key[i % keylen];

Customarily conversion of key bytes to the array key, and constants for initialization of P, is big-endian (as traditional in cryptography for many things such as DES, RSA, SHA, AES, but not MD5).

Many actual implementations of Blowfish accept keys with size any multiple of 8-bit, and there's nothing in Bruce Schneier's description to forbid that. To cover this, if P is an array of 32-bit words, key is an array of 8-bit bytes, and keylen is the key size (from 4 to 56) in 8-bit increments, the loop can become, on an big endian machine:

for (int i=0 ; i<72; ++i)
   ((uint8_t*)P)[i] ^= key[i % keylen];

or, to keep the code endian-neutral:

for (unsigned i=0 ; i<72; ++i)
   P[i>>2] ^= ((uint32_t)key[i % keylen])<<((3&~i)<<3);

Note: the shift count computed as (3&~i)<<3 is 24, 16, 8, 0, 24, 16, 8, 0, 24.. when i is 0, 1, 2, 3, 4, 5, 6, 7, 8..

Note: while Blowfish's definition states a minimum key size of 32 bits, some implementations lower that to 8 bits, including the one that was used for these test vectors of Blowfish with variable key length (also available as a C header). Further, some implementations (especially of Blowfish as used in Bcrypt) allow up to 576-bit keys (72 bytes), rather than 448-bit (56 bytes).

Example 1: if the key is the string abcd in ASCII, the array key (viewed as a 32-bit array) is the single element 0x61626364; thus after processing the key,
P[ 0] is 0x243F6A88^0x61626364 that is 0x455D09EC,
P[ 1] is 0x85A308D3^0x61626364 that is 0xE4C16BB7,..
P[17] is 0x8979FB1B^0x61626364 that is 0xE81B987F.

Example 2: if the key is the string abcdJKL in ASCII, after processing the key,
P[ 0] is 0x243F6A88^0x61626364 that is 0x455D09EC,
P[ 1] is 0x85A308D3^0x4A4B4C61 that is 0xCFE844B2,..
P[17] is 0x8979FB1B^0x4B4C6162 that is 0xC2359A79.

Note: there are further transformations of P but they are rather unambiguous; refer to either of the articles.

Final Caution: some Blowfish implementations (especially those used in Bcrypt) are known to vary in how they convert text to bytes before applying the above transformation of key to P; some bugs have even crept there, for example

  Versions of jBCrypt before 0.3 suffered from a bug related to character encoding that substantially reduced the entropy of hashed passwords containing non US-ASCII characters. An incorrect encoding step transparently replaced such characters by ? prior to hashing. In the worst case of a password consisting solely of non-US-ASCII characters, this would cause its hash to be equivalent to all other such passwords of the same length.

Notice that if "of the same length" is necessary in this quotation, then some length, padding or terminating character must have been included in the key converted to bytes (otherwise all passwords consisting solely of non-US-ASCII characters would have been equivalent, regardless of length).


HMAC based challenge-response authentication Would a challenge response HMAC authentication be secure?

i.e.

Client sends id
Server sends a challenge(32byte value)
Client calculates hmac_sha256 of the challenge value with its key and sends the reply
Server verifies the reply

That's as secure as a symmetric challenge-response authentication can be. Some remarks:

In an authentication protocol, the only assurance is that the authenticated party participated in the protocol. It could well be that there's a man-in-the-middle.
Step 1 (sending client ID) can be coalesced into 3 if all clients have to authenticate that way regardless of ID.
At step 2, the server's challenge should be unique and unpredictable. Making that reliable is less easy than it seems.
At step 4, the server must be able to get or regenerate the client's key, from a database of random keys, or a master key and a key derivation function.

The big problems are

Said database or master key could leak for the server, and poof goes all security. One good mitigation is to use a security token (HSM, Smart Card..) in the server, programmed so that it can only check the response to challenges.
The ultimate solution from the standpoint of avoiding server leaks is when there is noting secret in there. Challenge/response replacing HMAC with a signature allows just that.
Authentication is one thing, securing what follows next is better. That's why we have authentication-and-key-agreement protocols. Good ones resist man-in-the-middle.
The client's key (symmetric or asymmetric) can be compromised on the client side. A password (and proper password-based key derivation) to encipher the key-at-rest in the client might help, but is less convenient than directly using the password as an authentication mean. That's why we have SRP and ISO/IEC 11770-4.


Choosing UWP encryption algorithms I've just come across the large variety of encryption ciphers available in the UWP WinRT API, both symmetric and asymmetric. I'm trying to figure out which are commonly seen as the most favourable from the choices available for UWT (obviously this is very context specific, but surprisingly many seem to be outdated or clearly just "worse").

With symmetric, I've seen that AES is usually a good go-to algorithm of choice (this post for example), and this site says AES_GCM is pretty much the best variant.

With asymmetric the two main options presented in UWP's API are ECDSA and RSA. I was sceptical if ECDSA was actually an encryption algorithm, but this answer certainly made it seem so, even if the name says "digital signature". Now all of these names include a hash, and their descriptions state that there is signing involved with this hash, which confused me. Why is this explicit encryption algorithm signing this stuff too?
Anyway, this post, and this article both suggest that OAEP is better than PKCS#1, which then leaves us with the following options for asymmetric encryption:
ECDSA_P256_SHA256
ECDSA_P384_SHA384
ECDSA_P521_SHA512
ECDSA_SHA256
ECDSA_SHA384
ECDSA_SHA512
RSA_OAEP_SHA1
RSA_OAEP_SHA256
RSA_OAEP_SHA384
RSA_OAEP_SHA512
Given that P256, P384 and P521 are the public key size for ECDSA, then that raises the question of what the difference is with the ECDSA without P256, P384 or P521? What applicable difference do these differences make?

Okay, cheers for reading so far! I've summarised my questions below:

Is the assumption that AES is "best" a valid one, alongside the assumption for AES_GCM?
Is ECDSA actually an encryption algorithm, given the name?
Why do the UWP API asymmetric encryption algorithms all reference signing with hashes in their descriptions? Is this really the case, and if so why? Surely if they wanted authentication through signing it would be a separate process?
Is OAEP generally considered better than PKCS#1?
What is the difference between the ECDSA algorithms which do and don't specify public key size (eg ECDSA_SHA256 vs ECDSA_P256_SHA256)?
What difference do the hash sizes (and public key sizes for ECDSA if relevant) make, and what about if authentication isn't needed (which I guess would be why they're hashing and signing in the first place)

Any and all help is greatly appreciated, thank you for your time! :D

Is the assumption that AES is "best" a valid one, alongside the assumption for AES_GCM?

Opinionated, but Microsoft doesn't implement a lot of modern ciphers, so AES is the tried and true one. If GCM mode is best depends on the use case really, but as it is an authenticated mode - it includes a MAC - it is generally better than e.g. ECB / CBC which aren't.

Is ECDSA actually an encryption algorithm, given the name?

Asking the question is answering it: no it is not. However, using ECIES, you can use the keys both for ECDSA and ECDH, and ECDH enables ECIES, which is an encryption scheme.

Why do the UWP API asymmetric encryption algorithms all reference signing with hashes in their descriptions? Is this really the case, and if so why? Surely if they wanted authentication through signing it would be a separate process?

I don't know, Microsoft webpages are down, I get a 403. Oh, they are up again, and they are as helpful as ever. Off topic here though.

Is OAEP generally considered better than PKCS#1?

PKCS#1 v2.0 is the standard that defines OAEP, so that's a nonsensical question if you take it literally. Yes, generally it is considered more secure than PKCS#1 v1.5, which is what "PKCS#1" usually refers to. Although you could say that this is opinionated as well, at least OAEP has got a proof that it is secure given that RSA is secure.

What is the difference between the ECDSA algorithms which do and don't specify public key size (eg ECDSA_SHA256 vs ECDSA_P256_SHA256)?

That's more of an issue with the API, maybe the P256 one assumes the Certicom named curve with the NIST standardized name. Again, not specified.

What difference do the hash sizes (and public key sizes for ECDSA if relevant) make, and what about if authentication isn't needed (which I guess would be why they're hashing and signing in the first place).

Hashes are used for a lot of things, e.g. OAEP uses them internally as well, but not to authenticate the message. In ECDSA they are used to hash the message, which is then used in signature generation and verification. Generally a larger hash output size / key size means more secure.


Random Oracle to prove an Authenticated DH protocol I am trying to understand how they use the random oracle to solve the CDH. For example, in the security proof on page 7 of the following paper; A Lightweight Message Authentication Scheme for Smart Grid
Communications, Fouda et al. 2001. The authors used a random oracle to break the security of an authenticated DH protocol. They assumed an adversary who can break the semantic security of the shared key and used this adversary along with a random oracle to solve CDH.

to my understanding a random oracle is like a hash function where the input is a random string and the output also is another random string, so how can we use to solve the CDH;
in the paper, they gave the adversary a tuple $(g, g^a, g^b)$ and allowed him to make a query to the random oracle. Then, they tracked the queries to the random oracle to monitor of $g^{ab}$ was queried. But Why would the adversary query g^ab to the random oracle? Is it part of the game?

Answers to your questions:

1) Random oracle - is a replacement for hash-function. Its input is any bitstring, and output - random string. In some sense - it's an ideal hash-function. But in order to evaluate it, you (attacker) need to explicitly ask the oracle.

2)  "Why would the adversary query g^ab to the random oracle. Is it part of the game?" - no, adversary of course isn't obligated anything for you, and it isn't obligated to ask ROM for $g^{ab}$. But, easy to see, that if the attacker didn't ask oracle for $g^{ab}$, he has only a negligible probability of success.
In the article it's simply expressed as "has no idea on the session key"; it's indeed true - recall that oracle will return some random string for this input, regardless of all previous actions/queries of the attacker.
While it's not a rigorous mathematical statement, it still correctly describes what happens.

In addition, I would try to explain why this ROM model good for modeling hash function. In this proof we essentially use the fact that any attacker will explicitly ask the oracle for hash-values, and we can track all these queries.
While in real life, for real hash function, we can't track attacker actions.
But, if hash-function is good (ideal), to get hash-value everyone needs to honestly calculate it by applying hash-function to some input (e.g.,
you can't derive hash-value of some input from hash-values of other, even somehow related, inputs).
So, if hash function is good enough, any successful attacker at some point should calculate hash from $g^{ab}$, i.e. this attacker should know $g^{ab}$ at some step. So, this attacker is able to solve CDH. This is a meaning of this proof in ROM. It doesn't mean that for any hash-function it's true - it's only true for good hash functions, which are really unpredictable and behave like random oracles.


Is it possible to perform an MPC protocol to compute a product in a polynomial ring? I hope not to be asking much, but I have N parties, each one holding a polynomial in with 0-1 coefficients and fixed degree $n-1$. I was wandering if it is possible (I mean feasible) to compute the product of all of these polynomials with an MPC protocol.

Actually, for security I would need the result modulo $X^n+1$, so my actual request is the following : Given $N$ polynomials $P_1,P_2,\dots,P_N$ with $0-1$ coefficients and degree $n-1$, compute $(\prod P_i)\mod(X^n+1)$ with a multiparty computation protocol where each party holds a $P_i$.

My question regards the complexity of such a product ($O(n \log n\log N)$ integer multiplications if an FFT algorithm is used ?)

It is my first question here, so please attach a welcome message to you answer :-)

You mention a ring but you are only using the multiplication operation. So it's really just a protocol for a group operation that you want. If the group is abelian, then there is a simple classical protocol for $n$-party group product:

Each party performs $n$-out-of-$n$ multiplicative secret sharing of their input. In more detail, party $i$ has input $P_i$ and chooses random polynomials $P_{i,j}$ so that $\prod_j P_{i,j} = P_i$, then privately sends $P_{i,j}$ to party $j$.
Each party $j$ now has $\{ P_{i,j} \mid i \in [n] \}$. He/she computes their product $P'_j = \prod_i P_{i,j}$ and publicly announces $P'_j$.
If the group is abelian, then $\prod_j P'_j = \prod_{i,j} P_{i,j} = \prod_i P_i$, so everyone can compute the final answer from the public $P'_j$ values.

Furthermore, the view of any number of colluding semi-honest parties leaks no more than the final result.


Confused about final subtraction of modulus in Montgomery Multiplication, during modular exponentiation I'm confused about how one might supposedly bypass the final subtraction of the modulus in radix-2 montgomery modular multiplication, when used in a modular exponentiation algorithm. The following two papers put forward the conditions for bypassing the subtraction.

Montgomery Exponentiation with no Final
Subtractions: Improved Results
Montgomery Multiplication Needs no Final
Subtractions

I don't understand exactly what is required in terms of the "preprocessing and postprocessing" to eliminate the need for the repetitive subtraction of the modulus at the end of the montgomery multiplication.

My understanding after reading the above papers is that, to eliminate the final subtractions, you must:

Zero-extend each input operand to the modular exponentiation by two

e.g. new[2049 downto 0]  = (0, 0, old[2047 downto 0])

Increase the loop bound inside the Montgomery multiplications by two, such that two more iterations of the loop are executed

I've made these modifications to a working algorithm, however the results are not as I expect and I do not understand why. Therefore, I assume I am misinterpreting something in these papers, or leaving out a critical step.

Let us refer to my (working) radix-2 montgomery modular exponentiation function in (C-like pseudocode). Note that I have extended the operand width by two most-significant zero digits (just to make sure I'm not overflowing). They used to only be 2048 bits.

let NUM_BITS = 2048
let rsaSize_t be a 2050-bit vector type

// Montgomery multiplication: outData = XYr^(-1) modulo M,
// where the radix r=2^n    (n=NUM_BITS)
function montMult( rsaSize_t X,       // Multiplier
                   rsaSize_t Y,       // Multiplicand
                   rsaSize_t M,       // Modulus
                   rsaSize_t outData) // Result
{
    rsaSize_t S = 0;  // Running sum

    for (i=0; i<NUM_BITS; i++)
    {
        if (X.bit(i)==1) // Check ith bit of X
            S += Y;

        if (S.bit(0)==1) // check LSB of S
            S += M;

        S = S >> 1;   // Rightshift 1 bit
    }

    // HERE IS THE FINAL SUBTRACTION I WANT (NEED) TO AVOID
    if (S >= M)
    {
        S -= M;
    }

    outData = S.range(NUM_BITS-1,0);
}

//  montgomery modular exponentiation using square and multiply algorithm
//  computes  M^e modulo n, where we precompute the transformation of the
//  base and running-partial sum into the montgomery domain
function rsaModExp( rsaSize_t e,     // exponent
                    rsaSize_t n,     // modulus
                    rsaSize_t Mbar,  // precomputed: montgomery residue of the base w.r.t. the radix--> (2^2048)*base mod n
                    rsaSize_t xbar,  // precomputed: montgomery residue of 1  w.r.t. the radix--> 2^2048 mod n
                    rsaSize_t *out)  // result
{
    for (i=NUM_BITS-1; i>=0; i--)
    {
        montMult(xbar, xbar, n, xbar); // square
        if (e.bit(i)==1)
            montMult(Mbar, xbar, n, xbar); // multiply
    }

    // undo montgomery transform
    montMult(xbar, 1, n, out);
}

Am I missing something in the papers? I do not believe this is an implementation error, as my code matches exactly what is put forth in the papers. I believe that I might be a conceptual error. Any and all help appreciated.

Thanks!

The problem was that there was one additional thing I left out....if I'm increasing the loop iteration count and the number of bits from 2048 to 2050, then I had to choose a new R to satisfy the preconditions of Walter's optimization.

$R=2^{bitwidth} $ so I needed to have $R=2^{2050}$ instead of $R=2^{2048}$.

I'd now like to modify this to use multiple word scanning, as suggested by @Ruggero, and have a few follow up questions so will open another thread.


Counter mode secure hash algorithm Ever since the SHA-3 competition, I've been wondering if it is possible to create a hash algorithm that is easier to parallelize. The current algorithms all seem to require building a tree of hashes. This has however rather serious drawbacks:

as they requires a tree with certain parameters (such as the size of nodes and branches), it needs to be explicitly defined what the tree looks like
communicating parties should be programmed explicitly to allow hash trees
the tree is likely to be optimized for certain configurations, and not all parties will have the same configuration (e.g. an 8 or 16 bit processor checking the hash created by a 64 bit server machine with GPU acceleration)
if the leaves are too big, you need a whole lot of information before you could start with the next leaf
with the exception of Skein, none of the remaining candidates seem to define how the hash tree should even be constructed

Now I am wondering if you could construct a hash algorithm using a PRF that has a counter as input. In this construct, you would have a relatively strong PRF that is fed both the counter and a block plain text, resulting in an output of a known size (step1). This output would then be compressed together with the other transformed blocks in (step 2). Finally, as usual for a hash, you would have a finalization step which avoids length extension attacks (step3).

To allow for easy parallelism, I think that step 2 should be associative. In other words, it should not matter in which order the output of step 1 is given to the function in step 2. If it is associative, it would even be possible to distribute step 2 between the processes as well. In that case, step 2 may even be relatively heavy (sponge like?). The trick, obviously, is to create collision resistance for the combination of step 1 and step 2. This is where my perfect scheme begins to crumble, and I am wondering if it is even possible to create a solution for the problem.

The advantages of such a scheme are obvious: it would have none of the drawbacks of the tree hash scheme. Anybody could generate a hash using as many threads or computing blocks as they want. Only the block size, the output size of step 1 and the state of step2 would be restraining implementations.

The algorithm would of course not be able to use the Merkle–Damgård construction, as it assumes that each block is processed in a sequential fashion - which introduces the problem in the first place. It seems that Merkle–Damgård and variations on Merkle–Damgård  still rule supreme in the SHA-3 competition (at least with most of the final candidates).

[EDIT: By now Keccak has been chosen as winner of the SHA-3 competition, and one of the reasons is that it was the candidate within the 5 remaining candidates that was using a sponge instead of a Merkle–Damgård construction, so I guess that this paragraph is out of date by now]

Unfortunately, I'm not introduced to mathematics enough to see the correct solution, I cannot find if it has been tried, and I'm certainly not able to prove that my scheme would be impossible. Hopefully, this is where you can give me some hints.

First of all, I think I want to correct you at one point; in step 2, you aren't actually that interested in whether the operation is commutative, what you're actually interested in is that the operation is associative, that is, if $(a \oplus b) \oplus c = a \oplus (b \oplus c)$.  In essence, your operator $\oplus$ in step 2 turns out to be a group operation.

Hence, your proposed hash function can be expressed as:

$H(P_1, ..., P_n) = G( \sum_i F( P_i, i ) )$

where:

F is the your so-called 'cipher mimicking counter-mode encryption' (bad terminology, btw) in step 1, which outputs group members
$\sum$ is the group operation sum over all the group members
G is finalization operation in step 3, which takes as input a group member, and outputs the actual hash (and may also take the file length as input; that detail is irrelevant)

Now, assuming that F and G are well-chosen (for example, that it's infeasible to find collisions or preimages in F), the obvious way to attack this construct is to find a collision at the summation step;

for second-preimage on a hash of $P_i$, find a distinct set of blocks $Q_i$ such that $\sum_i F(P_i, i) = \sum_i F(Q_i, i)$
for a collision attack, find distinct sets of blocks $P_i$, $Q_i$ such that $\sum_i F(P_i, i) = \sum_i F(Q_i, i)$

Now, I have good news, and I have bad news.

The good news is that there exists groups where the above problems are NP-hard (!), and even better, one such group is integer addition modulo a large number.  There are also groups where the above problems are easy (such as the group of bitstrings where the group operation is bit-wise exclusive or's), so we'll need to be careful when choosing a group.

Now, the bad news; just because the problem is NP-hard doesn't mean that there aren't shortcuts.  One such short-cut to the second-preimage problem is a square-root attack which works by dividing the blocks $Q_1, ..., Q_n$ into two sets $Q_1, ..., Q_{n/2}$ and $Q_{n/2+1}, ..., Q_n$, collecting sums from both subsets, and scanning the sums for a pair that sum to the target value.  This attack allows us to find a set that sums to the target N-bit value in $\sqrt N$ time; hence the group members must be — at least — twice as big in order to keep the second-preimage problem as difficult as expected.

The update of this observation is that for an $N$ bit hash, the internal sum must be over $2N$ bit values; that means that your $F$ function must generate strong $2N$ bit values, and so ends up being considerably harder to compute than the leaf compression function in a hash-tree construction.


Why does encrypting the Diffie-Hellman value with the other side’s public key prevent man-in-the middle? As far as I understood about Diffie-Hellman, it is easy for the man in the middle to easily decrypt and read the message.

It's because, Eve (attacker) can't break the encrypted data since Eve doesn't have other side's private key. Only by using other side's private key, the encrypted data can be decrypted.

And yes, this is general technique for preventing Man-In-the-Middle attack using asymmetric keys. Diffie-Hellman is Symmetric Key Exchange Protocol, not encryption mechanism.

First two numbers are generated g and p where p is prime.

One side:

$R_1 = g^x \bmod p$ where $x$ is randomly chosen

Send $R_1$ to other side, Receive $R_2$

Calculate key as $K = {R_2}^x \bmod p$

Other side:

$R_2 = g^y \bmod p$ where $y$ is randomly chosen

Send $R_2$ to other side, Receive $R_1$

Calculate key as $K = {R_1}^y \bmod p$

Also, Diffie-Hellman doesn't prevent Man-In-The-Middle; it's one of Diffie-Hellman's weakness and it's vulnerable to it.