"Random permutation" in the random oracle model? I'm trying to read through a paper on ring signatures - "How to Leak a Secret" by Rivest, Shamir, Tauman (link: https://link.springer.com/content/pdf/10.1007%2F3-540-45682-1_32.pdf )

In section 3.2 it is said

  We assume the existence of a publicly defined symmetric encryption algorithm
  $E$ such that for any key $k$ of length $l$, the function $E_k$ is a permutation over b-bit
  strings. Here we use the random (permutation) oracle model which assumes that
  all the parties have access to an oracle that provides truly random answers to new
  queries of the form $E_k(x)$ and $E^{−1}
_k (y)$, provided only that they are consistent
  with previous answers and with the requirement that $E_k$ be a permutation

What exactly does this mean? Is $ E_k $ available to (and only to) parties who know the secret key $k$ and does it give random answers to new queries in the same sense as a random oracle, except it's bijective and there's also the inverse oracle? And is this assumption equivalent to the random oracle model? That is, can we construct $E$ given access to a random oracle?

From the middle of p. 561:

  Algorithm $A$ accepts the public keys $P_1, P_2, \dots, P_r$ (but not any of the corresponding secret keys) and is given oracle access to $h$, $E$, $E^{-1}$, and to a ring signing oracle.  It can work adaptively, querying the oracles at arguments that may depend on previous answers.  Eventually, it must produce a valid ring signature on a new message that was not presented to the signing oracle, with a non-negligible probability (over the random answers of the oracles and its own random tape).

Specifically, $A$ is allowed to query $E$ and $E^{-1}$ at any key and any message, with the keys obtained from the oracle for $h$ as stated a little below.

(It doesn't matter that $A$ is allowed to know the bits of the key because presumably the choice of permutation is independent uniform random for each distinct key, so there's no meaningful structure to be had out of the bits of the key.)


Zero-Knowledge Bingo Bingo is the game of chance where each player matches the numbers on their card with the numbers that the caller draws at random. When the first player has collected enough called numbers on their card, they declare that they have won, and their card is verified.

Imagine this game being played online with players allowed to choose their own card.

Question: Is there a way to play Bingo online and assert that your card won, without revealing what your card is, only that you chose this card at the beginning and that it does contain the called numbers?

Sub-question: Is this a practical application of an existing, generalised problem?

Own thoughts: In the first iteration of this game, we could ask that players publish, signed, which card they chose at the beginning of the game. When the first player has collected enough called numbers, the winner will be apparent. But I don't want for players to publish their card at the start of the game.

In the second iteration of this game, we could ask that players publish, encrypted, which card they chose at the beginning of the game. We could include salt to avoid reverse lookups, and we could include a checksum to ensure that what they publish can't easily be decrypted into any card. But I don't want for players to publish their card at the end of the game, either!

Once a game is won, we know which subset of cards could have won. Perhaps it is possible to say that your card belongs to this subset (with some probability?) without saying what member it is? Perhaps this involves generating a large amount of winning cards, of which perhaps one is the actual winning one, and then prove that your card is one of them, without saying which one it is.

Clarification 1: This problem does not deal with calling numbers in a fair way. Assume that the players cannot predict what numbers are called.

Clarification 2: To prove that you have collected all the numbers, the subset of cards that could have won contains exactly that card, so the method of the first and second iteration are the same; this question applies to the subgoals of collecting one row, two rows...

This seems entirely straight forward. Each player publishes a commitment, essentially a hash of their board. Possibly signed.

If the boards are not high enough entropy themselves we will tack on some random data to increase their entropy to make the result unguessable.

When a player declares victory he will provide a Zero Knowledge proof that he knows of a winning board matching his commitment.

Note Zero Knowledge proofs are very powerful stuff, but we need to open the black box of the functions we use (such as hashing) in order to use them. For any efficiently computeable predicate function $f$ we can prove we have $x$ so that $f(x)=true$ without revealing anything about $x$ beyond the statement.

In our case we would have $f(board)$ be the predicate which checks the board is a winning board and matches our commitment. Obviously trivial to compute.


RSA example-calculation: Public Key = Private Key (e = d) I am a bit confused. I just calculated manually the single steps of RSA for an implementation with small numbers and suddenly $d$ was equal $e$. Please help me understand what I am doing wrong.

Here’s my example:

I chose: $q = 7$ and $p = 11$
$N = 77$
$phi(N) = 60$
I chose: $e = 29$
$e \times d + k \times phi(N) = 1 \rightarrow$ Extended Euclidean algorithm
$$k = -14\\
   d = 29$$

Test: $29 \times 29 + (-14) \times 60 = 1$

Where is the mistake?

The only reason you are seeing this is because you are dealing with such small primes. With primes like we would use in practice (1024 bits), the probability of this happening is very, very small. And, it can only happen when $e>\sqrt{\lambda(n)}$. Since we typically use $e=65537$ in practice, it is guaranteed to not happen.

Anyways, there is no mistake in your calculations, you just happened to pick an $e$ which is its own inverse.


Diode vs quantum computer Consider everyone's favourite pseudo random number generator, RANDU where V is the output of any successive iteration.

$$ V_{j+1} = 65539 \cdot V_j \; mod \; 2^{31} $$

I've purposefully  chosen RANDU because it's not so good a PRNG, but works well in my example. Such linear congruential generators can be easily inverted to recover the state, and hence predict all future values.

Now let's replace the 65539 constant with a normal probability distribution, A. And let's define A as:-

A = NORMAL(μ =~ 65538.5, σ =~ 998) where the values are rough approximations obtained by mysterious empirical means. An integer rounding operation happens somewhere.  It's my cunning model of a diode that might be used for an  entropy source inside a TRNG. A represents the Avalanche Effect inside certain diodes, and looks like a children's Galton board as electrons tumble through the semiconductor material.

Lastly,  assume we have a mega quantum computer slurping up all the output from this random generator.  Are we able to predict the future output, given enough samples? And if not, can we say anything at all about the security of this generator? Would it now be a true unpredictable entropy source, or would we able  to get almost perfect estimates of the future output sequence?

This is a highly theoretical question, but I'm trying to get a perspective on what may /may not be possible in derandomising entropy sources given quantum computers.  I emphasise derandomising, as this and equivalent terms have previously been used in discussions of classical entropy sources for true random number generation. There is a long list of Similar Questions on my screen suggesting the upcoming end of traditional randomness. Some will posit that if the quantum computer can form sufficient simultaneous equations, it can determine the internal state  of the diode via  ersatz linear cryptanalysis. This is my attempt at countering.

Even some at America's NIST say that only a quantum device can produce true randomness, and that everything else produced by classical physics is just not. They say:

  No device that relies on classical physical principles or operations can certify that its output is absolutely unpredictable.

News(?) to the UK government who regularly certify ERNIE running the country's national savings scheme. And he runs on diodes. Are NIST suggesting that he can be predicted, perhaps in the future with bigger computers?

Summary: an ounce of math wins over computers, quantum or not.

For most natural distributions of A (including samplings from a physical process like diode noise, not too much affected by conversion to digital or feedback from the state of the generator) and common rounding methods, we are able to predict future output given enough samples. A stream of zeroes is all it takes. With good likelihood that will start to match the generator's output, and keep on that way from there on, before $2^{32}$ steps, or just $2^6$ if A is rounded to integer before multiplication.

This follows from the fact that once and if $V_j$ reaches zero, it remains stuck there. And that if A is rounded to integer (either to nearest, lower, or higher) before multiplication, an iteration removes from $V_j$ as many bits of entropy as there are low-order bits at zero in the integer multiplicand that turns out to be used. This problem does not touch the original RANDU, because its multiplier is always odd.

Hereafter I consider using $V_{j+1}=65539\cdot(V_j+1)\bmod2^{31}$, which at least may avoid that issue.

Now the generator can be be fully predicted from future output, or not, depending on characteristics of A that are not explicitly stated in the question. It is entirely possible to have A such that after rounding it is always in a small set of integer values equal modulo $2^{31}$, and then A will have no influence on output.

However, for distributions of A arising from sampling a quantum phenomena similar to diode noise and not too much affected by conversion to digital or feedback from the state of the generator, the output will indeed be significantly influenced by A. Output will not be fully predictable from past output, because the multiplier is likely to vary unpredictably (for reasons explained in that other answer, for diode noise). I do not believe (or see anyone believing) that a quantum computer without a direct physical link to the particular source used for A is able to change that; at best it could improve to some degree on the advantage obtainable by a classical computer, or turn something almost predictable to totally predictable.

With the hypothesis in the previous paragraph, the generator will remain utterly distinguishable from random; but if we believe in the hypothesis of quantum physics to any degree (as overwhelmingly most physicians and engineers do), there will be some exploitable entropy in its output, so that seeding enough of that into a sound and generously dimensioned CSPRNG will yield a RNG computationally indistinguishable from random, including by the quantum computer in the question.


Why are side channel attacks such as SPA/DPA/ CPA based on the AES SubBytes routine? I have three questions about AES related to side channel attacks:

Why are side channel attacks  such as CPA  related to the non-linearity of the SubBytes routine within AES?
What is the difference between using the substitution BOX (SBOX) in a non-linear way and the combinational SBOX proposed in articles such as "Design of AES S-box using combinational logic optimization"?
Does the use of a combinational SBOX avoid side channel attacks?

The values targeted by CPA are of the type $S(p\oplus k)$ where $p$ is a plaintext and $k$ a key byte, and $S$ maps bytes bijectively to bytes. One finds the correct key $k_0$ by correlating the Hamming weight of $S(p\oplus k)$ with the power consumption, as the absolute value of the correlation is expected to be the highest for the correct key $k_0$ at the time $t_0$ when the $S$-box output is processed in the CPU.

Now assume that for a second key $k_1\ne k_0$ the values of $S(p\oplus k_0)$ and $S(p\oplus k_1)$ differ only by a single bit for all plaintext bytes $p$. Then also their Hamming weights differ only by 1, and therefore the Hamming weights of $S(p\oplus k_0)$ and $S(p\oplus k_1)$ are strongly correlated. So whenever $k_0$ gives a high correlation between current consumption and predicted Hamming weight, so does $k_1$, which makes both keys difficult to distinguish, if one wants to know, which one is the correct one.

If $S$ happens to be linear, then $S(p\oplus k_0)\oplus S(p\oplus k_1) = S(k_0\oplus k_1)$ is independent of $p$. So if $S(k_0\oplus k_1)$ has Hamming weight 1, one is exactly in the bad situation (for the attacker) of the last paragraph. For $S$ bijective linear, this occurs for $8$ different key bytes $k_1$'s.

As the $S$-boxes have to protect the crypto-algorithm against linear and differential attacks, they are chosen such that $S(x)$ and $S(x\oplus\Delta)$ are "linearly as independent as possible". In particular, also their Hamming weights have as little correlation as possible. So if you have a high correlation with $S(x)$ (think $x=p\oplus k_0$), you will not have much correlation with $S(x\oplus\Delta)$ (think $\Delta=k_0\oplus k_1$), making different key bytes easily distinguishable.

Differently phrased, real $S$-boxes fulfill the basic assumption of DPA that wrong keys give random predictions for the current consumption, whereas linear $S$-boxes violate it.

In conclusion, any $S$-box good for "classical" cryptography is bad (=good target) for side-channel attacks like CPA, and vice versa. (There are some papers published about finding $S$-boxes good for both purposes, but to my knowledge none were found yet, and I'd be surprised if there will be.)

I do not know the article you ask about, but judging from the abstract the authors are only interested in an efficient (time+space) HW-implementation of the AES S-box, and not at all in security against side-channel attacks (they would mention it).

For the security against CPA it doesn't matter how an intermediate value you try to attack was created in the HW, only if it (or something else correlated to it) shows up leaking side-channel information (like power consumption).

Trying to fight side-channel attacks without using dynamic random (dynamic = freshly generated each time the algorithm is run) I wouldn't bet on. Just take a look at how easily all white-box implementations got broken using DPA-like techniques.


How to beat a substitution cipher when adding a pseudo-random number stream? From view-source:https://web.archive.org/web/19990224060310if_/http://www.cl.cam.ac.uk:80/PGP/pgpdoc1/pgpdoc1_29.html:

  When I was in college in the early seventies, I devised what I
  believed was a brilliant encryption scheme.  A simple pseudorandom
  number stream was added to the plaintext stream to create
  ciphertext.  This would seemingly thwart any frequency analysis of
  the ciphertext, and would be uncrackable even to the most resourceful
  Government intelligence agencies.  I felt so smug about my
  achievement.  So cock-sure.

  Years later, I discovered this same scheme in several introductory
  cryptography texts and tutorial papers.  How nice.  Other
  cryptographers had thought of the same scheme.  Unfortunately, the
  scheme was presented as a simple homework assignment on how to use
  elementary cryptanalytic techniques to trivially crack it.  So much
  for my brilliant scheme.

By Philip Zimmermann, according to the about page of that same website. Emphasis mine.

The crux of it is "A simple pseudorandom number stream was added to the plaintext stream to create ciphertext." This can be read multiple ways:

it is added to the end (unlikely)
it is interjected as in "h4e7l2l5o" (also unlikely, unless he meant the numbers are turned into letters, in which case I find it somewhat unlikely)
the numbers are added to each character

The latter seems like the only sensical option to me. But as far as I know, adding (equivalent to xor, security-wise) random numbers to each position is actually secure, assuming a good source of randomness. But it sounds like the scheme is broken using "elementary cryptanalytic techniques", not the underlying RNG. And of course the RNG (which has to qualify as CSPRNG) is the crux of such an algorithm, not the way of mixing its output with the plaintext.

The only thing I can think of is that it is unauthenticated, but that's rather a flaw in bad usage and not in this primitive itself. Does anyone know what "elementary cryptanalytic techniques" Phil is talking about? He makes it sound as though any basic cryptographer should have come across it and would know what it means (and how to break it), but I don't.

Phil Zimmermann here.  Yes, it was modulo addition of bytes from the pseudorandom number generator, and subtraction at the receiver end.  Essentially a stream cipher.  The fatal weakness was that I used a linear congruential generator, seeded by the key.  As weak as an LFSR.  I knew nothing at that time about the weakness of linear generators.  It was 1973.  I was clueless.  There were no crypto courses available in the university in that era.

This was not the last time I attempted home-grown crypto algorithms.  Later, in PGP version 1.0, I developed my own block cipher design called Bassomatic, a cautionary story I have told elsewhere.  From this humiliating experience I learned to only use extensively peer-reviewed algorithms.

-prz


Entropy of Androids motion-sensor data My app on Android uses the built-in motion sensors to collect seed-data for the PRNG (java.security.SecureRandom) that is later to be used for key-generation.
The user is told to shake the device so the incoming data should be somewhat pretty random. Also, too slow movements are ignored in order to avoid getting only 0s as seed if the device was not moved during the time of "recording".

In detail: Teh length of the movement-vector is calculated ($l = sqrt(x^2 + y^2 + z^2)$) and $9.81$ is subtracted from it in order to ignore gravity.
If $l$ is less than 81% of the sensors Peek value the set of values is ignored. Otherwise the resulting values for x, y, z are beeing muliplied by $2^{28}$ (because bit-shifting is not supported on floats in Java), then XORed.
These values then fill an array like that:

dataStack[dataSetsRecorded++ % dataStack.length] ^= value;

The question is: is that a high entropy or can this be predicted (e.g. because most phone users would shake the phone up and down but not sidewise and tablet users would rather tilt than shake the device)?
Thanks :)

Read Toward Sensor-Based Random Number Generation for Mobile and IoT Devices, if it's not too late(!)

In summary, the extracted table below shows their findings.  Those were that the three accelerometers in combination provided a good 24 bits of entropy for randomness extraction.  The good bits are the black boxes in the table as per the note below it.  The team got fairly good random results from their scheme.

I'd add the proviso that they used aggregated data from 37 devices.  The results for a single device might vary...


Determine RSA modulus from encryption oracle Suppose we have an RSA encryption oracle $E(m)$ which basically just calculates $m^e \mod n$ for a given message $m$. Here $e=65537$ is known but $n$ is not. Can we determine the value of $n$ without trying all values below $n$, assuming $2^{1023}\leq n <2^{1024}$?

I thought of using $E(-1)$ but sadly only positive messages are allowed. Another idea that i had was to just use $E(2)$ and if $e$ was small it would wrap the modulus only a few times and we would be able to determine $n$. Sadly $2^{65537}$ is many times bigger than $n$ so it doesn't work either.

We have $E(x) = x^{65537} - k \cdot n$, for some integer $k$ (which will be different for different values of $x$), and the unknown modulus $n$, and hence $x^{65537} - E(x)$ will always be a multiple of $n$.

So, compute:

$$\gcd( 2^{65537} - E(2), 3^{65537} - E(3) )$$

That will be $n$ multiplied by some integer which is likely to be small...

As similar method (that doesn't involve computing on such large integers, and even works even if you don't know $e$) is to compute:

$$\gcd( E(2)^2 - E(4), E(3)^2 - E(9) )$$

How this works should be fairly obvious...


Determine the Key given ciphertexts and plaintexts? Given two sets of plaintexts and their corresponding ciphertexts, how does one determine the key $K$?

The ciphertexts are:

$$C_1= (P_1 \oplus K_0) + K_1$$

and

$$C_2= (P_2 \oplus K_0) + K_1$$

$K = K_0 || K_1$ (string of bits).

where $+$ means addition mod $2^n$.

How do we find the unknowns (eg, $K_1$)?

There is a straightforward brute force method. For example, take the lowest $8$ bits of everything and check for valid values of $K_1$ and $K_2$, mod $2^8$. You will need about $2^{16}$ checks to get the lower $8$ bits of $K_1$ and $K_2$. Proceed then to values mod $2^{16}$, as you know the lower $8$ bits of $K_1$ and $K_2$, only bits $8\dots15$ of these must be checked, the effort is $2^{16}$ again. Proceed until you get $K_1$ and $K_2$ in full.

Better, do the same but instead of $8$ bit increments do $1$ bit increments. So, brute force for values mod 2, mod $4$ ... mod $2^n$. You will need to check $4$ different values each step (one bit from $K_1$ and another from $K_2$), and do this $n$ times. Therefore, the cost of finding $K_1$ and $K_2$ is $4n$, meaning this isn't just polynomial in respect of the number of bits: it's linear.

However, must be noted that if $P_1 \equiv P_2 \pmod{2^i}$, then the first $i$ bits of $K_1$ and $K_2$ are indeterminable, so more plaintext/ciphertext pairs will be needed until finding some pair where $P_1 \not\equiv P_2 \pmod{2}$, to retrieve then the whole keys.

Update: Probably there are (for a given $n$) $2$ pairs $(K_1,K_2)$ compatible with an adequate $(P_1,P_2)$ pair, so this method should check incrementally $2$ pairs of keys.


What effect does adding noise to a substitution cipher have? Assume I assigned the letters A-Z to random numbers in the range of 0-100. The mapping of plaintext characters to ciphertext values constitutes my cipher alphabet(and key).

I encrypt a message using a normal substitution cipher. I then create a sequence of random values the same length as my initial ciphertext using numbers in the range of 0-100 that were not used in my cipher alphabet. I then randomly weave my initial cipher text and my random sequence together.

Specifically, I would start with the first ciphertext character and randomly decide wether or not to add noise. If I decide to add noise I will insert the first unused element from my random sequence either before or after the current ciphertext character (again chosen randomly). When I reach the end of the cipher text there may still be unused values from the random sequence. If there are I go back to the first character of ciphertext (which could be an encrypted value or noise added in a previous pass) and continue inserting values randomly until all of the values from the random sequence have been used.

The final result is the message that would be transmitted. If you know the key description is trivial since you can just ignore the "noise". But if you don't know the key how would you go about decrypting this? specifically what are the techniques for separating noise from meaningful data or is there some other attack scheme?

Note: I am asking because of hobbyist curiosity. I know modern encryption algorithms are secure and don't need to be meddled with. And I know the scenario I described results in a larger transmission, etc. I just want to know how you break it.

I did some simulations and found that after adding noise, the common English letters (e, a, t, r, s, etc) still stuck out like sore thumbs. Knowing which characters represent these letters, and assuming the attacker knows we added noise, makes this only trivially harder than a straight substitution attack.

But that got me thinking, what if for each letter A-Z I choose some random amount of random numbers to represent that letter. Each random sequence must be uniquely identifiable when concatenated with any other value (I don't know an easy way to generate this kind of key but its possible to construct manually if your careful). For example I could choose the following values for A, B, and C:

A: 36 52 47
B: 36
C: 95 47

Given the string "36 52 47 95 47 95 47 36 52 46 36" we can tell that it represents the characters "ACCAB", but without knowing the key, frequency analysis wouldn't work (for example B shows up once in our plaintext, but its corresponding cipher text value 36 shows up three times).

I don't know if this type of cypheralphabet has a name, but I realized that on its own, it isn't that strong. We can look at the frequency of pairs of numbers in the ciphertext and determine what numbers are more likely part of the same character representation. If you can split the numbers up correctly, then this is the same as a standard substitution cipher.

But if we add noise to this weird random character length cipher alphabet, in the same way it was originally described, then there is no way I can see to determine which groups of numbers represent single characters, and basic frequency analysis doesn't work. What am I missing?


What's the difference between Trapdoor Functions and Encryption Functions? From Wikipedia:

  A trapdoor function is a function that is easy to compute in one
  direction, yet believed to be difficult to compute in the opposite
  direction (finding its inverse) without special information, called
  the "trapdoor".

What's the difference between this and encryption functions like AES? Are all encryption functions instances of trapdoor functions? Are there any situations in cryptography were we want a trapdoor function instead of an encryption function?

Typically, trapdoor functions are used in asymmetric cryptography. For instance, if you have a RSA public key $(n,e)$, it is easy to compute a cipher text $c = Pad(m)^e\mod n$, but hard to get back to $Pad(m)$ from $c$ even if you have the public key. In order to easily reverse the operation you need the corresponding private key $d = e^{-1}\mod\phi(n)$. The reason RSA is a trapdoor function in this sense, is because it is based on the hardness of the Integer Factorization Problem. You can't calculate the private exponent $d$ unless you know $\phi(n)$, and you can't calculate $\phi(n)$ unless you know the prime factors of $n$.

AES and other symmetric ciphers are not trapdoor functions in this sense. You are only able to compute $c = AES_k(m)$ if you got the key $k$, but if you got this key it is equally easy to compute $m = AES_k^{-1}(c)$


Where does signing/decrypting take place on a YubiKey 4/5 PIV private key? I have a YubiKey 4 and want to use it to store a private key that should never enter a computer system's memory. After importing the key to the device I understand it never leaves it.  Do the signing/decryption operations that take place for plain text using the private key happen on the device's hardware? Also, if this does happen on hardware, then can it be used like an HSM if proper compliance does not require that it generate the key on the device?

From the official specifications, published by NIST;
https://csrc.nist.gov/publications/detail/sp/800-73/4/final
NIST  Special  Publication  800-73-4 Interfaces  for  Personal  Identity Verification  –  Part  1:  PIV  Card Application Namespace,  Data Model  and  Representation

A.5 Key  Establishment  Schemes  with  the PIV  Key  Management  Key
FIPS  201  specifies a public key pair  and associated  X.509  Certificate for  Key Management. The  key management  key  (KMK)  is further  defined  in  SP  800-78, which  defines two  distinct  key establishment schemes for  the KMK:
A.5.1.1  RSA  Key  Transport  with the PIV  KMK
As specified  in  SP  800-78,  the on-card private KMK can  be an  RSA transport  key that complies  with [PKCS1].  In  the scenario  described  above,  a sender  encrypts a symmetric key  with  the KMK’s  public RSA transport key.  The  role  of  the  on-card  KMK private RSA transport  key  is to  decrypt  the sender’s symmetric  key on  behalf  of  the  cardholder  and provide  it  to the  client  application  cryptographic  module

The client application cryptographic module would typically mean the software on the computer that you connected the card to. It means that RSA operations happens on the card, but the computer will then decrypt the full message. It's designed this way to not make the card a bottleneck for large messages.
The Yubikey mostly follows the official spec for these protocols.


Time complexity of trial division Suppose $n=pq$, where $p,q$ are prime numbers.
Let $p ( \le q)$ be the smallest prime, then we know that $p \le \sqrt{n}$.
In trail division, we check  $n \mod i$  for the values of $i$ from 2 to $\sqrt{n}$, to find the value of $p$ and then we calculate $\dfrac{n}{p}$ to get $q$.
In general, the time complexity is (assuming finding remainder and division takes place in constant time) $\sqrt{n}$.
How to calculate cryptographic time complexity?
Suppose $b$ is the number of bits to represent $n$ in binary format, then can I directly substitute in $\sqrt{n}$, so that I can get $2^{\frac{b}{2}}$.
Or should it be calculated as $(\sqrt{n}-1)*$ time taken for modulo operation $+$ time taken for division?
How to arrive at time complexity in terms of $b$?
How much time does it take for calculating modulo and division in terms of bits? If we substitute those values, finally should we get $2^{\frac{b}{2}}$?

Your assumption "(assuming finding remainder and division takes place in constant time)" is not fulfilled here. We are dealing with big numbers and division complexity is some function M(b) where M is the complexity of your multiplication algorithm, e.g., Schönhage-Strassen with O(b log b log log b). Schoolbook division is of order b².

Note that for cryptographic purposes n is really huge; even a polynomial time algorithm in n (exponential in b) is not feasible here.

EDIT: A note on complexity computation: Only leading terms in a sum are relevant, lower order terms are always negligible. When you complexity is already exponential, you can neglect polynomial factors. Therefore the complexity of division is just mentioned to make clear that your assumptions did not hold in the first place, it turns out to be negligible in the course of the argument.

NOTE: This all assumes a classical computer as model of computation. With a quantum computer, you can factorize an integer in polynomial time using Shor's algorithm. Current published Quantum Computers have 14 QBits and can factorise the integer 15 (fifteen). Apply Moore's law and some leeway for non-published Quantum Computers and you have an estimate when this kind of cryptography will be broken.


Crypto++ benchmarks cycles/byte vs. megacycles/operation With respect to Crypto++ benchmarks: https://www.cryptopp.com/benchmarks.html

Why is it that there are different metrics collected for block ciphers(i.e. cycles/byte) than for public key cryptosystems(i.e. megacycle/operation)?

Why can't the RSA operations be benchmarked by using cycles/byte as well?

The reason for this is that RSA and other asymmetric operations are not used for bulk encryption (or bulk signature generation, if such a term exists).

If a lot of data needs to be signed/verified or encrypted/decrypted then a hybrid cryptosystem will be used instead.

In the case of signature generation / verification most if not all of the plaintext will be hashed by a secure hash algorithm. This hash value will be used as input for signature generation or verification using the asymmetric keys.

For encryption a symmetric cipher will be used. The symmetric key will be wrapped / unwrapped or derived using the asymmetric keys.

So you'd use just a single operation when it comes to asymmetric primitives such as RSA for most operations.

If hybrid encryption is used you'd use a single operation for the asymmetric primitive and then add the amount of time required to hash or encrypt the amount of data.


Convert numeric value of RSA key to a .key file After reading about RSA encryption in wikipedia I managed to create two number, a number d which is the private number, and a number n which is the public number.

But when I tried to use these keys to encrypt and decrypt php seems to prefer functions such as openssl_public_encrypt and libraries like phpseclib which seem to need a .key file or a .pem file or a .cem file... Which when I views them looked nothing like a number.

I'm a beginner and I do this kind of stuff because it fascinates me a lot.

So why don't they look like numbers?And how can I convert my numeric value a key to such a value?

In general an RSA private key consists of at least d and n, but this century it is usually stored with added CRT (Chinese Remainder Theorem) parameters as described in Wikipedia and specified more exactly in PKCS1 (Public Key Cryptography Standard 1) which was actually issued by the company RSA (later acquired by EMC and then Dell) but is more conveniently and stably available as several Internet RFCs, currently 8017 at 3.2.

(Native) phpseclib supports several formats for key files.

The first two are de-facto defined by OpenSSL, a widely used open source implementation since about 1995 (originally as SSLeay) of SSL/TLS protocols including the cryptography for those protocols including RSA.

A plain (unencrypted) PEM file simply consists of the PKCS1 RSAPrivateKey structure encoded in ASN.1 DER or BER converted to base64 and wrapped to lines shorter than 80 chars, with delimiter lines -----BEGIN RSA PRIVATE KEY----- and -----END RSA PRIVATE KEY---- added.

An encrypted PEM file consists of the same PKCS1 ASN.1 encoding first encrypted with Password-Based Encryption, then PEMized similarly: base64 plus BEGIN/END lines but adding some RFC822-style headers defining the encryption. This is documented in the man page for the function PEM_write_RSAPrivateKey also on the web for the current release.

The PuTTY format is also Password-Based Encrypted, with encodings of the public and private parts separated in a format defined by PuTTY, an implementation of SSH protocol which like SSL/TLS includes RSA. AFAICT it is not documented, but PuTTY is open source and the source file sshpubk.c effectively defines this format.

The XMLSig/XMLenc format is defined by public standards and using (unsurprisingly) XML. This might be best for your purpose, since it simply contains the various numbers as base64 of canonical big-endian, tagged using XML.

The OpenSSL binding isn't clearly specified but presumably supports the PEM formats supported by OpenSSL; in addition to the two PKCS1 formats described above, this includes plain and encrypted formats defined by PKCS8 which is basically an ASN.1 wrapper around PKCS1, optionally with Password-Based Encryption, similarly available as RFC 5208 optionally combined with PKCS5 and sometimes PKCS12.


How can CKA_TRUSTED be set to true? I'm confused by the wording of the PKCS#11 v2.40 specification in terms of when CKA_TRUSTED can be set to true on a public key certificate object:

  The CKA_TRUSTED attribute cannot be set to CK_TRUE by an application. It MUST be set by a token
  initialization application or by the token’s SO. Trusted certificates cannot be modified.

I'm trying to reconcile "cannot be set to CK_TRUE by an application" and "It MUST be set [...] by the token's SO".  Does this mean a R/W SO session can create (or update) a Public Key Certificate Object (e.g. CKC_WTLS) with CKA_TRUSTED set to CK_TRUE?  I feel this doesn't jive well with "cannot be set [...] by an application".

In general an application - a program that uses the token for cryptographic operations - is supposed to use CKU_USER, not CKU_SO.

The CKU_SO is supposed to be used by the security officer. Of course, the only way that the SO can generally communicate with the token is through some kind of management application - sometimes combined with an authentication device such as an external PIN pad connected to an HSM. And yes, usually it is possible to write a management application yourself; it is of course dubious at best to mix that into an application that uses the key material stored within the token (especially if you also integrate the login credentials).

And yes, the SO can generally set trust on certificates. The SO is responsible for making sure that they can be trusted after all.

There can be tokens where the trust cannot be set at all. For instance smart cards may have a specific PKCS#11 interface where no management operations are applicable whatsoever.


Is there an example of a “robust, yet not private” SMC protocol? I have been trying to understand the interplay between robustness and privacy of an SMC protocol. It is easy to come up with a protocol that is private but not robust.

Can someone provide an example of a secure multiparty computation protocol that is not private but is robust, under some threshold $t$ corrupt parties?

Sure.
Parties:  more than 1
Input:  each party has a secret input
Output:  empty string

"Protocol":  Each party broadcasts their secret input then outputs the empty string.

That is robust for arbitrary thresholds, but is

not private against even a single semi-honest adversary.


What SALT value will be used in HKDF_EXTRACT in TLS1.3? What SALT value will be used in HKDF_EXTRACT while generating the Handshake Secret (when there will not be any PSK)?

The relevant text at the end of section 7.1 that explains this is:

  If a [PSK or ECDHE] secret is not available, then the 0-value consisting of a string of Hash.length bytes set to zeros is used.  Note that this does not mean skipping rounds, so if PSK is not in use, Early Secret will still be HKDF-Extract(0, 0).

This means that when a PSK is not used, the first step in key derivation is to compute the Early Secret (which is a fixed value that depends only on the selected HKDF hash function).

Following the main flow chart in section 7.1, feed Early Secret through Derive-Secret once, and the result is the salt argument for HKDF-Expand for the Handshake Secret calculation.

early_secret_no_psk_sha256 = "33ad0a1c607ec03b09e6cd9893680ce210adf300aa1f2660e1b22e10f170f92a"

And finally the HKDF-Expand salt for Handshake Secret is obtained when you invoke Derive-Secret(., "derived", "") on the Early Secret. For SHA-256, you end up with:

handshake_secret_salt_no_psk_sha256 = "6f2615a108c702c5678f54fc9dbab69716c076189c48250cebeac3576c3611ba"

Since these values contain no entropy, you don't need to compute them every time (again, assuming a PSK is not used). These values can be derived by anyone from the RFC text and depend only on the selected HKDF hash function.


Are asymptotic lower bounds relevant to cryptography? An asymptotic lower bound such as exponential-hardness is generally thought to imply that a problem is "inherently difficult". Encryption that is "inherently difficult" to break is thought to be secure.

However, an asymptotic lower bound does not rule out the possibility that a huge but finite class of problem instances are easy (eg. all instances with size less than $10^{1000}$).

Is there any reason to think that cryptography being based on asymptotic lower bounds would confer any particular level of security? Do security experts consider such possibilities, or are they simply ignored?

An example is the use of trap-door functions based on the decomposition of large numbers into their prime factors. This was at one point thought to be inherently difficult (I think that exponential was the conjecture) but now many believe that there may be a polynomial algorithm (as there is for primality testing). No one seems to care very much about the lack of an exponential lower bound.

I believe that other trap door functions have been proposed that are thought to be NP-hard (see related question), and some may even have a proven lower bound. My question is more fundamental: does it matter what the asymptotic lower bound is? If not, is the practical security of any cryptographic code at all related to any asymptotic complexity result?

Just because a lower bound has been shown does not necessarily make the problem good for crypto. For example, approximation algorithms or probabilistic algorithms could be used to break the system.

That said, I would imagine that a lower-bound could strengthen the argument for a particular system. So, it would seem that a lower bound is neither necessary nor sufficient, but would have it's benefits.


What is meant by a "short" vector in cryptography? I was trying to understand Learning with Errors for Lattice-based Cryptography and I came across this.

  The learning with errors problem is: Given an $m \times n$ matrix $A$ and a vector $b \equiv As + e \pmod q$, where $e \in \mathbb{Z}^m_Q$ is a "short" error vector, to compute $s \in \mathbb{Z}^n_q$.

Can somebody explain what does a "short" vector in this context means ?

Short just means small (in terms of some metric, usually Euclidean).

You can see that if $e$ is the zero vector, $s$ becomes trivial to recover, using Gaussian elimination. If $e$ is uniformly random, then you can imagine that it is impossible to recover any information on $s$, since it is hidden against a uniformly random backdrop.

If you're familiar with lattices, it might be helpful to picture the following instead. Consider the LWE lattice

$ \mathcal{L} := \{ \mathbf{A} \mathbf{s} : \mathbf{s} \in \mathbb{Z}^n_q \} + q \mathbb{Z}^m .$

If the vector $e$ is small enough, $b$ is close to only one of the points in this lattice. In other words, the LWE problem becomes a bounded-distance decoding problem on this lattice. If $e$ is too large, $b$ might be closer to another vector in this lattice.

Since we are typically interested in recovering $s$ and not a set of possible secrets, we must be given a guarantee that $e$ is sufficiently short (hence bounded distance decoding).

So "short" just means that $s$ is recoverable. Usually, $e$ is sampled from a discrete distribution approximating a Gaussian centered around 0, with width small relative to $q$. This allows one to ensure that $s$ is recoverable with an arbitrarily high probability, while still making the problem as difficult as possible.


How do I attack an RSA setup where e is even? As a challenge, we were shown an RSA setup where we have a big $n$ (617 decimal digits), $e=4$, and asked to recover three messages. (However, the messages are padded to the same length as the key with random bytes.)

I don't have a very strong background in cryptography, and this is apparently so poor that nobody bothered to explain how you'd wreck it. For instance, I've been reading the Wikipedia article on Coppersmith's attack, and it reads:

  [e=3, 17 or 65537] are chosen because they make the modular exponentiation operation faster. Also, having chosen such e, it is simpler to test whether $gcd(e, p-1)=1$ and $gcd(e, q-1)=1$ while generating and testing the primes in step 1 of the key generation.

I'm not super good at this, but given that $e$ is even, I'm pretty sure that it can't be coprime with $p-1$ or $q-1$.

How would I go around to crack it?

EDIT: as some of you have guessed, this was not RSA. Instead, the single number $p$ was a ~2048 bits prime. The crypted message was essentially $pad(m)^4 \mod p$, which could be deciphered using the modular square root twice.

Unless they did something wrong (either accidentally, or deliberately to make it easy), there is no practical way.

It's well known that, if you're able to compute the squareroot of an arbitrary number modulo a composite, you can efficiently factor that composite.  And, solving $e=4$ is equivalent for solving the RSA problem twice with $e=2$.

Now, it's possible that they somehow made it feasible for you, such as:

Selecting a prime $N$, or one that is easy to factor
Selecting a tiny message (however, you did indicate that they didn't do that)

As for why we generally select $e$ relatively prime to $p-1$ and $q-1$, well, that's not actually to make things more difficult for the attacker.  Instead, it's so that the legitimate decryptor (that is, the guy with the private key) can uniquely determine the original message.

After all, we have $M^4 = (N-M)^4 \bmod N$ for all messages $M$; hence if the decryptor got the value $M^e \bmod N$, he would have not inherent way to determine if $M$ or $N-M$ was the original message.

However, that doesn't help you.


How to prove that two EC public keys created with two different generators share the same secret key? Consider a situation where there is a (scalar) secret key $x$, known only to Alice.

There are two well known generator points $G$ and $H$, known to both Alice and Bob. $H$ is chosen such that discrete log of $H$ base $G$ is unknowable.

Alice provides Bob with the points $A$ and $B$, where $A = xG$ and $B = xH$.

Without Alice revealing $x$ to Bob, how can Alice prove to Bob that both $A$ and $B$ were constructed with the same $x$? The proof should be non-interactive.

Is it safe to simply provide a Schnorr signature using the private key $x$ and public key $(A+B)$ on the basis of a generator point $(G+H)$?

The Schnorr signature would be:

$sig.c = Hs( (A+B)$  $||$  $k(G+H))$

$sig.r = k - x * sig.c$

where $k$ is a random number generated only for this Schnorr signature.

The Schnorr signature would be verified by checking that:

$sig.c == Hs((A+B) $ $||$ $ (sig.r*(G+H) + sig.c*(A+B)))$

$Hs()$ means hash the contents to produce a scalar

$||$ means byte concatenation.

Is it safe to simply provide a Schnorr signature

Actually, a single Schnorr signature is insufficient.  For your proposal, someone could pick an arbitrary $A$ and compute $B = x(G+H)-A$ (for some $x$ he picks), and he could generate the signature.

I will also assume that the order of the subgroup that $G, H$ generate is prime (which is usually the case)

Instead, you can use three signatures:

One is sig.c = Hs(A || kG), sig.r = k - x * sig.c; this shows that we know a solution $x$ to $A = xG$
Next is sig.c' = Hs(B || k'H), sig.r' = k' - x * sig.c'; this shows that we know a solution $y$ to $B = yH$
Third is sig.c" = Hs((A+B) || k"(G+H)), sig.r" = k" - x * sig.c"; this shows that we know a solution $z$ to $A+B = z(G+H)$

[Don't forget to use three different $k$ values for the three signatures]

It is easy to show that if we know solutions to the above three with $x \ne y$, then we can rederive the discrete log of $H$ wrt $G$.  We assumed that we don't know that, and hence we have $x=y$ (which is what we are trying to prove)


What would a backdoor in symmetric key cipher look like? Pretty much what the title says. DES was suspected of having one, but I couldn't imagine what it could possibly look like if only the NSA knew how to use it. Dual_EC_DRBG's backdoor is asymmetric, but it's not a cipher. Could one have a kletographic symmetric key cipher?

As usual, inserting a backdoor in a symmetric cipher becomes a lot easier if you have knowledge your adversaries lack.

DES is a pretty good (counter)example of how a backdoor could be introduced in a symmetric cipher.

Back in 1974, IBM and the NSA both knew about differential cryptanalysis, but they did not publish their findings. Some 16 years later, differential cryptanalysis was rediscovered and published by Biham and Shamir. As they found out, DES's S-boxes – which are precisely the part of DES prople suspected to contain a backdoor – were surprisingly resistent to differential cryptanalysis.

As it turned out, the S-boxes were designed to to repel this type of attack. In theory, since the NSA knew about differential cryptanalysis but the general public didn't, they could have chosen S-boxes that were exceptionally vulnerable to it. That would have been a backdoor.

Another example would be the use of apparent trapdoor functions with a known inverse.

To see how this could be exploited, suppose nobody knew about RSA. Define $R(X)$ as the RSA encryption of $X$ with a certain public key and design a cipher that generates the stream $$R(1\times K) || R(2\times K) || R(3\times K) || \cdots$$ where $K$ is the secret key for your stream cipher.

If you know the associated private key, you can easily compute $R^{-1}$. Now, if you know enough plain- and ciphertext to figure out part of the stream – let's say $R(1\times K)$ – all you have to do is apply $R^{-1}$ to figure out $K$.

Nobody will be able detect the vulnerability without essentially discovering RSA.


How can I make sure non-open source programs are really using end-to-end encryption? Without going deep into math, is there a way to make sure that non-open source programs like WhatsApp, FaceTime, Zoom, etc. are really using end-to-end encryption instead of just 'regular encryption' (i.e. the server has the cryptographic keys)?

Is there's a way to make sure that non-open source programs are really using end-to-end encryption?

Only by deep reverse-engineering. Which is hard, and might be illegal. Plus the apps are a moving target: they change like weekly. And, using end-to-end encryption is not proof that no interception is possible: this encryption (or its key generation) could be weak, accidentally, deliberately, perhaps surreptitiously. In the end, there's no practical way¹.

True story: I was the lead engineer for this² modem capable of end-to-end encryption with negotiation of session keys using Smart Cards, released in 1990, sold in France with some success. A director of our company insisted that we get approval from the authorities for these features, because that was raised in a conversation with Apple France, our main distributor. Soon after (mid 1991) I had a guy introducing himself with a military rank in my office, explaining that the law required that for crypto devices sold to the general public, there must be a way to find the key with a test requiring at most 240 steps. He required a detailed description of the protocol. I argued that changing it would break interoperability. The guy proposed addition of a side channel leaking the session key, so that if one end was using the rigged device, the session key would be available for one intercepting the line signal and knowing the method. I had the distinct impression this was standard procedure. In the end, I created a new packet type that older devices ignored, containing the session key RSA-encrypted, sent at moreless regular intervals, and new models did that. I remember the guy came for a demo. I insisted not to know the production private key, for my own safety. I still have the source code for that device, in 8051 assembly.

Note: the main feature of that device's point to point crypto was that, when you had made a set of Smart Cards, and inserted one in your modem, you could be confident that only someone holding another Smart Card from the set could connect. This feature was not compromised, as French law did not ask.

¹ No practical way to be confident that there is effective end-to-end encryption. It's sometime possible to prove that there is no end-to-end encryption. For example, if data goes thru a central server thru a https link protected using a server certificate, and the user messages are revealed by breaking that https encryption using a local proxy (a standard hack on one's device), then we are sure there is no end-to-end encryption.

² Scroll down and click on the wide picture or right arrow for more, including internals.I have no connection with this website.


Why we need ECDSA when we have ECDH? ECDSA and ECDH give us the following methods:

// ECDSA
var signature = ECDSA.sign(privateKey, hash);
var isValid = ECDSA.verify(publicKey, hash, signature);

// ECDH
var sharedSecret1 = ECDH.compute(node1.publicKey, node2.privateKey);
var sharedSecret2 = ECDH.compute(node2.publicKey, node1.privateKey);
// sharedSecret1 == sharedSecret2;

ECDSA give as a very long signature (73 bytes).

I am wondering why we need ECDSA if we can do signing only with ECDH and get much smaller signature:

function sign(priavteKey, hash) {
  // generate public key from private key
  var publicKey = computePublicKey(hash);
  var sharedSecret = ECDH.compute(publicKey, privateKey);
  var signature = hash(sharedSecret);
  return signature;
}

function verify(publicKey, hash, signature) {
  var sharedSecret = ECDH.compute(publicKey, hash);
  return (hash(sharedSecret) == signature);
}

This method exposes one of the private keys of ECDH and uses it for generating the signature hash. Is there any way that this method can expose the real private key?

I've been reading these answers and it seems ok…

To simplify your definition:

$$
s = \operatorname{sign}(k, m) = h(G\ h(m)\ k)\\
\operatorname{verify}(Gk, m, s)\iff s \overset{?}{=} h(Gk\ h(m))
$$

This is obviously insecure because I can forge "signatures"!

$$s' = \operatorname{forge}(Gk, m') = h(Gk\ h(m'))$$

ECDH is not a signature scheme. Schnorr is amazing and is much more interesting than ECDSA! Including but not limited to: threshold k-of-n distributed identities, n-of-n multisig aggregation, batch verification, public key recovery, implicit certificates, and much more!


weakness of a DES enhancement The following key enhancement to DES was proposed in order to increase the complexity of finding the keys by exhaustive search.

$$\text{DES}^V_{k,k_1}(M)=\text{DES}_k(M)\oplus k_1$$

where the keys’ lengths are $|k|=56$ and $|k_1|=64$ ($k_1$ has the same length as the block length). Show that this proposal do not increase the complexity of breaking the crypto-system using brute-force key search. That is, show how to break these schemes using on the order of $2^{56}\ \text{DES}$ encryptions/decryptions.

You may assume that you have a moderate number of
plaintext-ciphertext pairs, $C_i=\text{DES}^V_{k,k_1}(M_i)$.

Let $r$ be the number of pairs indexed from $1$ to $r$.

I define $\forall\ l\in\{0,1\}^{56},\ i\in\{1,\dots,r\}:\text{K}(l,i) = \text{DES}_l(M_i)\oplus C_i$.

My proposal for an adversary is:

for every l of size 56:
     for i = 1,...,n:
          compute K(l, i)
     if for all i != j : K(l,i) == K(l,j)
          return <l,K(l,1)> as the keys of the cryptosystem

It is true that if in some iteration $l=k$ before returning, all the $\text{K}(l,i)$ will be equal to $k_1$ (from the definition of the new crypto-system), so we will return $k,k_1$ as the keys.

But, I think that it is possible that for some $l\neq k$ the $\text{if}$ in the second $\text{for}$ loop will be satisfied since we are checking only a small amount of messages. In such a case if we meet $l$ before meeting $k$ the return of the algorithm will be false.

question

Is it possible to break the crypto-system deterministically with the given complexity, or we must allow  some error probability?

Is it possible to break the crypto-system deterministically with the given complexity, or we must allow some error probability?

If we model DES as a random permutation, there is always some probability of either deriving the wrong key, or finding multiple ones.

If we have $n$ plaintext/ciphertext pairs, there is a nonzero probability that there exists a second spurious key that just happens to map each plaintext to the corresponding ciphertext.  If our brute force search stops at the first key it finds, it might stop at the wrong one.  If our brute force search keeps on going after the first key it finds, it'll find the second one (and hence report multiple).

Now, the actual probability of this happening is tiny; if $n=2$, then the probability in your example would be about $2^{-8}$ (which is small, but not neglicable), however if $n=3$ (which the term "moderate" would appear that we have at least this many), the probability drops to about $2^{-72}$.

In addition, attackers typically aren't that concerned about a small probability of failure.  When we protect data, we want to succeed (in this case, be secure) with overwhelming probability; but that's not the case for the attacker...


Equal sign with a "c" I am not sure whether this is common sense, but I really don't know what this $c$ means in an equivalent sign, from Lindell's How to Simulate It:

$$\big\{(S_1(1^n, x, f_1(x,y)), f(x,y))\big\}\stackrel{c}{\equiv}
\big\{(\mathsf{view}^\pi_1(x,y,n),\mathsf{output}^\pi(x,y,n))\big\}_{x,y,n}$$
$$\big\{(S_2(1^n, x, f_2(x,y)), f(x,y))\big\}\stackrel{c}{\equiv}
\big\{(\mathsf{view}^\pi_2(x,y,n),\mathsf{output}^\pi(x,y,n))\big\}_{x,y,n}$$

To quote the paper

  Two probability ensembles... are said to be computationally indistinguishable, denoted $X\stackrel{c}{\equiv}Y$, if...

This is found in section 2.


Gaussian distribution in lattices In many lattice based cryptosystems, Gaussian distribution is used. Can you explain why only Gaussian distribution is preferred?

Most lattice based encryption and/or key-exchange algorithms are based on the LWE or Ring-LWE problems. Typically, their security is shown using a reduction to an average-case instance of the (Ring-)LWE problem.

As pg1989 commented, Regev proved a very important hardness theorem for LWE in 2005. Essentially it's a quantum, polynomial-time reduction using an oracle for LWE to solve the approximate SIVP problem (given a lattice, find a full-rank set of lattice vectors where the longest such vector is nearly as short as possible). This is very useful, because it is a worst-case hardness guarantee: as long as some SIVP instances are hard, then a random LWE instance is also hard.

A similar quantum worst-case hardness theorem exists for Ring-LWE to approximate Ideal-SVP (given an ideal lattice, find a vector nearly as short as possible). Note that classical reductions exist as well (at least for LWE), but with some extra restrictions on the parameters.

Both these problems have been intensively studied and appear to be intractable for reasonable approximation factors. IE, you can find exponential approximation factor solutions in polynomial time, or find polynomial approximation factor solutions in exponential time. Quantum algorithm attempts don't fare much better.

Now to answer your question: why are (discrete) Gaussian distributions used? Because (discretized) Gaussian error distributions are assumed in the worst-case hardness theorems that are essential to the security of (Ring-)LWE.

I don't really know if similar theorems are known/possible using other error distributions. My best guess is that the Gaussian nature of the error distribution is essential to the reduction.


Multiple Hash Functions that work in either nesting Are there any hashing functions that, if two are used in conjunction (with the same salts) will return the same response regardless of ordering?

I.e. are there hash-functions $H_1$, $H_2$ such that for all suitable salts $s_1$, $s_2$ and all passwords $x$ we have

$$  H_1(s_1, H_2(s_2, x)) = H_2(s_2, H_1(s_1, x)) $$

[Take 4.2, back to requiring only the PRP to be secret]

Improving on the line of thought in that other answer, we will craft two efficiently computable functions $H_1$ and $H_2$ each accepting two arbitrary strings as input, with output a fixed-size string, say 512 bit; and (I conjecture) indistinguishable from a random function (under the assumption that some parameters are secret) except for this superset of the desired property:
$$\forall(i,j)\in\{1,2\}^2,\forall(s_1,s_2,x), H_i(s_1,H_j(s_2,x))=H_j(s_2,H_i(s_1,x))$$

We'll use as building blocks three 512-bit PRFs $P_0()$, $P_1()$ and $P_2()$ accepting an arbitrary bit string as input, and one 512-bit PRP $E()$ with $D()$ its reverse function, such that $D(E(a))=a$.We can build the PRFs as $P(m)=\mathtt{HMAC}_\mathtt{SHA512}(k,m)$ and three arbitrary distinct $k$. And by this famous result we can build the PRP as the four-rounds Feistel cipher with round functions $\mathtt{HMAC}_\mathtt{SHA256}(k,m)$ and four arbitrary distinct $k$.

For $i\in\{1,2\}$, define $H_i(s,x)$ as
$$H_i(s,x)=E\big(\text{ }D(P_i(s))+D(x)\bmod{2^{512}}\text{ }\big)\text{ when }x\text{ is a 512-bit string,}$$
$$H_i(s,x)=E\big(\text{ }D(P_i(s))+P_0(x)\bmod{2^{512}}\text{ }\big)\text{ otherwise.}$$Notice that in the above, $P_0(x)$ is now added without going through $D$; this avoid that knowledge of $P_0$ would allows creating collisions of the form $H_i(s,P_0(x))=H_i(s,x)$

The desired property $H_i(s_1,H_j(s_2,x))=H_j(s_2,H_i(s_1,x))$ follows from commutativity and associativity of addition in $\mathbb Z_{2^{512}}$, and the $H_i$ functions appears much like random oracles, except for consequences of that property, to an adversary ignoring the PRP (but possibly knowing the PRFs).

By querying the functions/oracles $H_i$, it seems impossible to internally add 0, or otherwise create collisions, other than by chance. Computing $H_1(s,H_1(s,\cdots H_1(s,H_1(s,x))\cdots))$, where $x$ is a 512-bit string and there are $2^n$ iterations, has odds only $2^{n-511-k}$ to return to $x$; if we had used XOR instead of modular addition, we'd have $H_1(s,H_1(s,x))=x$.

Note: to an adversary knowing the PRP and PRF, the problem of finding collisions on $H_1$ unrelated to the property is tractable: it is a knapsack problem in $\mathbb Z_{2^{512}}$ with unlimited supply of random values to choose from.

Open problems:

Can this be proven secure (e.g. collision-resistant except per application of the required property); or broken?
Can we make a scheme secure yet fully public?
We do not need a full group operation (on the contrary, the neutral element and existence of an opposite are a risk), any commutative semi-group will do; is something more suitable than $\mathbb Z_{2^{512}}$?
Is $H_i(s_1,H_j(s_2,x))=H_j(s_2,H_i(s_1,x))$ a consequence of $H_1(s_1,H_2(s_2,x)) = H_2(s_2,H_1(s_1,x))$?
If not, can we make a construction with only the originally asked property?


Where is the proof of security of Diffie's cipher? There is an apparently provably secure cipher that was proposed by Diffie, but enhanced by R.A. Rueppel. The scheme, which was mentioned in Applied Cryptography, works like this:

Measure the length of the plain-text, $n$.
Multiply it by $128$.
Generate this much ($128·n$ bytes of) real random data and split it out into 128
byte-arrays of length each equal to the plain-text. This can be thought as a two
dimensional array:

One of the indices gives the sequence number ($0\dots 127$).
One of the indices gives the position in the sequence, $0 \dots n-1$.

Use a 128-bit key to choose which of these streams to XOR together. Each bit of the key corresponds to "yes/no" on whether to use particular sequence. All the selected sequences are XORed together to make a single keystream, $K$.
Compute $P \oplus K$ to give the cipher-text $C$.
Serialize the two dimensional array and append it to the cipher text.
Send the whole package to Bob, who can then decrypt by de-serializing the matrix
and selecting the same rows.

Apparently, this scheme is completely secure. The attacker has to examine every possible combination of sequences ($2^{127}$ on average) in order to break the encryption scheme.

What is the proof of this? I can't find the paper that discusses this anywhere.

This looks totally weak. If you know 128 bits of known plaintext, you can infer the corresponding 128 bits of keystream. The keystream being the multiplication of the random matrix by the key (in the vector space $\mathbb{F}_2^{128}$), the key is then revealed through a basic matrix inversion.


Is there a way to confirm that a homomorphic division (multiplication with inverse) using ElGamal produced the correct result? By running some tests I observed that if I perform a homomorphic division (multiplication with the multiplicative inverse) between two values using the ElGamal scheme, I get the correct result when the division produces a whole number.
For example, D(E(10) / E(2)) = 5 which is the expected result (here "/" denotes division applied homomorphically).
But if I try D(E(10) / E(3)) the result is a very large positive or negative number.
This might be expected since, I think, ElGamal supports homomorphic division only when the dividend is divisible by the divisor. My question is given only the decrypted result of such operation, is there a way to know whether the division "succeeded" in the sense that it is the result of a division where the dividend is divisible by the divisor?

I've included some discussion in general, but "El Gamal" here is a red herring. Your confusion is with the difference between "division" in $\mathbb{R}$, and "division" in $\mathbb{F}_p$. I discuss this more in detail at the end.

El Gamal's ciphertexts are of the form:
$$\mathsf{Enc}_{g, h}(m) = (g^y, mh^y)$$
Note that $h = g^x$, where $x$ is the secret key.
This admits a (multiplicative) homomorphism, as you mention:
$$\mathsf{Enc}_{g, h}(m_1)\ast \mathsf{Enc}_{g, h}(m_2) = (g^{y_1+y_2}, m_1m_2 h^{y_1+y_2})$$
I believe your confusion stems from confusion over what $m_1m_2h^{y_1+y_2}$ means.
Like many cryptosystems, El Gamal is defined over what is known as a "finite field" (in particular $\mathbb{Z}/p\mathbb{Z}\cong\mathbb{F}_p$). This is a number system that allows you to add, subtract, multiply, and divide (just like with $\mathbb{R}$), but the operations are somehwat different than you are used to. Fix $p = 5$ (although any prime number works). Then addition is defined "mod 5", so:
$$3 + 3\bmod 5 \equiv 6\bmod 5\equiv 1\bmod 5$$
So in this number system, $3 + 3 = 1$.
Multiplication is similarly defined "mod 5".
So:
$$3 \times 3\bmod 5 \equiv 9\bmod 5 \equiv 4\bmod 5$$
So $3\times 3 = 4$ in this number system.
What does "division" mean in this number system?
Well, one can show that for any (non-zero) $x\in\mathbb{Z}/p\mathbb{Z}$, there is a unique $y$ such that $xy \equiv 1\bmod p$.
Over $\mathbb{R}$ this is true as well (instead with the equation $xy = 1$) --- if $x = 2$, then $y = 1/2$.
But in $\mathbb{Z}/5\mathbb{Z}$, if we have that $x = 2$, then $y = 3$ means that $xy\bmod 5\equiv 6\bmod 5\equiv 1\bmod 5$.
So, in $\mathbb{Z}/5\mathbb{Z}$, we have that $2^{-1} = 1/2\equiv 3\bmod p$.
This is now when we get to your point --- if we have $x,y\in\mathbb{Z}/p\mathbb{Z}$, then $xy/y\equiv xyy^{-1}\equiv x\bmod p$, so "when $y$ divides $xy$, division is like you would expect over $\mathbb{R}$".
But the situation can be more complicated in general.


Question about the Proof of "Pseudorandom generators imply one-way functions" in "Foundations of Cryptography" In "Foundations of Cryptography, Volume 1" by Oded Goldreich, chapter 3.3.6 states the following theorem:

  Let $G$ be a pseudorandom generator with expansion factor $l(n) = 2n$. Then the function $f\colon \{0,1\}^* \to \{0,1\}^*$ defined by letting $f(x,y) \stackrel{\text{def}}= G(x)$, for every $|x| = |y|$ is a strongly one-way function.

The theorem is proved by reduction, with given an inverter $A$ construct the following distinguisher $D$:
$$D(\alpha) = 1 \quad\text{iff}\quad f(A(\alpha)) = \alpha$$
 (where $D$ distinguishes between $U_{2n}$ and $G(U_n)$). There is one part of the proof I do not understand:

  [...] by $f$'s construction, at most $2^n$ different $2n$-bit-long strings (i.e., those in the support of $G(U_n)$) have pre-images under $f$. Hence $\Pr[D(U_{2n}) = 1] = \Pr[f(A(U_{2n})) = U_{2n}] \leq 2^{-n}$.

Why don't all $2^{2n}$ possible $2n$-bit-long strings have preimages under $f$?

Let $n\in \mathbb{N}$, and fix $x,y \in \{0,1\}^n$, $f(x,y)=G(x) \in \{0,1\}^{2n}$. By $f$'s definition, $$\forall x,y_1,y_2 \in \{0,1\}^n,\;f(x,y_1)=f(x,y_2).$$
Hence, if we define the function $f'\colon\{0,1\}^n\to \{0,1\}^{2n}$ by $f'(x)=f(x,0^n)$ we get that $\operatorname{Im}(f)=\operatorname{Im}(f')$ and $\lvert\operatorname{Im}(f')\rvert\le \lvert\{0,1\}^n\rvert=2^n$.


How is de-synchronisation of HOTP solved? From RFC 4226 I understand how HOTP generates one-time passwords by incrementing a counter and uses the 'look-ahead' window to try to resynchronise (from this counter), if the user tries a few wrong passwords.

Say the user leaves their token with their cat, which decides to generate 200 passwords while rolling around with it. This would likely desynchronise the system such that the user will not be able to login in, even with the look-ahead.

I assume the user would need assistance to reset the system, but what are the actual steps to doing this?

Additionally, what would be a good number for the parameter w? 10? 50? 100?

The usual resynchronization method involves getting several consecutive codes from the token and then running the algorithm once with a very large look-ahead window until the set of consecutive codes are found. The number of consecutive codes needed depends on how far off the token is.

With a typical token, two codes would suffice to handle a desynch of 200. Many HOTP systems will simply ask you for a second code and fix a desynch of less than 500 codes or so by themselves.


RSA assumption and cryptography The RSA assumption states that it is hard to find $m$, given $c = m^e \bmod{n}$, $e$, and $n$ (for appropriate choice of $n,e$).

Suppose that there exists an algorithm, $D(c,e,n)$, that finds $m$ in 1% of cases.
What could be a pseudocode of an algorithm that can use $D(\cdot,\cdot,\cdot)$ and finds $m$ easily for any $c$?

Since it sounds a lot like homework, I will only give a hint, not the actual answer.

First, you don't want to mess with $e$, since you can not be sure that a different $e$ is actually a valid exponent ($e$ has to be coprime to $\phi(n)$, which contains at least $2$ as prime factor).
RSA is not IND-CCA. The same attack that works against IND-CCA also works against this.
This attack utilized the homomorphic property of RSA. If you decrypt $c=(ab)^e=a^eb^e$, you get back $m=ab$

edit: textbook-RSA is not IND-CPA either, but the according security game is trivial for the attacker, since the encryption is deterministic. That doesn't help in this case.


Why shouldn't I use ECB encryption? I'm using Java to generate encrypted strings, and I get this warning at build time:

  ECB encryption mode should not be used

So I'm wondering why I shouldn't use ECB and what I can use instead?

Why shouldn't I use ECB encryption?

The main reason not to use ECB mode encryption is that it's not semantically secure — that is, merely observing ECB-encrypted ciphertext can leak information about the plaintext (even beyond its length, which all encryption schemes accepting arbitrarily long plaintexts will leak to some extent).

Specifically, the problem with ECB mode is that encrypting the same block (of 8 or 16 bytes, or however large the block size of the underlying cipher is) of plaintext using ECB mode always yields the same block of ciphertext.  This can allow an attacker to:

detect whether two ECB-encrypted messages are identical;
detect whether two ECB-encrypted messages share a common prefix;
detect whether two ECB-encrypted messages share other common substrings, as long as those substrings are aligned at block boundaries; or
detect whether (and where) a single ECB-encrypted message contains repetitive data (such as long runs of spaces or null bytes, repeated header fields or coincidentally repeated phrases in text).

There's a nice graphical demonstration of this weakness on Wikipedia, where the same (raw, uncompressed) image is encrypted using both ECB mode and a semantically secure cipher mode (such as CBC, CTR, CFB or OFB):

While this scenario is somewhat artificial (one would not usually encrypt raw images like this), it nicely demonstrates the problem with ECB mode: repetitive areas in the input image result in repetitive patterns in the encrypted output, so that many large-scale features of the image remain recognizable despite the encryption.  In the real world, a cryptanalyst attacking an ECB-based encryption scheme would be more likely to look for such patterns in a hex dump of the ciphertext, but the principle is the same.

An actual case of this weakness of ECB encryption contributing to a real-world data compromise is given by the 2013 Adobe password database leak, as described in this answer.  Here, one element contributing to the severity of the leak was that, instead of hashing them properly, Adobe had encrypted the passwords using ECB mode.  This allowed the attackers to quickly locate passwords shared by multiple accounts, or sharing a common prefix with other passwords (like password1 and password2), and also revealed the approximate length of each password.

The ECB encryption mode also has other weaknesses, such as the fact that it's highly malleable: as each block of plaintext is separately encrypted, an attacker can easily generate new valid ciphertexts by piecing together blocks from previously observed ciphertexts.

However, the malleability is only an issue if ECB encryption is used without a message authentication code, and, in this situation, is shared (to some extent) by all other non-authenticated encryption modes, like the aforementioned CBC, CTR, CFB and OFB.  Thus, it cannot really be considered a specific weakness of ECB mode, even though it does tend to be an additional issue whenever ECB mode is used.

What should I use instead?

You should use any authenticated encryption mode, such as GCM, EAX or OCB.

Personally, for short messages, I'm rather fond of SIV mode (RFC 5279), which provides an extra layer of misuse-resistance.  (Many other encryption modes will break rather badly if the same IV / nonce is accidentally used to encrypt multiple messages.  SIV mode retains all its security properties in this situation, except for leaking whether the encrypted messages are identical.)

You can also use any traditional semantically secure encryption mode (such as CBC or CTR), combined with a message authentication code (such as HMAC) using the Encrypt-then-MAC construction.  (That is, you should first encrypt the message, then compute a MAC of the ciphertext, and append it to the ciphertext.)  As long as you make sure to verify the MAC before attempting to decrypt the message, this construction will protect you from the various vulnerabilities of these modes to active (chosen-ciphertext) attacks.

For disk encryption or similar applications that require the ability modify parts of the ciphertext without re-encrypting all the data, you should use a cipher mode designed for that purpose, such as XTS.  Note that such modes generally lack resistance to active attacks, and may have other weaknesses that should be understood before using them.  If possible, they should be combined with some form of integrity protection, such as a MAC on a hash tree.


SHA3-512 similar message digest How is it possible to find a similar message-digest for SHA3-512 for the first 80 bits or so?
There was a Q/A on this site where the answer stated that 80 bits that $2^{42}$ computations are required. But shouldn't it be $2^{40}$ considering the root of 80? Why did it state $2^{42}$?

Simplifying the deleted question: it's given two large distinct prefix bytestrings $p_0$ and $p_1$, and it's asked two suffixes $s_0$ and $s_1$ so that $H(p_0\mathbin\|s_0)=H(p_1\mathbin\|s_1)$ for some $b=80$-bit cryptographic hash $H$ (obtained by truncation SHA-3, but that's immaterial). I concluded

The number of hashes to compute is in the order of $2^{42}$.

The standard technique for this is to define a function
$$\begin{align}f:\{0,1\}^b&\to\{0,1\}^b\\
x\quad&\mapsto\begin{cases}H(p_0\mathbin\|r_0\mathbin\|x)&\text{if the low-order bit of }x\text{ is }0\\
H(p_1\mathbin\|r_1\mathbin\|x)&\text{otherwise}\end{cases}\end{align}$$
where $r_0$ and $r_1$ are short fixed bytestrings of length chosen to align $x$ in a way making multiple evaluations of $f$ as fast as possible.
Observe that if we get $x_0$ and $x_1$ differing in their low-order bit and with $f(x_0)=f(x_1)$, that yields the desired suffixes $s_0=r_0\mathbin\|x_0$ and $s_1=r_1\mathbin\|x_1$.
If we evaluated $f$ for incremental inputs $x$ and looked for all exploitable collisions, for $2n$ hashes ($n$ with each value of the low-order bit), the probability of collision is slightly below $1-(1-2^b)^{n^2}$. Thus for $n=2^{b/2}$, that is $2^{b/2+1}$ hashes, and $b$ of cryptographic interest, the probability is about 63%. It's only 22% for $2^{b/2}$ hashes. That's lower than in pure hash collisions for a given number of hashes, because collisions between inputs with the same low-order bit are worthless, and about half of collisions fall into that category.
We can now answer

shouldn't it be $2^{40}$ considering the root of $2^{80}$ ?

by: No. Even with the best possible collision-detection technique, it's rather unlikely we can solve the problem with $2^{40}$ hashes. We can be cautiously optimistic with $2^{41}$.
Further, that exact strategy would require $O(2^{b/2}\,b)$ memory, which is impractically much; and a lot of its execution time would be search in that memory. The simplest solution to that issue is Floyd's cycle-finding, which reduces the memory requirement to a negligible $O(b)$, but markedly increases the expected number of evaluations of $f$. I don't know the exact factor, which depends on strategy; perhaps $3$, which would put us above $2^{42}$.
There are a number of improvements to cycle-finding. One key idea is distinguished points: we define $g$ iterating $f$ until the output has some characteristic (e.g. has the top 24 bits at zero), and try to find collisions in $g$ for inputs with that characteristic. When we get one, there remains only little work to find a collision for $f$, and it has 50% chance to be usable. That enables a time/memory trade-off which will get us to roughly $2^{41.5}$.
There's also the issue of distributing the work on several machines or execution units of a GPU, which would be a necessity is we use SHA-3 and want the result fast. The trade-off becomes between work and communication, and sometime we are willing to make sizably more hashes than the minimum, say in the order fo $2^{b/2+2}$. The standard reference is Paul C. van Oorschot & Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications, in JOC, 1999.


KDF with low-entropy salts I need to derive a key from a username and a password. These are the only two things I have access to. What I thought is using PBKDF2 with username as the salt and password as the master password.

Could someone help me evaluate / confirm this solution in terms of security?

Update: Since the salts are required to be unique, I have thought about using the following as a salt:

HASH(USERNAME) XOR SOME_GLOBAL_CONSTANT

or perhaps

HMAC(SOME_GLOBAL_CONSTANT, USERNAME)

What do you think of this updated salt value?

That's a reasonable solution if you can't use a random salt. If you personalize your hash function for your application, then the salt is globally unique for each user. (e.g. use sitename||username as salt) The only salt reuse happening is that older passwords of the same user have the same salt. But that's a very minor issue.

I disagree with Polynomial who wants unpredictable salts. Unpredictability is not necessary for most protocols involving password hashing. Global uniqueness or at least rareness is the decisive property.

To combine sitename and username I'd simply go with concatenating them. Your HMAC suggestion is certainly fine too. Your xor variant gives me a bit of a bad feeling, but is probably fine too.


How does DJB's nistp224 manage to fit compressed points into 224 bits? DJB's nistp224 program purports to be an implementation of elliptic curve Diffie-Hellman relative to the standard NIST P-224 elliptic curve.

To the best of my understanding, ECDH relative to this curve should produce 225-bit public messages (compressed points consisting of a 224-bit x-coordinate and a 1-bit y-coordinate), which require 29 bytes to encode (in SEC1 format).  Yet somehow nistp224 manages to produce 28-byte messages, which are therefore one bit short.

How does it do this?  I find the source code utterly unenlightening.

(Rationale for question: It sure would be nice if I could shave a byte off my messages on the wire.)

That's because you can do ECDH by exchanging only the X coordinates of your public value; as long as the shared secret depends only on the x coordinate, everything works out.

Here's the fundamental property of elliptic curves that makes this work, the x coordinate of $nP$ is only a function of the x coordinate of $P$ (and $n$); it does not depend on the y coordinate of $P$.

So, if the two sides select their secret values as $a$ and $b$, they both compute $aG$ and $bG$.  They then exchange the x-coordinates of those points to the other.  What both sides can do is then compute the x-coordinate of $a(bG) = b(aG) = (ab)G$.  This x-coordinate is the same value on both sides.  Now, neither side knows the y-coordinate of the common point; however, the x-coordinate is sufficient for a shared secret.


Modular exponentiation on calculator for textbook RSA How do you encrypt $51$ with public key $(n,e) = (91,23)$

I understand that $c = 51^{23} \bmod 91$.  How can I calculate the result on a calculator?

If your calculator is able to compute $n^2$, you can compute $m^e \bmod n$ using the binary exponential method.

In this method, you should first compute the binary form of $e$. Let $\ell$ be the number of bits in $e$, and let $e_i$ denote the $i$-th bit of $e$, so that $e=\sum\limits_{i=0}^\ell e_i \cdot 2^i$.

Now, with the algorithm below, you can compute $c$:

  $z:=1$
  $\text{for } i:= \ell \text{ down to } 0 \text{ do:}$
  $\quad z:=z^2 \bmod n$
  $\quad \text{if } e_i = 1 \text{ then } z:=(z \cdot m) \bmod n$
  $\text{end for}$
  $\text{return } z$


AES-CTR mode and the Biclique Attack The biclique attacks that break AES (Biclique Cryptanalysis of the full AES) appear to require decryption oracles to work, presumably because the key schedule of AES is weaker in the decryption direction, enabling better bicliques to be constructed starting from the ciphertext end.  Which is to say, these attacks show that AES does not have 128 bits of security under the Chosen Ciphertext Attack (CCA) model.

But what about modes of operation that only require us to assume the underlying block cipher is a PRP rather than a SPRP, i.e. secure under the Chosen Plaintext Attack (CPA) model?  For example, CTR mode.  Does AES-128-CTR mode still have 128 bits of security not-withstanding the biclique attacks?  Are there also biclique attacks on the full AES starting from the plaintext end?

I do not remember if we checked this explicitly, but my guess is that in the chosen-plaintext setting the biclique attack would still be faster than the exhaustive search, maybe by the factor of 2 compared with 4 in the chosen-ciphertext setting.

However, both results are pretty far from declaring AES broken in any sense. Such small gain over exhaustive search is admissible by virtually every mode of operation. For modes CBC, CTR, CFB, OFB the situation is even simpler: they claim 64-bit security only, because if the adversary is allowed to ask more than $2^{n/2}$ queries for $n$-bit blockcipher, various collision effects invalidate security proofs. Moreover, it becomes hard to state what sort of security should be provided beyond the birthday bound: should the cipher be indistinguishable from the random permutation or function, or the whole ciphertext (possibly gigabytes long) should have this property.

To summarize, the security claims of AES-CTR are not affected by biclique attacks at all, and probably will never be since the meet-in-the-middle attacks (which include bicliques) usually can not be faster than $2^{n/2}$.


Discrete Logarithm problem with inverse Let $\mathbb G$ be a cyclic group of order $q$. The Discrete Logarithm Problem (DLP) is, given $g, g^x \in \mathbb G$, to compute $x \in \mathbb Z_q $.

I'm interested to know if there is a known variant of DLP as follows:

  Given $g, g^x, g^{x^{-1}\bmod q} \in \mathbb G$, compute $x \in \mathbb Z_q$

It is clear that this variant would not be harder than the DLP, since a DLP solver could be used to solve this problem simply by ignoring the third input.

This problem seem to be equivalent to a particular instance of the $k$-Strong Discrete Logarithm Problem.

Let $\mathbb G$ be a cyclic group of order $q$. The $k$-Strong Discrete Logarithm Problem ($k$-DLP) is, given $h, h^x, h^{x^2}, .., h^{x^k} \in \mathbb G$, to compute $x \in \mathbb Z_q $. Taking a simple change of variable ($h^x = g$), one obtains an equivalent version of the problem, which is as follows:

  Given $g^{x^{-1}\bmod q}, g, g^x, ..., g^{x^{k-1}} \in \mathbb G$, compute $x \in \mathbb Z_q $

It can be seen then that the problem in the question is the case of $k=2$.

The $k$-Strong Discrete Logarithm Problem is discussed in Correlated-Input Secure Hash Functions by Goyal, O'Neill, and Rao, for instance.


Minimum plaintext length for AES-GCM In AES-GCM, from what i understand, the plaintext(as well as AAD and IV) bit length taken in must be a multiple of 8 (as specified by NIST Spes. Pub 800-38D). The AES-CTR however, doesn't "care" about the bit length.

The majority of my confusion comes from looking at how the AES-GCM works as a whole. It seems to me that to appropriately generate an authentication tag it needs two strings of plaintext. Additionally , the GHASH function seems to take in n 128-bit ciphertext strings.

Which leaves me with the question: What is the minimum amount of plaintext data required(after any padding) to appropriately encrypt and authenticate using AES-GCM?

The original proposal specifies:

  A plaintext $P$, which can have any number of bits between 0 and $2^{39} − 256$.

The NIST SP 800-38D specifies:

  Although GCM is defined on bit strings, the bit lengths of the plaintext, the AAD, and the IV shall all be multiples of 8, so that these values are byte strings.

So there is a clear difference between the original proposal and 38D. I presume that this is because the test vectors almost never contain any tests for plaintext (or AAD, IV and authentication tag) that are not a multiple of 8 bits. In that case it is probably better to leave it out.

So onto your question:

  What is the minimum amount of plaintext data required (after any padding) to appropriately encrypt and authenticate using AES-GCM?

Well, zero bits, obviously. GCM doesn't require any padding of the plaintext before it is used within the algorithm. Steps 4 & 5 in 7.1 of 38D define how the input is padded before it is used. Although the specification is limited to accepting bytes, there is nothing stopping you from creating an implementation that operates on bits.


How to combine $n$ 'less random' bits to generate one 'more random' bit? Suppose we have a random number generator badrand() generating 1 with probability $0.9$ and 0 with probability $0.1$.
How can we combine $n$ bits from badrand() to get one bit of betterrand()? What will be its probability of giving a 0 or 1?
I assume that this is possible since the entropy of the combined output increases with each call to badrand(). Please guide me if I am wrong.

If the outputs of badrand are independent and identically distributed you can use a randomness extractor function with $m=1$ and $k=-n\lg 0.9$.
If you're prepared to have a non-deterministic waiting time for an output, the von Neumann extractor is good way to get probability exactly 0.5 out of i.i.d. bit outputs. Sample pairs of bits until you get a pair with precisely one zero; if your pair is 01 return 0 and if it is 10 return 1. The i.i.d property means that the probability of these two events is equal (in your example both have probability 0.09 and resampling has probability 0.82, leading you to expect around 100/9 badrand outputs to produce one betterrand output).


Montgomery Ladder vs Double-and-Add I would like to know what (if any) are the advantages of using Montgomery Power ladder over the Double-and-Add-Always algorithm.
I think that firstly, Monty would be slightly faster than DoubleAndAdd. But I'm not too sure about side-channel security.

I'm asking this in the context of RSA's modular exponentiation and ECC's Elliptic Curve Scalar Multiplication.

Actually, those two algorithms are surprisingly close; I'll write both of them up to show how close they are.

They both can be written as a combination of three substeps:

A := Add( B, C )

This takes the two points B and C, and adds them together (I'll be writing things in additive notation; in RSA, with would be a modular multiplication)

A := Double( B )

This takes the point B, and adds it to itself (or, in RSA, a modular squaring)

If (cond) swap( A, B )

This tests a condition on the multiplier (exponent in RSA), and depending on that, either exchanges A and B, or leaves them alone.  Note that if it leaves them alone, it still performs the read and write operations; however when it writes A, it writes A's original value (and not B's value); this allows this operation not to leak any information via the cache.

Note that all these three can be done in constant time, and with constant memory accesses; hence we don't leak any information, even against an attacker who can listen to cache accesses.

Now, both algorithms use temp variables A and B, and I'll call the original point G.  The core of the DoubleAndAdd algorithm can be written as:

A := Double(A)
B := Add(A, G)
if (bit_i_of_multiplier_is_set) Swap(A, B)

(Actually, the swap operation here can be simplified; we don't care if it actually updates B)

The core of the Montgomery Ladder can be written as:

if (bit_i_xor_bit_i_1_is set) Swap(A, B)
A := Add(A, B)
B := Double(B)

There are also differences with how the two algorithms initialize A and B (Montgomery stirs in G by how it initializes A and B), and where they find the final result -- those are relatively minor.

So, given that both algorithms solve the problem of doing a point multiplication in constant time without leaking any information via the cache, how do they compare?

Well, for one, if you look at the Montgomery Ladder, the two operations it does can be done in parallel.  I would be skeptical if it would be a win to give them to two different cores (core synchronization is not cheap); however if you could have them done on a 2-way SIMD (if the add and double operations are sufficiently similar), that may be a win.

On the other hand, if you look at the DoubleAndAdd algorithm, we always add the point G.  Now, with Elliptic Curves and RSA, this doesn't buy us anything, but with Diffie-Hellman, we can pick G to make this operation cheap (say, G=2); that would speed up the first phase of the operation.  Also, in my humble opinion, DoubleAndAdd is a bit less complex than the Montgomery Ladder.

So, bottom line: there isn't actually that big of a difference; there might be some minor implementation differences.


Size of IV in AES-GCM according to RFC 4106 RFC 4106 specifies about nonce. It contains a salt of size 4 octets and an iv of size 8 octets. Further, RFC specifies that salt is assigned at the beginning of the security associations which is established through Internet Key Exchange (IKE) and salt value is constant. But all most all of the implementations and descriptions found about AES-GCM specifies iv as 12 octets and there is no consideration of salt value.

AES-GCM takes inputs as a secret key, an IV, a plaintext and Additional Authenticated Data (AAD). AES-GMAC is a variant of AES-GCM which provides authentication of data by keeping plaintext as zero bits.

Other questions I have regarding AES-GCM mode are.

I know that AES-GCM can be used for authentication of data by Can we use AES-GCM mode only for encryption by ignoring authentication?
Is it mandatory to use iv for encryption using AES-GCM?
What are the allowable variants of AES-GMAC like AES-GMAC128, AES-GMAC256 etc. ?

kelalaka answered your questions, however I do believe there are things that could use some clarification:

  RFC 4106 specifies about nonce. It contains a salt of size 4 octets and an iv of size 8 octets. Further, RFC specifies that salt is assigned at the beginning of the security associations which is established through Internet Key Exchange (IKE) and salt value is constant. But all most all of the implementations and descriptions found about AES-GCM specifies iv as 12 octets and there is no consideration of salt value.

First, a clarification on terminology (at least, the terminology I'll be using in my answer below):

Nonce - this is the (typically 96 bit) value passed to the GCM routine
IV - this is the value within the packet - IPsec with GCM uses 64 bit IVs
Salt - this is the additional value that is included with the recipe to generate the nonce.

RFC 4106 is specifically about how to use GCM within IPsec; as such, it has a recipe for generating the nonce (which you refer to as an 'iv') that GCM requires.  It does it by talking 8 bytes chosen by the encryptor (which he places in the 'iv field' within the packet, and which the decryptor extracts from the packet), and 4 bytes for the key derivation (the 'salt') and concatenating them.

This is specific to IPsec (actually, TLS's use of GCM does the same thing); other protocols which use GCM may generate (and communicate) their nonces in a different way.  Because a cryptographical routine is typically protocol agnostic, they would not have the IPsec-specific recipe built in.  Instead, they would assume that something protocol specific would generate the nonce, and pass the entire nonce in.

As for why IPsec uses this specific recipe to generate GCM nonces, well, it's to frustrate potential multitarget attacks.  Suppose that the attacker has a large number of GCM encrypted sessions, and that he would like to recover the contents of one of them (and doesn't really care which one it is).  Further suppose that the GCM implementations use the same IVs for each session (e.g. the first encrypted packet might always use an IV of 0).  Then, what the attacker might try to do is guess an AES key, and generate the GCM privacy keystream, and see if that the correct keystream for the initial packet for any session (that turns out to be efficient with plausible assumptions).  If he could do that, that would mean that, for a 128 bit key and $N$ sessions, his expected work effort to break one of the sessions is $2^{128}/N$ trial decryptions, which is less than we want.  However, by including the 32 bit salt (which varies between sessions), this expected work effort increases to $2^{160}/N$ (because he has to guess the salt as well as the key); in particular, this means that this multitarget attack is actually less efficient than a simple brute force attack unless $N > 2^{32}$, which is quite a lot.  Note that this salt doesn't actually help against brute force attacks against a single session; it doesn't hurt either.  And, it doesn't really have to be secret (however, there's no particular reason we have to go out of our way to publish it either...)


Security assessment between $g^{a_ix_i+r_i}$ and $g^{x_i+r_i}$ Imagine a tagging system whose security requirements imply to learn nothing from the tag about the encoded value.

We consider a plaintext space $X \in \mathbb{Z}_p$ and a group $\mathbb{G}$ where the DLP is computationally hard.

The sender sends $\sf{tag_1}=g^x_i$ where $g$ is a generator of $\mathbb{G}$. This is not really secure in the sense that we provide the attacker an oracle to verify its guess on values in $X$.

We change the tag to be of the form $\sf{tag_2}=g^{x_i+r_i}$ where $r_i$ is a random value from $\mathbb{Z}_p$

We consider another tagging scheme where $\sf{tag_3}=g^{a_ix_i+r_i}$ where $a_i, r_i$ are random values from $\mathbb{Z}_p$

Is $\sf{tag_3}$ more secure than $\sf{tag_2}$? Is there an attack in $\sf{tag_2}$ which is mitigated with $\sf{tag_3}$?

It is not entirely clear what your exact security requirements are and for which purpose you require this construction. I assume that the tags can not be manipulated by an adversary, e.g., are signed, and that users do not try to change their choice of $x_i$ after having a tag. Anyways, I give it a shot (although I may be wrong due to some information I do not have):

First Construction

Clearly, for the first construction you can simply try guessing $x_i$ and test against $g^{x_i}$ (which will be problematic if your $x_i$ come from a small set).

Second Construction

For your second construction, if $g^{\sum r_i}$ is revealed, then you can again test: Lets say for simplicity you have only one tag, then given the aggregate of the $r_i$ values (which happens to be $g^{r_1}$), you can just guess $x_1$ and test as in the first construction. Clearly, if there is more than one tag you can also test by cancelling out $g^{\sum r_i}$ from the aggregate of all tags, but the sum $x_1+\ldots+x_n$ in the remaining value $g^{\sum x_i}$ may not be unique anymore (so it depends if the $x_i$ can only take some specific values - then your sum could be unique but it must not be the case).

Thrid Construction

For the third approach with tags of the form $g^{a_ix_i +r_i}$: If the value $a_i$ is uniformly at random chosen by every user, then even when publishing $g^{\sum r_i}$ this will not give an advantage for testing, as even when cancelling out $g^{\sum r_i}$ in the full aggregate of all tags you still have $g^{\sum a_i x_i}$. Without knowing any of the $a_i$ values, you cannot test anymore (this is even unconditional hiding - for uniformly random $a_i$, the value $g^{a_i}$ is a random element and so is $(g^{a_i})^{x_i}$). So your last construction is secure even if the values $x_i$ are known to come from a small set (clearly, assuming that the values $g^{a_i}$ are not available to the adversary).


How do I express each element in a field F as a power of a primitive element? I have a field $\mathbb F_{2^4}$, and it is represented as a residue ring of the

polynomials over $\mathbb F_2$ modulo the polynomial $\beta^4 + \beta^3 + \beta^2 + \beta + 1$.

I want to express each element in this field as a power of a primitive element $β+1$.

My questions are:

What are the elements of the fields?
How do I express them as powers of the given primitive element?

Any hints will be very helpful.

Just enumerate all powers of your primitive element.  There are only 15 of them.  That will give you a lookup table that allows you to translate from field element to its expression as a power of the primitive element.