Calculating RSA Public Modulus from Private Exponent and Public Exponent If I know the private and public exponents ($d$ and $e$) of an RSA key pair, is it possible to (efficiently) calculate the public modulus $n$?

Summary: finding $n$ from $(e,d)$ is computationally feasible with fair probability, or even certainty, for a small but observable fraction of RSA keys of practical interest, including with a modulus much too large to be factored.
I'll assume

unknown $n=p\,q$ with $p$ and $q$ unknown distinct large primes of comparable order of magnitude, say $\max(p,q)<2\min(p,q)$.
given $(e,d)$ with small $e$ (e.g. one of the 5 Fermat primes).
a known one of $d=e^{-1}\bmod\varphi(n)$ (as often in textbook RSA) or $d=e^{-1}\bmod\lambda(n)$ (as in FIPS 186-4) holds.

It follows from their respective definition that $\varphi(n)=(p-1)(q-1)$ and $\lambda(n)=\varphi(n)/g$, with $g=\gcd(p-1,q-1)$.
It holds $h\,(p-1)(q-1)=(e\,d-1)$ or $h\,(p-1)(q-1)=g\,(e\,d-1)$ for some unknown $h<e$, and a $g$ that can be found by enumeration, for it is a small even integer, often $2$ (always in some key generation strategies), rarely above $10$.
In the cases where we can fully factor $e\,d-1$, that will leave an enumerable number of options for re-arranging its factors into $p-1$, $q-1$ and $h$. Given the size and primality constraints on $p$ and $q$, few possibilities will remain, often a single one. $n$ follows.
That can sometime work in cases where the best factorization obtained for $e\,d-1$ is partial, but we are lucky enough that the remaining large composite has all its factors in a single of $p-1$ or $q-1$. This is possible only if that remaining composite is less than $\max(p,q)$, and then only with low probability.
The proportion of keys where the methods works depends on the modulus size, on how hard we are willing to try to factor $e\,d-1$, and on how the primes $p$ and $q$ have been generated (in particular: at random, or with a large known prime factor in $p-1$ and $q-1$ in consideration of Pollard's p-1 factorization. In the later case, the magnitude of that factor will be important. If high (e.g. 60% of the bit size of the primes), the task will be hard; but typical parametrization is lower).
The factorization strategy could be similar to that for arbitrary integers:

pull the small factors of $e\,d-1$ by trial division.
pull more small factors by Pollard's rho
optionally but somewhat advantageously, some Pollard's p-1.
optionally but still somewhat advantageously, some William's p+1.
a lot of ECM, where most of the effort should be when we get barely enough $(e,d)$ pairs to hope find one allowing success.
perhaps, if a large composite remains that needs to be factored, MPQS or GNFS.

Illustration, based on the the 829-bit RSA-250 recently factored.
We get $e=65537$ and the following 828-bit $d$ known to be $d=e^{-1}\bmod\varphi(n)$.
1219002363472329316632678572665837077877528004905520939230037996503041169769564562618818603930146413036298872224725717654149810234132887053185714832075764978825457518728410705223332728199047961645304133836997233492855592278022423674340390891560261753

We compute the 844-bit $m=e\,d-1$, and pull out its smalls factor $2^3\times3\times5\times13\times6221\times6213239\times440117350342384303$ (that's seconds), leaving a 740-bit $m_1$ to factor.
The command¹ ecm -pm1 1e7 <m1 found a 73-bit factor $8015381692860102796237$ in <3s, leaving a 667-bit $m_2$ to factor.
The command ecm -pp1 1e7 <m2 found a 67-bit factor $101910617047160921359$ in <7s, leaving a 600-bit $m_3$ to factor.
The command ecm -pp1 1e8 <m3 found a 72-bit factor $4597395223158209096147$ in <77s, leaving a 528-bit $m_4$ to factor.
We need to factor that $m_4$, because it is still too large to be a divisor of $p-1$ or $q-1$. The command ecm -pm1 3e8 <m4 failed after ≈85s. The command ecm -pp1 1e8 <m4 failed after ≈69s. The command ecm 1e8 <m4 launched repeatedly on multiple cores repeatedly failed after ≈272s. We would have been very lucky if that had worked.
I did not really factor $m_4$ with GNFS², but that's well within reach. The factors of $m_4$ are  276-bit and 253-bit (the first two in the list below)
$p-1$ and $q-1$ are even, thus we have these 12 factors to split between $(p-1)/2$, $(q-1)/2$ and $h$:
72769022935390028131583224155323574786067394416649454368282707661426220155269516297
11015842872223957032465527015746975907581857223611379316467045416408679146689
8015381692860102796237
4597395223158209096147
101910617047160921359
440117350342384303
6213239
6221
13
5
3
2

There are a mere $3^{10}<2^{16}$ possibilities to explore after we assigned the first two entries to $(p-1)/2$ and $(q-1)/2$. We want to explore those with $\max(p,q)<2\min(p,q)$ and $h<e$. Pruning this tree requires only addition of approximate logarithms. That's a near-trivial knapsack problem. I've not coded it, but I'd be surprised if there was a solution yielding $p$ and $q$ prime other than $h=2\times3\times6221$, and these $p$ and $q$ which immediately yields $n=p\,q$, here RSA-250.
33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711
64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367

¹ GMP-ECM implements carefully optimized Pollard's p-1, William's p+1, and ECM. I let it use a random seed, thus some of the results may take a few runs to reproduce.
² I'm hearing a lot of good of the implementation in CADO-NFS.


Two mutually untrusted parties want to exchange data: how to ensure each one gets the data it needs? I am trying to come up with what could maybe be a novel algorithm for an application I am writing. Client A has a file fA. Client B has file fB. Each party is untrustworthy and will try to rip off the other party. Client A wants the fB and client B wants fA.

How can I make an algorithm were it is not possible for them to screw the other player.

For example:
    A encrypts fA and send the file to B.
    B encrypts fB and sends it to A.

Now, both A and B have an encrypted version of the file they want.
How can they both share the decryption key at the same time... or what?

Is this even possible? This is breaking my mind.

Since each client will try to rip the other party, Client A cannot send the file fA to client B and expect client B to send back its file. If client A sends it first "with no guarantees", client B will simply run off with the file.

In real life a person holds the pot in one hand, the other holds the cash in the other. They both trade each hand at the same time. The guy with the cash now ends up with the pot and vice versa. How can I do something similar with computer bits. (client A and B are on a network at different locations).

EDIT: Please note that each party has a hash of the file they are supposed to get. Therefore, the parties cannot send a junk file to the other guy whit-out him knowing. A trusted third party will provide the hash.

It can be done, but the algorithm is a bit complex and the hashes have to be specially constructed. The basic idea is this:

What you need is a way for each party to give the other a verifiable "clue" that reduces the search space for the possible file, say by a factor of 10. As soon as one party stops giving clues, the other stops giving clues as well. So a deceiver can, at worse, give you one fewer clue than you have given him.

That means you may have to do 10 times as much computation as he does to recover the file, but that's not enough to make the task possible for him but impossible for you.

One way to do this is to encode the file such that every byte is needed to recover any byte of it (for example, you can do this with no waste of bytes using an erasure code). Then you can make the hash actually include four hashes. One is of the entire encoded file. The next is of the file with the last two bytes missing. The next is of the file with the next three bytes missing. The last is of the file with the next four bytes missing.

You can then exchange all but the last 10 bytes of the file with the other side and validate this by hash. Then you can exchange the next four bytes and validate. Then the next three, and so on through the four rounds. At worse, a deceiver leaves you with 256 times more work to do than he has. So if he needs the file within a day, at worse you get the file within 256 days.

You can switch to nibbles and make this 16 instead of 256 at the cost of more hashes and more exchanges.


Is there a secret sharing scheme which allows delegation/re-sharing without reconstructing the original secret? EDIT: Ilmari Karonen's answer below well not exactly what I want, gives a very good idea of what I am trying to accomplish.

Are there any known secret sharing schemes that allow new parties to be read in on a portion secret, preferably without all parties having to be online at the same time?
I don't want to have to keep the original trusted authority around. The question is, is this possible without reconstructing the original secret?

My idea is that I divide a secret between $N$ of $k$ people at time $T$. At time $T+1$, I want to change it to $n$ of $k'$ people. This may or may not be strictly possible, but is there something possible along those lines?

Suppose we have a $(k, n)$ threshold scheme meaning that there are $n$ shares of a secret distributed to different parties, and any $k$ shares can be used to re-create the secret.  A new person joins the club and wants to have a share of the secret too.  I contend that the secret must be available to a trusted party who can create the extra share.  Because if someone with little knowledge of the secret (or even as much
knowledge as a cabal of $k-1$ shareholders trying to break the scheme) could
create a new share of the secret, then this someone could repeat the process many times until $k$ shares are available, and thus recover the secret via the standard reconstruction
technique.  Now, it is possible to have a mathematical algorithm or computer program
that will take $k$ (or more shares) and create new shares without the secret being
explicitly reconstructed, that is, none of the quantities used internally or stored
anywhere (register or memory cell or disk or tape drive) will actually be the secret itself and so the new share creation process is safe from the casual eavesdropper.
However, a savvy opponent  who can view the process or get a core dump from the
processor  will be able to recreate the secret.


Attack on BB84 algorithm for quantum key exchange? I have a question which is related to the BB84 cryptosystem.

We are not able to send single photons so instead we send $K$ photons at a time all with the same polarization. An enemy can separate one of these from the remaining $K-1$.

If the enemy can detect the polarisation by only looking at one of the photons, the others may remain undisturbed and so the enemy will not be detected - is this correct?

Why can the enemy find our common key if $K=3$?

What you are describing is known as the Photon Number Splitting Attack (PNS), described for the first time (I think) by Brassard, Lütkenhaus, Mor ans Sanders in this 1999 paper. Several countermeasures have been invented since (single photon sources, robust protocols, decoy states), but detailing them would stray away from of your question.

If one sends 2 or more photons, the enemy can store this photon in a quantum memory, and make the polarization measurement after the basis choice have been revealed. The enemy then knows whether to measure in the rectilinear or diagonal basis, and has all the information shared by Alice and Bob.

In 2001, Scarani, Acín, Ribordy and Gisin proposed a protocol (SARG04 pdf, wiki) which is robust against PNS attacks while using the same physical modulation than BB84. This protocol works by exchanging classical information which is more ambiguous than the basis. However, as soon as $K\ge3$ and the losses are over 50%, this protocol is subject to an unambiguous discrimination attack.


Multiparty encryption and decryption Is it possible to send a single encrypted data message to multiple users so that the users receiving the message can only decrypt certain parts of the message, depending on their rights.

For example, I send a message "Hello World", User A could decrypt and receive the whole message(hello world), but user B could only decrypt a certain part and receive the message as "hello" only.

This is - in a way - Functional Encryption.

From Wikipedia:

  Functional encryption is a type of public-key encryption in which
  possessing a secret key allows one to learn a function of what the
  ciphertext is encrypting.

So, YES, it is possible.

For more information this paper might prove useful.


Authentication over the phone? Are there any known good methods of performing authentication over the phone in a way that's not susceptible to replay attacks?

The specific scenario that comes to mind is having an automated call centre which verifies the identity through one or more questions. Since the phone line is not guaranteed to be secure (or the user may simply be in public), the calls can be eavesdropped.

One idea that came to mind would be something akin to CHAP - the user hears a challenge, mentally hashes it (per this CryptoSE Q&A, perhaps Blum's hash is a good candidate) and then speaks the solution out loud. Has something like this been attempted before and are there any known vulnerabilities?

Take a look at the military's Dryad for authentication.


Secure entropy extractor for thermal noise collected from camera input? I have read this paper (pdf) which talks about measuring the entropy of thermal noise collected from camera input. They estimate the minimum entropy at about 4 bits per pixel. Probably estimating 1 bit per color looks to be the safest option from looking at the X500's camera:

The paper mentions some future research work on how to extract the random data. Edit: I have found that paper by the same authors which discusses some methods which I will read up on some more.

What I would like to know is how I can extract the entropy from each pixel in an information-theoretic way ie. to get true randomness. Hash functions will not be suitable for this purpose. It should also be simple to understand an implement in software.

One idea was to take the least significant bit for each color of a pixel. XOR the 3 bits together. Output 1 bit. After all the pixels have been processed and all the bits have been output, then run them through the Von Neumann extractor and this is the final output.

Another is to take an accumulator S, initialize to zero. XOR the next byte onto it, and rotate one bit. Repeat with 8 bytes or as many as needed. In theory it takes known regularities in the input and eliminates them one by one. The bits in the byte are biased, hence the rotations. We might also expect RGB values being biased, so we want to make sure equal amount of R, G and B goes into every bit.

Are any of these methods information-theoretically secure? I am open to any proper methods (or references to any prior papers) on how to do this properly in a conservative manner from any reputable cryptographers on here.

The question asks for an entropy extractor suitable for a particular camera, that is information-theoretically secure, but rejects hash on the rationale that hash functions are not perfectly secure. I'm afraid that for the same definition of secure in these statements, there's nothing on the book; perhaps nothing possible.

A method considered in the question seems to be: XOR the low-order bit of the readings of the three color channels, and feed the result to a Von Neumann extractor. Even assuming that the experimental data in the question holds, it is not information-theoretically possible to prove this will give a result indistinguishable from random, or even just unbiased. Rather, it could be demonstrated that for some model of the input, the output is biased; and more surprising things have occurred in similar attempts in practice. That's because:

There is reason to believe that the channels of the same pixel are heavily correlated; combining several of them is some arbitrary way not taking their nature into account can theoretically leave us with less entropy than in any channel alone, even if the combiner is information-theoretically secure under the assumption that its inputs are not uncorrelated.
The Von Neumann extractor is guaranteed to yield unbiased output if it is fed with mutually independent bits; but here there are reasons to fear that consecutive readings are mutually related (like: the analog route taken by pixels in the same scanning row is the same, hence the capacity of that line creates correlation).
Keeping only the low-order bit of a reading with known entropy is guaranteed to lower the entropy to at most 1 bit per sample, but there's no theoretical minimum, no matter how high the entropy before truncation is, unless some detailed hypothesis is made on the initial samples (in particular: it is quite conceivable that an ADC has its low-order bit constant while it recovers from a large input change).

Cryptographic entropy extractors, based on a hash or similar primitive, are the best thing around with a sound security rationale that does not require knowing some model of the physics and hardware in the entropy source. They are robust: a sound cryptographic entropy extractor convincingly gives output computationally indistinguishable from random for any mishap in its input, except for loss of entropy in the input ever since initialization, or leak of the extractor's internal state thru side channels.

By contrast, simple extractors relying on a some model of the source at their input tend to fail because the model is inaccurate, perhaps even briefly (for example: ADC saturation caused by a power supply transient, internal recalibration after some time or a temperature change).

If one insists on something extremely simple (not secure in a cryptographic sense), with a level of theoretical justification that it is unlikely to be catastrophic for a natural entropy source of unknown model, one could use

a multiplicative scrambler with a large $n$-bit state (detailed below); that's a simple entropy accumulator, of easily tuned capacity; it's output is provably perfectly random if its input is, and it smoothly degrades to a simple PRNG otherwise;
fed with all the bits output by the sensor's channels;
with sub-sampling  of its output keeping every $s$th bit, with sub-sampling factor $s$ coprime with $n$ and such that the residual bit rate is comfortably below the entropy rate on input estimated by the empirical data at hand (say, by a safety/fudge factor of 8, or 2 if the next step is taken); thus here, if we feed 24 bits per pixel and have an estimated 2.1 bit entropy per pixel (which the second figure on the right column justifies), we want $s$ at least 8*24/2.1 or 2*24/2.1; rounding up to the next prime number in order to widen our choice of $n$, that's $s=97$, or $s=29$ with the next step;
optionally followed by a Von Neumann extractor, which will divide the average bit rate by 4 (and make it irregular, which might be unwelcome); it is likely to remove a residual bias that could be present for low $n$ even if everything else goes as planned; it makes cryptanalytic attacks trying to distinguish the output from random more involved;
taking care to discard the early output until the number of discarded bits is several times $n$;
with precautions that nothing in the above can have any feedback to the entropy source (which would invalidate the hypothesis that the model of the source has nothing to do with the scrambler).

A multiplicative scrambler is built around a LFSR, based on a binary polynomial of degree $n\ge1$. The polynomial must have the constant term set (ensuring it does not lose entropy), and is often chosen primitive (which avoids a number of poor choices; and maximizes the expected period for input stuck at 0, though that's not essential here). For example, with $x^{23}+x^{18}+1$, the schematic of a scrambler used in telecoms goes

In telecoms, $n$ must be small (for quick resynchronization of the descrambler in case of error). We rather want something with a larger state, like $x^{256}+x^{187 }+x^{125}+x^{60}+1$, taken from eq-primpoly-w5.txt of Jörg Arndt's Tables of mathematical data, quoting Janusz Rajski, Jerzy Tyszer: Primitive Polynomials Over GF(2) of Degree up to 660 with Uniformly Distributed Coefficients, in Journal of Electronic Testing: Theory and Applications, vol.19, pp.645-657, 2003. A software implementation can use an array $b$ of 256 bits, and an 8-bit index $i$ (all operations on index being truncated to 8 bits)

for each input bit $x$

$i\gets i+1$
$x\gets x\oplus b_i\oplus b_{i+60}\oplus b_{i+125}\oplus b_{i+187}$
$b_i\gets x$
output $x$


Encrypting and Decrypting a 19-digits long BigInteger How can I take a maximum 19-digits long BigInteger and encrypt it with the following rules:

The result must be based on digits and lower-case English letters only.
All outputs must have the same length to any input. The length must be between 11 to 16 characters, depending on your method, but should be consistent for all possible inputs.
No easy patterns. For example, if you encrypt 000...1 and 000...2 the results should look completely different.
No collisions at all
Should be able to decrypt back to the original BigInteger.

Things that I have tried

Take the original number, XOR it by some key, multiply it by a factor and convert it to a base 36 string. The purpose of the factor is to expand the range so there won't be too much 0 padding. The factor must be between 1 to 36^16/10^19. The problem with this method is that a) it's not 'secure' enough, and b) close numbers have very similar results.
This answer. However, the result was often too short or too long, and the factor method used before didn't work here.

Well, first of all, when we do encryption, we generally insist that there is a "key" involved; this key is something that the person doing the encryption and the person doing the decryption knows, but no one else.  The goal of an encryption method is that someone who doesn't know the key can't gain any information from the encrypted messages.

Note: there are methods where the key that the encryptor knows differs from the key the decryptor knows; for example, the encryption key might not be able to be used to decrypt.  This comes in handy at times; I'll assume that you don't need that.

Now, the next questions are:

Do you care whether, if you encrypt the exact same number twice, you come up with the same encryption"?  Usually, we do care (because we don't want someone looking at the encrypted messages to deduce that we sent the same plaintext message twice), however you might not (for example, you might know that you'll never actually encrypt the exact same number twice).
Do you care whether, if someone tweaks the ciphertext, and you decrypt that ciphertext, you get a warning that the ciphertext isn't what was encrypted?  Generally, we do; we do this by adding a cryptographical checksum; if that checksum doesn't validate, we know that something's not right.

However, here is a procedure that doesn't address either of these issues:

First of all, a maximum 19-digits long bignum fits within 64 bits (almost exactly); the first step of the encryption process will to convert the Bignum into an 8 byte (64 bit) integer.
Now that we have an 8 byte integer, the easiest way to encrypt it would be to have a 3DES key, and encrypt those 8 bytes in ECB mode (in case you're wondering, ECB mode is almost always the wrong solution; this is one of the few situations where it is appropriate).
Now that we have an encrypted 64 bit value, we convert that value into a base-32 value (using the 10 digits and 22 lower case characters to represent the 32 digits; a 64 bit value can be represented by 13 base-32 digits; that's our encrypted text.

Decryption (as long as you have the 3DES key) is straight-forward; you just follow the procedure backwards, reversing each step.

Now, why did I leave the above two issues unaddressed?  Well, that's because such an extension would cause the ciphertext to be longer.  The problem with that is your limit that the ciphertext be limited to a maximum of 16 digits and lower case characters; that means that we have (at best) 18 bits or so of possible ciphertext expansion, and that's not much.

What this means is that if you do care about the above two problems, you may need to rethink your limits of the ciphertext size (or possibly expanding the ciphertext alphabet; allowing upper case characters would mean we have 31 bits to play with).


Is it fair to say that MACs use a signing algorithm? The Wikipedia page on MAC calls the algorithm that is used to generate the MAC as a signing algorithm. Is that a fair use of that term? Can we then say that HMAC-SHA-1 uses SHA-1 as the signing algorithm?
Since the term signing algorithms is usually used in digital signatures that use asymmetric cryptography, won't this create confusion?

You misunderstood something. HMAC-SHA-1 does not use SHA-1 as the signing algorithm. The signing algorithm is the HMAC-SHA-1 calculation, not an intermediate SHA-1 calculation. The signing algorithm takes the key and the message as inputs and produces the MAC value as output.
The usual terminology for the hash algorithm that an HMAC construction uses is “underlying hash algorithm”. Note that having an underlying hash algorithm is not a universal property of MAC. For example CMAC has an underlying block cipher, but no underlying hash algorithm.
Asking whether it's “fair” to use a word is meaningless. There is no ethical consideration. The right question is whether it's potentially confusing — but terminology choices are to some extent arbitrary.
The single pair of words “encryption, decryption” is used both for symmetric and asymmetric encryption. Does it create confusion? Maybe, but not much, in my experience. Confusion stems from not understanding the concepts, not from the use of the same words for two related but different concepts.
There's no intrinsic reason why authenticity would require different words for symmetric and asymmetric cryptosystems, but confidentiality would be fine with the same words. It's just a historical accident. And ”verification“ is already used for both symmetric and asymmetric cryptosystems.
The only reason not to use “signature” for a MAC is that it's uncommon. In cryptography, “signature” almost always means an asymmetric signature cryptosystem, the signature operation of that cryptosystem, or the output of that signature operation (or the input of the verification operation). However, if the context of a symmetric system is established, there's no risk of confusion. In the context of a MAC, using the word “signature” to mean the calculation of the MAC value is unambiguous, and there isn't a really good alternative other than “MAC” itself (which also refers to the cryptosystem in general and to the value, so it is quite ambiguous).
So while “signature” for a MAC calculation is not well-established terminology, it should be. That would reduce confusion.


Is modular Barrett reduction usable for Ed25519? I currently try to implement Ed25519 following this draft. I have implemented every field operation except the reduction by the group order $q$ (in chapter 5). I looked for a reduction algorithm and found montgomery reduction and barrett reduction. Because Barrett reduction seems to be more fitting I tried to understand how to implement it (mainly using this).

What I don't understand is how I can reduce a SHA512 hash by $q$, as the maximum possible value to reduce is ca. $2^{504}$ ($q$ is $2^{252}$, meaning $q^{2} = 2^{504}$). Is there a trick to reduce it in a step before that (like in curve25519 with $2^{256-38}$) or is Barrett reduction simply not usable here? (I don't necessarily need the fastest method available, a simple working one would be enough.)

Note that $q = 2^{252} + n$ for $n < 2^{125}$.  Consequently, $2^{252} \equiv -n \pmod q$, so $$2^{504} \equiv (2^{252})^2 \equiv (-n)^2 \equiv n^2 \pmod q.$$  Since $n^2 < 2^{250}$, you can reduce $$2^{504} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv n^2 x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod q.$$  Since the original input was only 512 bits long, $x_{\mathrm{hi}} < 2^8$, so we can set the bound $$n^2 x_{\mathrm{hi}} < 2^{250} 2^8 = 2^{253} < 2^{253} n + n^2 = q^2 - 2^{504},$$ which puts the reduced sum $n^2 x_{\mathrm{hi}} + x_{\mathrm{lo}} < q^2$ in the range of Barrett reduction.


Near preimages, applicable to Bitcoin? Bitcoin mining relies on generating a smaller hash than the so-called target (a function of the so-called difficultly), thus is vulnerable to a truncated preimage attack (you just need to obtain a certain number of leading zeroes).

I believe this is called a near preimage attack.

What is the current status of attacking truncated second preimages of SHA-256?

The current status as of the time I write this is: There are no known attacks on second pre-images for truncated SHA-256 that are faster than brute force.


Commitment based on authencticated encryption Let $(E,D)$ be the encryption/decryption of an authenticated encryption scheme. Consider the following commitment scheme.

Generate a random key $k$. Commit to $m$ by sending $c=E_k(m)$.
Reveal $m$ by sending $k$.

The hiding property of the above commitment scheme follows directly from standard assumptions on the confidentiality of $E$. However, I can't figure out if this is binding. It seems that most security notions for authentication do not consider swapping out the keys. In particular, is there a property that guarantees that $D_{k'}(c)$ fails to verify/decrypt?

is there a property that guarantees that $D_{k'}(c)$ fails to verify/decrypt?

No, there is not; all the security guarantees that authenticated encryption provides is of the form "if you don't know the keys, then it is difficult to..."; it says nothing about the difficulty of anything if you do know the keys.

And, it turns out that, with GCM, you can generate a ciphertext that authenticates with two different keys, and it's not that difficult.

Here's how it works; you pick two random keys $k_0, k_1$, a random authentication tag $t$, and an appropriate nonce and AAD.  Then, GCM has the property that, if you have a 32 byte ciphertext consisting of the 16 byte blocks $X_a, X_b$, this ciphertext would authenticate (in the context you picked) if:

$$h^3 X_a + h^2 X_b = C$$

where $h$ is the authentication key generated by the key, and $C$ is a constant that depends on the key, authentication tag, nonce and AAD, and all math is in $GF(2^{128})$

The two different keys generate different $h$ and $C$ values, and hence we can generate two simultaneous equations:

$$h_0^3 X_a + h_0^2 X_b = C_0$$

$$h_1^3 X_a + h_1^2 X_b = C_1$$

Everything here is known except for $X_a, X_b$; you have two simultaneous linear equations, and so you can solve for $X_a, X_b$, thus giving you a ciphertext that will decrypt to something with two different keys.

Now, this method doesn't give you any control over what they decrypt to, but still, that is enough to show that GCM isn't binding.

Instead, it would make a lot more sense to use a hash function, that is, $\text{Hash}(r, M)$ for a random fixed length nonce $r$.  The collision resistance property means that it is binding.  And, if the random nonce $r$ you include is longer than the hash, then it is plausible that even a computationally unbounded attacker cannot get more than weak probabilistic information of what you committed to.


Curve25519 choice of the prime In the paper for curve25519 is described how the prime was chosen. But I don't understand why the biggest 255-Bit prime was chosen instead of a 256 Bit prime. Can someone explain this to me?

A pretty good answer to the question can be found here
I try to give a shorter and more precise answer: The Curve25519-standard uses a pretty specific modulo-algorithm. A pseudocode of the algorithm looks like this:
def fastModulo(num, prime):
    # Basecase:
    if num < prime: return num
    if num < 2*prime: return num-prime
    # Split number in upper and lower bits:
    upper = upperBits(num)
    lower = lowerBits(num)
    # calculation:
    factor = differenceToPowerOfTwo(prime)
    nextnum = factor * upper + lower
    # recursion:
    return fastModulo(nextnum, prime)

The algorithm is faster if factor is smaller. So the difference to a power of two is important for the speed of the standard. Therefore the biggest 255 Bit prime was chosen instead of the biggest 256 Bit prime, because a significant speed boost is more important than a non signficiant security boost.


Any Idea on this identification scheme's problem? I was looking at the exercises of Cryptography theory and practice and I could not find the answer to this question anyone has an idea?

Well, here's one obvious attack:

Eve wants to impersonate Alice.
Bob wants Eve to prove that she's Alice.  Bob gives a value $x$ to Eve
Eve turns around, and asks Alice to prove that she (Alice) is Alice.  Eve gives $x$ to Alice
Alice gives the value $y$ to Eve
Eve then gives the value $y$ to Bob

Of course, that's not the attack that Stinson is looking for...

For the attack that Stinson is thinking of, here's a hint:

For a random quadratic residue $x$, how many values of $y$ are there s.t. $y^2 = x$?
Suppose Bob picks a random value $y$ and computes $x = y^2 \bmod n$ and gives it to Alice, what is the probability that Alice will compute a $y'$ that's neither $y$ nor $n-y$?
If Bob knows $y$ and $y'$, what could he do with those values?  Hint: consider $y^2 - y'^2 = (y + y')(y - y')$


Questions about a SHA3 cipher stream encryption scheme I have written an encryption implementation using a hash as a cipherstream for demonstration purposes. I know it is slower than more sensible options such as AES but I am interested in several things, which I will list at the bottom of this message.

NOTE: I am writing this in a pseudo-language that resembles C++ and using string for simplicity, I know that in practice the stream can output null character and cause trouble with string reading. SHA3 is assumed to be the 512-bit flavor.

SHA3_Sym_Enc(key,message)
{
base_key=SHA3(key); //not really needed, but in case we will ever allow the key to be "anything", we'll standardize the initial value like this

keystream="";
int counter=0;

for(read_message=0;read_message<message_length;read_message+=base_key.length()) //work in blocks of SHA3 outputs
    {
    hash_block=SHA3(base_key+string(counter)); //H(base_key+#) -> block#
    keystream+=hash_block; //add blocks into one big pseudorandom output
    counter++;
    }

keystream=keystream.Left(message.length()); //our keystream works in blocks, and might output bigger than the message, so trim any excess

return message^keystream; //XOR the keystream with the message, output
}

void main()
{
scanf(key); //input user key

nonce=generate_random_bytes(sizeof(SHA3)); //generate a nonce, SHA3-length should be enough

message_key=SHA3(key+nonce); //build the actual key that is going to encrypt the message via concat and hash

ciphertext=SHA3_Sym_Enc(message_key,plaintext); //output the encrypted message via the function described earlier

final_message=ciphertext+SHA3(ciphertext+message_key)+nonce; //append a MAC and the nonce to the message, note that we are not doing HMAC because SHA3 is supposedly immune to length extension attacks
}

final_message is [ciphertext][MAC][nonce].

Decryption:

Break up final_message, extract the MAC and nonce, their lengths are predetermined and they are known to be at the end so this will be easy
Take key+nonce and hash, reach message_key
Hash ciphertext+message_key, if they = MAC, the message is untampered
parse the ciphertext back through the function to rebuild the original message

Now my questions:

If given a large enough password, does this system appear secure?
The hash function used here has a 512bit output and 1066 bits of internal state; does it really provide 512 bits of security? Also because hashes produce wildly different and unrelatable outputs for even tiny incremental changes, would this mean it's immune to a related key attack, even without a nonce? I ask these because AES only goes up to 256 bits and has some known issues with related keys, and as far as these two points go, this stream would be superior?
If I were to chain only half of the output instead of the full H(base_key+counter), in order to further hide any vital info about the keystream's origins that an attacker would try to obtain, how many bits of security would I lose? Would I go down to 511 or 256? I think it would be really nice because the stream could, in theory, at some point output a block identical to a previous block, and this in full implementation would mean that the stream has reached an interval and starts repeating, but this one would not because the out-of-sight bits are still different, further confusing an attacker.

TL;DR: The idea is good and the implementation should work securely (with a solid security margin), given that some tweaks are implemented.

How secure is it?

  A) If given a large enough password, does this system appear secure?

If you replace "password" with "key", then the answer should be yes.

For analysis purposes, let's define $E_K(M) = \operatorname{MAC}_K(\text{CTR} || \text{Nonce})\oplus M$, with $\operatorname{MAC}_K(M) = \operatorname{Keccak}(K||M)$. The nonce is message based and the counter is call-based, i.e. the counter increases by one every 512 bit. The MAC was already analyzed here.

Let's further define $E^A_K(M) = \text{Nonce}||E_{K1}(M)||MAC_K(E_{K2}(M))$ which is the full authenticated encryption mode. Note that I have used different keys here for authentication and for encryption. This removes potentially dangerous dependencies between the two components. Not furthar that the order of key and ciphertext was swapped for the authentication to obtain more consistency and don't do potentially dangerous things.

The encryption component of the above is basically CTR-Mode, with a split-up counter where one part is "static" and one part is "dynamic", like is done in GCM. As you properly randomize it using the nonce and the counter, this is a proper instance and therefore the standard security bound of $2^{n/2}$ (for non-permutations) holds, i.e. the encryption strength is 256-bit. This is is due to the fact that you expect collisions from the hash after roughly $2^{n/2}$ invocations with different values and thereby can derive information about the plaintext from this. As for the authentication, at least collision attacks are required to break the standard encrypt-then-mac, also giving (at least) 256-bit security.

If you truncate the output of the hash function, security will decrease accordingly. SHA-3-256 would only yield 128-bit strength, as you'd expect collisons after only $2^{128}$ calls instead of $2^{256}$.

Potential Improvements

Make the keys independent.
Make the order of arguments to the hash consistent (i.e. always the key first)
Take associcated data (AD) into account, especially the nonce should always be authenticated.

Real Life applications

If this wasn't for demonstrations purposes you should strongly avoid rolling your own crypto and rather use AES-GCM (which should be faster anyways), any standard AES authenticated encryption scheme, Keyak or the scheme linked by otus in the comments: "Duplexing the sponge: single-pass authenticated encryption and other applications" by Bertoni, Daemen et. al.


Composition of X25519+XSalsa20+Poly1305 In a correct implementation of X25519+XSalsa20+Poly1305, I think I have the right understanding in saying that the Poly1305 message authentication code is a function of the secret key + plaintext.
My question is, on the recipient side, with such a construction, is there a need to supply some extra secret to check the validity of the MAC/Tag?
I guess my question stems from using other primitives such as HMAC SHA-256, where to verify the authenticated hash you need an additional secret to be shared.
In the case of X25519+XSalsa20+Poly1305, is the only secret required to decrypt and verify simply the result of the X25519 ECDH key agreement? i.e. there is no additional MAC secret?

Poly1305 itself has the requirement that its keys can only ever be used to generate a tag for a single message. That means that when Poly1305-AES (or another Poly1305-based authenticated encryption algorithm) is used as intended, the Poly1305 authentication key will be different for each message even if a key is reused.

However, the various Poly1305-based authenticated encryption algorithms (let's say Poly1305-*) support key reuse as long as the same nonce is not reused for a given key. The nonce is a non-secret (single use) value, so it can be sent alongside the ciphertext.

Poly1305-* generates a new Poly1305 (authentication) key for every new message. It does this by using the (authenticated encryption) key and the per-message nonce to derive the single use Poly1305 key. As long as both the sender and receiver use the same key and same nonce, it is possible for both people to derive an agreed-upon per-message Poly1305 (authentication) key.

In Poly1305-AES, that key is basically derived by extracting the first 16 bytes of an AES CTR-mode key stream. Subsequent keystream blocks are XORed with the plaintext. Note that bits used for the per-message Poly1305 (authentication) key and the bits used for message encryption are non-overlapping portions of the key stream. Because the keystream is pseudorandom, the per-message derived Poly1305 are expected to be unique.

Because this is a safe way for the sender and receiver to agree upon a per-message key, there is no need for an API to expose the per-message key to the programmer using the API. They just see parameters for one key and for the nonce.

(An API may even go further and abstract away the nonce, randomly generating one every time the encryption function is called and silently concatenating it with the ciphertext and MAC tag. The corresponding decryption function also could silently read the nonce from its expected location in the combined nonce/ciphertext/tag string, never exposing anything but the shared key, combined ciphertext, and plaintext to the programmer.)


How to safely derive a value from a secret? I have a use case of symmetric encryption with a single-use random key K known only by the sender and the receiver:

In my scheme, Bob is able to send beforehand a tiny amount of information to Alice. Alice must send her data through Eve, which is an untrusted network. V is the "address" of Bob (not secret): a single-use random value which means "please send the encrypted data to bucket V".

Bob has extremely limited bandwidth when first speaking to Alice.
I'd like to achieve an important improvement: let Bob send only 1 value to Alice:

Alice and Bob would tacitly derive the same value V, from their shared secret K.

How can Alice and Bob compute an identical random-ish, non-secret value for V?

In the diagram, V = AES.encrypt(42, K) where 42 is a public constant, but I don't know if it is a good idea.
Obviously, it is very important for me that Eve cannot guess the value of K, knowing N, V and 42.

My system currently uses AES and K has 83 bits of entropy.

To derive additional identity information from a key you can use a KBKDF - a key based key derivation function. One of the more modern ones is HKDF-expand which is based on HMAC. Any hash or HMAC based function is of course one way; adversaries should not be able to learn any information about the key, unless the key is too short or not random enough in the first place.

KBKDF's differ from password based key derivation functions or PBKDFs such as PBKDF2 in the sense that they do not require a work factor (or iteration count) and they may not use a salt either.

KBKDF's can often contain label or other $\text{Info}$ input parameter to distinguish between output keys, something that PBKDF's commonly do not feature. In this case the label may for instance be a single character "V" to indicate that you are indeed deriving a value for that particular field. This means that the derived key is specific to that input value, other keys derived using an other label will be entirely unrelated to the derived value for "V".

When specifying $\text{Info}$ it may be a good idea to also include some (statically sized) identity strings for the participants, so that the key for sending from Alice to Bob is different from the one used in the other direction.

Note that HKDF is still a relative heavyweight algorithm - if just because it uses HMAC instead of a hash. If the implementation size or speed is a concern then you could replace it with an extremely simple alternative such as ANS X9.63 KDF which consists of a hash over a statically sized key, a label/other info and a statically sized big endian counter of 4 bytes.

In formulas:

$$K_i = \text{H}(\text{IKM} \mathbin \| \text{I2OSP}(i, 4) \mathbin \| \text{Info})$$

and $\text{OKM}$ is the leftmost bytes of $K_1 \dots K_n$ with $n$ set high enough to get the required Output Keying Material, $\text{OKM}$.

Here:

The $K_i$ is a full block of output keying material, each block the size of the hash function $\text H$ being used;
$\text{H}$ is the hash function configured for the KDF, e.g. SHA-256;
$\text{IKM}$ is the Input Keying Material to the KDF ($K$ in your diagram);
The operator $\|$ means concatenation
$\text{I2OSP}$ converts a number to - in this case 4 - bytes, using unsigned big endian encoding;
$\text{Info}$ could be the ASCII string $\texttt{"V"}$ as explained above;
$\text{OKM}$ the output keying material which can be used to create a derived key

For AES the output keying material is the key, as AES simply consists of (pseudo) random bytes.

This creates a variable length output that is specific to the input keying material and the $\text{Info}$ octet string, which makes it possible to derive multiple keys for the same input keying material.

So with all that your key derivation scheme could be e.g. SHA-256(key | 00000001h | "V"). If you need more key information you can simply increase the counter to 00000002h (the point is never to use the same input for the hash of course) and concatenate the output of the result. If you need less than a full number of output blocks then you should simply use the leftmost bytes of the result. If you want to derive more information from a static key then simply introduce another counter.

KDF's are very flexible, often to the point that they are too flexible. this makes it near impossible to standardize on algorithm, so describe the one you are using well.


How to create the ciphertext that generates a desired plaintext in CBC (previous cipher- and plaintext are known) I'm struggling with understanding this part of the literature:
It can be assumed that the entire ciphertext AND plaintext is known.

Considering the encryption method is $C_i =  enc_k ( P_i \oplus C_{i-1})$ with a key k, and the decryption method is $P_i = dec_k(C_i)  \oplus C_{i-1}$.
Why does it say in equation (2) say that we can generate the desired ciphertext of the previous block this way?
Also shouldn't the equation (3) formula be: $P'_{i-1} = ...$ instead of $P_{i-1} = ...$
I don't really get equation (4) and why is it different from equation (2)?
Any help appreciated.

CBC-R
To better understand the attack on the paper, It is better to look at the original CBC-R attack to understand the above attack.

Practical Padding Oracle Attacks, Juliano Rizzo and Thai Duong. USENIX 2010

This work shows how to turn the padding oracle into an encryption oracle. With padding oracle, we can get decryption of any ciphertext.
Choose a random ciphertext $C_i$, actually, any ciphertext will work. Request decryption with the padding oracle $$P_i = Dec(C_i) \oplus C_{i-1}.$$ By controlling the $C_{i-1}$ we can turn $P_i$ to any value we want. The the target is $P_x$ than we can set $$C_{i-1} = P_x \oplus Dec(C_i).$$
As we know this will make the decryption of $C_{i-1}$ as a garbage block ( random block). But we started with a random block, too. Similarly, as the first step, request decryption then adjust the previous block;
$$C_{i-2} = P_{i-1} \oplus D(C_{i-1})$$ Here note that we request the decryption of $C_{i-1}$ with arbitrarily chosen $C_{i-2}$ then we adjust the $C_{i-2}$ so that the decryption is $P_{x-1}$. This is easy since it is just an x-or difference.
In this way, we repeat to the beginning where the last adjusted value is the nonce of the CBC mode.
This encryption oracle is very slow since it needs a padding oracle for the decryption of a block. The attack on the FPGA ( next title) is used directly by the decryption oracle and therefore it is very fast.
The Unpatchable Silicon: A Full Break of the Bitstream Encryption of Xilinx 7-Series FPGAs
When a malicious action occurs the system halts, and the WBSTAR register is left intact, then after reboot, they read the WBSTAR register that stores what was decrypted and leaks 32-bits. Repeat to reveal all. This turns this bug into a decryption oracle on the FPGA.
HMAC key can also be decrypted using the above technique using the FPGA as a decryption oracle.
The aim is to turn the decryption oracle into an encryption oracle!

Why does it say in equation (2) say that we can generate the desired ciphertext of the previous block this way?

Actually, it is the goal and they show it in the next steps. Therefore, you need to understand the next steps.

Also shouldn't the equation (3) formula be: P′i−1=... instead of Pi−1=...

Yes it should be $P'_{i-1}$

Note that  for arbitrary selected $C_i$ and $C_{i-1}$ using the decryption oracle one can find out $P_i$.
Now you want a value $P'_i$ in the FPGA and for this, you need the encryption of it $C'_i$.
$$P_i = dec_{KAES}(C_i) \oplus C_{i-1} \label{1}\tag{1}$$
If you set
$$C'_{i-1} = P_i \oplus C_{i-1} \oplus P'_i \label{2}\tag{2}$$
Then put values into equation \ref{1}
$$P_i = dec_{KAES}(C_i) \oplus P_i \oplus C'_{i-1} \oplus P'_i$$ leaves;
$$P'_i = dec_{KAES}(C_i)  \oplus C'_{i-1}  $$
CBC has the chaining so they need to modify to the beginning.
$$P'_{i-1} = dec_{KAES}(C'_{i-1})  \oplus C_{i-2}  \label{3}\tag{3}$$

I don't really get equation (4) and why is it different to equation (2)?

This is also a typo, since
$$C'_{i-2} = P_{i-1} \oplus C'_{i-2} \oplus P'_{i-1} \label{4}\tag{4}$$ leads
$$ P_{i-1} =  P'_{i-1}$$
It should be
$$C'_{i-2} = P_{i-1} \oplus \color{red}{C_{i-2}} \oplus P'_{i-1}$$

Results of the article

This turns the decryption oracle into an encryption oracle. And using this a valid HMAC can be created, to.

So, a simple bug leads to a loss of confidentiality and integrity and authentication.


Why AES 256 GCM is more preferred by email service providers / banks over the fast and efficient ChaCha20 - Poly1305? This question is based on my recent observation of preferences of  certain email service providers and banks to use AES related symmetric ciphers over the more fast ChaCha20 Poly1305 . For example Google's Gmail browser version uses AES 128 GCM but Google's Search uses ChaCha20 Poly1305  ?

Is AES 128/256 GCM in any way more secure  than ChaCha20 Poly1305 ?

Despite the fact that ChaCha20-Poly1305 uses processor friendly instructions for mobile devices, and easy to implement in software, why banks or financial institutions are reluctant to adopt it ?

Is it because of specific AES instructions on processors (as far as servers / PC/ laptops are concerned) or because they are sticking to old convention ?

AES-GCM is standardized by National Institute of Standards and Technology, the institution that drives standards for U.S. Federal agencies.

In some situations (think banking, government, large corporations) FIPS certification is desired and in order to pass FIPS certification you need to use approved algorithms.
When you check FIPS 140-2 Annex A, you see that AES-GCM is one of the approved 'security functions'. ChaCha20 Poly1305 is not.

Another reason is that ChaCha20/Poly1305 is a relatively newer design. AFAIK, it has been accepted as an IETF standard in 2015 RFC7539 while AES-GCM is a standard since 2007 (NIST SP800-38D).

Moreover, AES has been around since 2000 and this means there is a lot of IP designs that have dedicated AES accelerators which make AES-GCM very efficient.

When it comes to security, AES is a very solid cipher and I would probably prefer it over Chacha20, but on the other hand GCM mode is very brittle and prone to implementation errors (think IV abuse) and it may be considered less desirable in some implementation-related scenarios.


how many iterations of SHA3 (keccak256) hashing would be required to provide reasonable protection for the following data structure? ((A , B , C) , (D , E , F, G, H))

Where:

A is 0x0-0xF, (1 of 16)

B is 0x00-0xFF (1 of 256)

C is an 8 digit integer

D is a one of a list of one hundred words padded to 12 characters

E is a one of a list of one hundred words padded to 12 characters

F is a one of a list of one hundred words padded to 12 characters

G is a nine-digit numerical value, that could be one of 3 derived from (D,E,F) through research

H is an alphanumeric "secret" of a(hopefully but humans are lazy) secure nature

Where ABC are hashed to a 32-byte value, DEFGH to another, then both resulting values are concatenated and hashed together

These metrics are based an very pessimistic assumptions about the randomness of my inputs.

In my naive understanding that gives me 1.2289e20 permutations assuming that the "secret" can be derived from a 100 word rainbow table lol.

The objective is to make it impractical to derive hash-seed candidates in the foreseeable future.

my equally naive analysis is that at 1,000,000,000 hashes generated per second this would require a median time to match of about 1900 years per hash?

Since H is essentially a password, I would say... none.

Why? Because SHA-3 is not good for passwords, relative to alternatives, see my answer here why: Replacing the PRF in PBKDF2 with Keccak

Now, if you used a different hash function that is a different story, but you are also performing 3 hash steps, that require different security parameters. You want the outermost hash to be the most difficult to reverse, and you want the secret to be the most difficult to brute force.

Since A+B+C are small, your outer most hash must have a high iteration count. Since H is  a secret, the final hash containing it must have a high iteration count. Therefore your inner hashes can be a single iteration as long as the outer one is many. You can probably also just use PBKDF2-SHA256 with H as the password, and ((A , B , C) , (D , E , F, G)) as the salt. As for the logic behind this, it is best to look at H as the seed for your final output. A through G is now a 58.5-bit number used to derive the output from a secret.

Relative to H, your iteration count should be enough to slow the hash function down to more than 1ms, so at LEAST a million based on your calculation. Since this is a single threaded process, if you have a highly threaded system running the hash, your concurrent hash rate can be high, or you can increase the iteration count.


What does perfect mean within perfect forward secrecy and why do some cryptographers disagree with the term? In this blog post, Matthew Green says

Forward secrecy (usually misnamed “perfect forward secrecy”)...

The Wikipedia article on forward secrecy (which the same sentence links to in the blog) says

forward secrecy (FS), also known as perfect forward secrecy (PFS)...

which implies that they are the same thing and nullifies Matthew Green's statement.
Apparently Professor Green's statement is simply a personal disagreement with the term perfect
I'd be interested in knowing how forward secrecy is/isn't 'perfect',(why cryptographers disagree with perfect) and why was the term was originally attached to forward secrecy?

Forward secrecy of key-establishment (KE) protocol means, that compromising of long-term keys of parties doesn't affect secrecy of established keys in the past.
Example to clarify what PFS means.
Say parties A and B have private keys $s_B$ and $s_B$.
Today they run KE and establish a key $k_1$.
They use this key during a session, and then destroy this key.
During this session, attacker eavesdropped all the messages and remembers the transcript $T$ of the session. Obviously, $T$ includes messages of KE,
and subsequent "data" messages, encrypted with key $k_1$.
Tomorrow, attacker somehow gets keys $s_A$ and $s_B$, but not $k_1$ (because $k_1$ was destroyed and forgotten by $A$ and $B$).
And here comes PFS property of KE: even having $T$, $s_A$ and $s_B$, attacker is unable to find $k_1$ and decrypt messages hidden in $T$.
Then answering your question, why in PFS word "perfect" is ambiguous.
It's an opinion of M.Green obviously, but I will try to guess what he means.
Actually I feel pretty the same regarding this term. "Perfect" is ambiguous here.
E.g., we don't use "perfectly secure signature scheme", we just use "secure".
Moreover, in cryptography word "perfect" appears sometimes in order to describe
that some property (usually some sort of secrecy) is based not on computational assumptions, but it's perfect - i.e., unconditional and doesn't require any assumptions/hypotheses.
Examples:

perfect zero-knowledge vs zero-knowledge (which could be just statistical or computational)
Perfect secrecy of encryption - term introduced by Shannon https://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy

So, in cryptography "perfect" is usually a synonym to
https://en.wikipedia.org/wiki/Information-theoretic_security.
But for some stupid reason - not in this case (in case of KE).
So, more clear would be to have a term "Forward Secrecy", and then, additional "Perfect" would mean that it doesn't require any assumptions and it's unconditional.
But for some historic reason, in literature PFS is used for regular forward secrecy.


What's the difference between DH and DHM? Is DHM just Diffie-Hellman with Merkle added to the name?

Yes, it's the same.
Wikipedia writes on the subject:

In 2002, Hellman suggested the algorithm be called Diffie–Hellman–Merkle key exchange in recognition of Ralph Merkle's contribution to the invention of public-key cryptography (Hellman, 2002), writing:

The system...has since become known as Diffie–Hellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called 'Diffie–Hellman–Merkle key exchange' if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to the invention of public key cryptography.[7]


Effective period of Mersenne Twister generator output Mersenne Twister generator has a period of (2^19937)-1, but it is period of internal states.

Any idea what is the effective period of MT 32 bit output - period over which 32 bit output does not repeat. It has to be smaller than (2^31)-1 but I couldn't find definite answer.

Thanks

The Mersenne Twister algorithm is not a cryptographically secure algorithm. The state can be revealed if enough output is available.

However, if the internal state will repeat after $2^{19937}-1$ then obviously this is also the period of the output, even if the output is just 32 bits.

With a period it's not about when a certain output repeats once, but if the output is repeated indefinitely - in other words, you get into a cycle. Because of this the output size doesn't really matter: the repetition is on all the output put together. You can have a large period even if the algorithm outputs single bits at a time.

Note that the internal state of the Mersenne twister is not 32 bits, it's a whopping 2.5KiB. So the state is (necessarily) large.


Can a list of hashes with property $X_{n+1} = \operatorname{SHA-256}(X_n)$ loop? This is the situation:
I have a list of hashes where each hash is always the SHA-256 of the one above it.

If I keep going down the list it must at some point loop since there can only be $16^{64}$ possible SHA-256 hashes.
So at some point the hash I get has already been in the list before.

The problem is that the algorithms behind SHA-256 is above what I can currently comprehend (I'm only 17 and a part free programmer for 3 years).
But on here there seem to be a lot of geniuses so my question is:

Is SHA-256 designed to loop after exactly $16^{64}$ hashed hashes, or is there a chance it will do so before that point?

Also: If so, it would probably do multiple times.

I saw the post on $\operatorname{Hash}(x)=x$ with $p=1-\frac1e$ answered by User fgrieu, saying that we don't yet know. But if this is determined by probability is my question also answered by probability? Please let me know if I'm thinking the wrong way or give me an answer if you have one.

Is SHA-256 designed to loop after exactly $16^{64}$ hashed hashes, or is there a chance it will do so before that point?

SHA-256 behaves more or less like a random function. You can expect it to loop after approximately $\sqrt{2^{256}} = 2^{128}$ iterations due to the birthday paradox


Securely generating passwords based on a secret and a public identifier I'm trying to create a good scheme for generating passwords in my systems management scripts. What I'd like to do is have a secret key (let's say hello123), which I keep only on trusted management machines. I'd then like to combine that with a "password identifier" (for example testing-db-pass), and produce some ASCII text that can be set as the password in the service's config.

I've read about key stretching, PBKDF2 and HMAC, and it seems like using bcrypt  and passing hello123, testing-db-pass as the salt and key for those would work - but is that vulnerable to attack? Do I need to do something like HMAC-bcrypt? Is there a better way?

What I did in one of my password generators is that given a secret key $K$, public data $\text{Pub}$, I first generate a solid "master key" $K_m$ via key-stretching the secret key using PBKDF2 (any other key derivation function would work, I just happened to have that lying around):

$$K_m = PBKDF2(K, \text{salt, iterations, } \cdots)$$

And then derive individual secrets via $HMAC(K_m, \text{Pub})$ (formatting the result as required).

It is pretty straightforward, and secure, but there are a few sticky points that you need to look out for:

If your public data $\text{Pub}$ is aggregated from multiple sources (say, an identifier string + time + counter + version + other metadata), you must ensure you do not end up generating duplicate $\text{Pub}$ data from different original inputs (or you'll get the same derived password back, of course). For instance, do not concatenate strings to create $\text{Pub}$. Instead, hash them all, and concatenate the hashes. Formally, the "input data $\to \text{Pub}$" mapping must be collision-free. In practice this easily gotten wrong.
Make sure all your security parameters are properly set up (number of PBKDF2 iterations, strong hash functions are being used, all that stuff)

The advantage of using HMAC like this instead of just using PBKDF2 and messing around with the salt is that:

It scales - multiple derived secrets can be efficiently computed via a single PBKDF2 invocation, whereas your method would involve invoking the key derivation function for each derived password (which may be very slow, if you use a lot of iterations)
It is actually using the underlying cryptographic primitives properly. A key derivation function is not meant to derive a lot of individual passwords from a given secret key by changing the salt. See this question for details. This is not the case for HMAC, which is, in fact, supposed to be used like this, as its main use is to generate fingerprints of arbitrary messages with a cryptographic key (and of course you don't need to change the key at each message) .Of course, you would probably be fine, but PBKDF2 is just not meant to be used that way.
It is less susceptible to misuse. Your method has no intermediate steps, only an input and an output. This makes it difficult to reason about security properties that each variable in your algorithm has, as well as any "cryptographic barriers" that your algorithm creates (e.g. "one cannot derive the secret key from a given generated password"). This is important because when you will need to add more features to your derivation process, you will need to redo the entire cryptographic analysis again to make sure you are not fundamentally breaking anything. In the approach I suggest, the intermediate "master key" has some known security properties (for instance, the secret key cannot be compromised by any manipulation done on the master key) which means I can easily tack on additional features without fear of introducing such and such security vulnerability. If you've ever heard the term "structured programming", this is pretty much an instance of it.

Speaking of adding more features, you will probably want a mechanism to verify that you typed in the secret key right (else you will get a garbage password out which won't match what you used before). It's not obvious how to do it using your method. However, with the improved algorithm, this is fairly straightforward - generate and store a random salt $S$ which you feed to PBKDF2 to generate $K_m$, and then store $Hash(K_m)$ somewhere, enabling you to verify if whoever is in charge of the secret key typed in correctly, without compromising it (or any derived password) if this stored information is somehow leaked (this is akin to storing the hash of the key inside the file when encrypting a file, to be able to tell the user if he typed the key in properly instead of complying and decrypting garbage).

Finally, once you have your final bytes, it's fairly easy to convert them to some charset that you can use as a password. The simplest way is to convert it to Base64, which is fairly convenient and efficient. Of course since they are just bits, you can convert them to whatever you want (hexadecimal, raw ascii, a pin number, etc..)


Can you tell me why doing scalar multiplication of a point on a Elliptic curve over a finite field gets to a point at infinity? I am reading Programming Bitcoin. The author said:

  Another property of scalar multiplication is that at a certain multiple, we get to the point at infinity (remember, the point at infinity is the additive identity or $0$). If we imagine a point $G$ and scalar-multiply until we get the point at infinity.

He doesn't explain why. So I don't understand why. I would like you to give me a plain explanation, without a serious mathematical proof, if that could be possible.

The points on the Elliptic Curves $E$ over a finite field $K$ are forming a commutative additive group ( Abelian group) with the point addition as the group operation. The group needs an identity element and usually represented as $\mathcal{O}$. In most curves, this is the point at infinity and also notated as $P_\infty$. In the Edwards curves, the identity is an affine point $(0,1)$.
The scalar multiplication $[k]P$ this actually means adding the $P$ itself $k$-times. More formally;
let $k \in \mathbb{N}\backslash\{ 0\}$
\begin{align}
[k]:& E \to E\\
&P\mapsto [k]P=\underbrace{P+P+\cdots+P}_{\text{$k$ times}}.\end{align}
and by being identity $[0]P = \mathcal{O}$, and $[k]P=[-k](-P)$ for $k<0$.
Since $\#E(K)$, the number of points, on Elliptic curves over a finite field is finite if you add a point $P$ itself many times eventually you will get the identity $\mathcal{O}$.
$$\underbrace{P+P+\cdots+P}_{\text{$t$ times}} = [t]P= \mathcal{O}$$
The smallest $t$ will be the order of the subgroup generated by the $P$. For security, we want this order huge since the attacks. If we consider the  expected attack cost for Pollard's $\rho$ is $O(\sqrt{\ell})$, i.e. we need to double the point size.
Bitcoin uses Secp256k1 which has characteristic $p$ and it is defined over the prime field $\mathbb{Z}_p$ with the curve equation $y^2=x^3+7$.
The order $n$ of the base point
G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
is
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
Note 1: a point $P$ may not generate the whole group but it generates a cyclic subgroup.
Note 2: As pointed by SqueamishOssifrage, The Smart showed that if the order of the curve and order of the base field ($K$) are same then the discrete logarithm on this curves runs in linear time.


Salts, how does the script know what the salt is? I am new to PHP programming and trying to grasp the idea of hashing and encryption for protecting passwords, credit card details and such. I've done a lot of reading about MD5 which I think I understand the basics of now. I've seen places recommending that I use SHA2, which I don't understand how to implement.

Back to my question. I can understand how a script can tell if a password is correct or not by hashing the password and comparing the value against the hashed one in the database. My problem occurs when trying to understand salts. If I have a dynamic salt such as the date (yes, I have heard its a bad one to use), how does the script know that a password is correct because the salt will be different for the entered password and the one stored in the database.

For example:
Say the original password was created on the 21/02/2011:

unhashed with salt:

mypassword210211

hashed with salt:

cbc0a790b2f28fc72ca43eb749028b9f

Then if I check my password today:

unhashed with salt:

mypassword30012012

hashed with salt:

e4af7ca7e263750a15be642d903c9ac9

They're completely different, so how does the script know that they are the same? Do I have to store the salt used on the specified password in the database so it knows what to use next time?

I'm rather confused and its highly likely that I am not understanding the whole hashing process properly. I've done my research, but whether I have done correctly or not I don't know.

The salt has two main purposes as I understand it.

To ensure that two users who choose the same password, get different password hashes.

Say the CEO, and the janitor, choose the same password. Without a salt, they'd both get the same hash. This means that an attacker who managed to download the password file, could instantly see that the CEO, and the janitor, have the same password (whatever that is). So instead of putting a keylogger on the CEOs laptop, he'd just beat the password out of the janitor! Or if the janitor was the attacker, he'd instantly see that his own password, was also the CEO's - so he could log in as the CEO, without having to try multiple passwords and risk a system alert.

With a salt, the two hashes are completely different, and no attacker can possibly know that several users have the same password. Salting the passwords also ensures that users who choose the same password on different systems, get different hashes on each of those systems.

For (1), the only actual requirement, as far as I can see, is that the salt is different for different users - because even the slightest change in salt+password, will cause an enormous change in the hash thereof. So you could just use an increasing number 1, 2, 3 etc. It needn't be large, random, or secret - just different for different users.

However, in practice, when you're storing the password for a new user, you don't necessarily want to scan the other users' salts, to check you pick a different value; and you sure don't know what salts were used on other systems! So a common approach is to "take a chance", and just pick a big random number, hoping that the resultant number hasn't been picked before. The bigger the number, the less chance it has been picked before.
To reduce the chance of password cracking using rainbow tables.

Say an attacker pre-computes the hashes of a million common passwords, and stores those in a table. So the table has a million (password, hash) entries. (These are commonly called rainbow tables.) Then, when he downloads a password file, he just looks-up each of the hashes, from that file, in that table. If hash value 1234567890 matches table entry ("letmein", 1234567890), he now knows that password "letmein" will produce that hash - voila! The table takes time to generate, and space to store. But once done, it will instantly crack those million passwords - if they are unsalted.

But say each password is salted with one of (say) 1000 different values - perhaps just a number from 1 to 1000. Now the attacker has to pre-compute each password 1000 times - once for each possible salt. So the table is now a thousand times larger. Clearly, if the salt is large enough, this makes the table infeasible - it takes too long to generate, and is too large to store.

For (2), the requirement is, as I understand it, that the salt has many different potential values, and is unpredictable. If the salt doesn't have many different potential values, the table is still feasible. And if the salt is predictable, the attacker just generate a rainbow table for the predictable values, and hopes for the best!

So to meet both (1) and (2), you just pick a large random number for the salt. As I understand it, 32 BYTE salts are coinsidered the go these days.

Using the DATE as a salt is a very very bad idea. That wouldn't even achieve benefit (1) - let alone benefit (2). If I saw code that used the date for a salt, I'd not trust that code for any security related functions of any description - the author has no idea what he's doing.


Difficulty of generating a string "The (md5|sha1) hash of this string is (x)" that hashes to (x) vs. regular hash collision between files? I know that collisions in md5 and sha1 have been demonstrated in particular pairs of files (by incrementing some none viewable portion of a PDF, etc).

Would generating the above string be meaningfully more computationally difficult than generating such a collision?

Yes, it would be much more difficult to generate a string of the form The (MD5|SHA-1) hash of this string is (x) where x is (in hexadecimal or binary) the hash of that string, than it is to find collisions for MD5 or SHA-1. In fact, even though we can generate collisions for MD5 at low cost including for short messages (64-octet), I don't think that we could plug this one. Main issue is that the string x that we can change is much too small, and the rest too constrained.

However, we can easily construct a family of $2^{128}$ octet strings all with the same MD5 hash that are valid PDF documents and display any desired 128-bit value in hexadecimal, including one such document (that we can exhibit) displaying its own hash. That also works for Postscript, non-signed executables.. It would be feasible to do this for SHA-1, but that would cost about 128 times more work than what was used for one collision.

The trick is to start from a PDF document that displays a value depending on its content at 128 bits changing in 128 different local changes that each leave the hash invariant; each change involving altering 2 message blocks for SHA-1, or just 1 for MD5.

Update: That trick was pulled for a GIF image!


Is this authentication system insecure or not So I want to create a simple, fast and yet secure authentication in two steps for a PC - microcontroller communication.

The first step is a seed request, the second step is an authentication request.

The encryption that is being used is AES-128.

There should be a fixed key k with a length of 16 bytes.

Whenever a seed request is coming a random 16 bytes authentication message m should be generated and then be encrypted with k and sent back to the client as a seed s.

(NOTE: E(k, m) will always output the same s)

The seed s then should be decrypted with k by the client and then the original authentication message m should be sent to the server as an authentication request.

The server compares the auth message m with the message of the request, and grants access if they are equal or rejects the request otherwise.

Also assume that an adversary can collect as many m and s pairs as he wants.

Based on the information above is it feasible to easily break this system or not?

It is vulnerable to replay attacks since the attacker knows the plaintext and its corresponding ciphertext. To mitigate against this you might want to include some information in the message like a timestamp so that assuming time keeping isn't compromised for the server and client, outdated messages, i.e messages marked by a timestamp earlier than a certain timeframe can be invalidated.


Number of rounds for constant header size in common hashes and XOFs We compute hash $H(M_0\mathbin\|M_1)$ of size $d\ge1$ for some constant header $M_0$ of size $m_0$, and $\nu\ge1$ messages $M_1$ of random content and size $m_1$.
For Merkle-Damgård hashes, a simple optimization pre-computes the first $\left\lfloor m_0/r\right\rfloor$ rounds (where $r$ is the block size), and for some minimum extra size $\mu$, the total number of rounds computed is
$$\text{rounds}=\left\lfloor\frac{m_0}r\right\rfloor+\nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu}r\right\rceil$$
with, for some hashes:
$$\begin{array}{l|rrrl|rrrl}
\text{hash} & d&r&\mu&\text{(bits)}&\tilde d&\tilde r&\tilde \mu&\text{(bytes)}\\
\hline
\operatorname{SHA-256}    & 256 &  512 &  65 && 32 &  64 &  9 \\
\operatorname{SHA-512}    & 512 & 1024 & 129 && 64 & 128 & 17 \\
\end{array}$$
Note: The right side of the table assumes quantities are expressed in byte rather than bit. The only change to the formula is that variables get a tilde, except $\nu$.
For more common hashes and XOFs¹, what are the corresponding formulas and parameters?
I'm especially interested in common variants of SHA-3 (or KECCAK if it differs from SHA-3 other than by value of padding); SHAKE; various BLAKE; and perhaps some parallelizable hashes.
Update: I have changed notation several times to align with that in KECCAK/SHAKE for $r$ and output size $d$, and used greek letters in an attempt to avoid confusion with existing hash specifications.

¹ eXtendable Output Functions essentially are hashes where the output size $d$ is a parameter rather than fixed. An example is SHAKE256 of the SHA-3 family.

Heading
\begin{array}{l|rrrl|rrrl}
\text{hash} & d&r&\mu&\text{(bits)}&\tilde d&\tilde r&\tilde
 \mu&\text{(bytes)}\\
\hline
\operatorname{MD5}        & 128 &  512 &  65 && 16 &  64 &  9 \\
\operatorname{SHA-1}      & 160 &  512 &  65 && 20 &  64 &  9 \\
\operatorname{RIPEMD-160} & 160 &  512 &  65 && 20 &  64 &  9 \\
\operatorname{SHA-224}    & 224 &  512 &  65 && 28 &  64 &  9 \\
\operatorname{SHA-256}    & 256 &  512 &  65 && 32 &  64 &  9 \\
\hline
\operatorname{SHA-512/224}& 224 & 1024 & 129 && 28 & 128 & 17 \\
\operatorname{SHA-512/256}& 256 & 1024 & 129 && 32 & 128 & 17 \\
\operatorname{SHA-384}    & 384 & 1024 & 129 && 48 & 128 & 17 \\
\operatorname{SHA-512}    & 512 & 1024 & 129 && 64 & 128 & 17 \\
\hline
\operatorname{SHA3-224}  & 224 &  1152 &  4 && 28  & 144 &  1 \\
\operatorname{SHA3-256}  & 256 &  1088 &  4 && 32  & 136 &  1 \\
\operatorname{SHA3-384}  & 384 &   832 &  4 && 48  & 104 &  1 \\
\operatorname{SHA3-512}  & 512 &   576 &  4 && 54  & 72 &  1 \\
\hline
\operatorname{SHAKE-128} & d   &  1344 &  6 && \lceil d/8 \rceil & 168 &  1 \\
\operatorname{SHAKE-256} & d   &  1088 &  6 && \lceil d/8 \rceil & 136 &  1 \\
\hline
\operatorname{BLAKE2s-256}   & 256 &   512 & 0 && 32 & 64 &  0 \\
\operatorname{BLAKE2b-512}   & 512 &  1024 & 0 && 64 & 128 & 0  \\
\end{array}

SHA3-x
SHA3-x is defined with KECCAK as;

$\operatorname{SHA3-224}(M) = \operatorname{KECCAK}[448] (M \mathbin\| 01, 224)$
$\operatorname{SHA3-256}(M) = \operatorname{KECCAK}[512] (M \mathbin\| 01, 256)$
$\operatorname{SHA3-384}(M) = \operatorname{KECCAK}[768] (M \mathbin\| 01, 384)$
$\operatorname{SHA3-512}(M) = \operatorname{KECCAK}[1024](M \mathbin\| 01, 512)$

KECCAK
and KECCAK defined as

$\operatorname{KECCAK}[c] (N, d) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–c] (N, d)$

and note that $N = M\mathbin\|01$ and $d$ is the required output size, Now we have

$\operatorname{SHA3-224}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–448] (N, 224)$
$\operatorname{SHA3-256}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–512] (N, 256)$
$\operatorname{SHA3-384}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–768] (N, 384)$
$\operatorname{SHA3-512}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–1024] (N, 512)$

Padding

$\operatorname{pad10*1}(x, m)$  is not important since the message is not formed yet.

SPONGE

$\operatorname{SPONGE}[f, \operatorname{pad}, r](N, d)$

Let $P=N \mathbin\| \operatorname{pad}(r, \operatorname{len}(N))$.

Let $n=\lfloor\operatorname{len}(P)/r\rfloor$.

Let $c=\lfloor b/r\rfloor$.

Let $P_0, \ldots, P_{n-1}$ be the unique sequence of strings of length $r$ such that $P = P_0 \mathbin\| \ldots\mathbin\| P{n-1}$.

Let $S=0^b$

$\textbf{For } i \textbf{ from }0 \textbf{ to } n-1$
$\textbf{let } S=f (S \oplus (P_i\mathbin\| 0c))$.

...

As we can see, we can precompute a message $M$ up to the maximum multiple of $r$  that is smaller than $\operatorname{len}(M)$. More mathematically $$\operatorname{precomputableLen} = \lfloor(\operatorname{len}(M)/r)\rfloor \cdot r.$$ And the $r$ for

$\operatorname{SHA3-224}(M)$ is $r = 1152$
$\operatorname{SHA3-256}(M)$ is $r = 1088$
$\operatorname{SHA3-384}(M)$ is $r = 832$
$\operatorname{SHA3-512}(M)$ is $r = 576$

and the formula
$$\text{rounds}=\left\lfloor\frac{m_0}r\right\rfloor+\nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu }r\right\rceil$$
SHAKE128 and SHAKE256

$\operatorname{SHAKE128}(M, d) = \operatorname{KECCAK}[256] (M \mathbin\| 1111, d)$
$\operatorname{SHAKE256}(M, d) = \operatorname{KECCAK}[512] (M \mathbin\| 1111, d)$

As we can see the main difference is the capacity and extra two bits appended to have the domain separation.

$\operatorname{SHAKE128}(M, d)$ is $r =1344$
$\operatorname{SHAKE256}(M, d)$ is $r =1088$

and the formula
$$\text{rounds}= \underbrace{\left\lfloor\frac{m_0}{r}\right\rfloor + \nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu}r\right\rceil}_{\text{Absorbing part}} + \underbrace{\nu  \left\lceil \frac{d}{r} -1 \right\rceil  }_{\text{Squeezing part}}$$
BLAKE2b and BLAKE2s
BLAKE2 uses modified ChaCha as compression function with 16 words. BLAKE2s is the 32-bit version so  $r=512$ here, and for BLAKE2b $r = 1024$ ( $s$ for small, $b$ for big).
and the formula
$$\text{rounds}=\left\lfloor\frac{m_0}r\right\rfloor+\nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu } r\right\rceil$$
since BLAKE2 uses all-zero padding, they called it minimal padding.


Is my block cipher ready for the real world if it passes all AESAVS tests? If I validate my  implementation(s) of Rijndael against the  Advanced Encryption Standard Algorithm Validation System (AESAVS) specified validation testing requirements is it fit for purpose and real world use cases? Can I then state as much? What about other ciphers and their test vectors that lack NIST authority?

Based on my reading of that document, it looks like it only covers Rijndael (aka "AES"). Moreover, I would say that the AESAVS test the correctness of your implementation, but not the security.
From the linked document:

1 Introduction
This document specifies the procedures involved in validating implementations of the Advanced Encryption Standard (AES) algorithm in FIPS 197 : Advanced Encryption
Standard 1. ... This publication ... includes the specifications for the three categories of tests that make up the AESAVS, i.e., the Known Answer Test (KAT), the Multi-block Message Test (MMT), and the Monte Carlo Test (MCT).

So these tests will show that your implementation produces the correct output for a given input. They do not make any claim about whether your implementation is robust to timing attacks, or power analysis attacks, or really, any kind of attack.

So, as to

is it fit for purpose and real world use cases?

That depends, does your purpose include being secure (in addition to being correct)?


Forgery of a custom MAC I'm trying to solve a problem that was given to me. The issue I have is that I'm missing some parts to solve it.

I'm confronted with an Oracle that performs MAC on an input that can be of any length using the following function. I need to forge a message that must match the message the Oracle has computed.

$o_1 = E(k, d_1)$
$o_2 = E(k, o_1 \oplus d_2)$
...
$o_N = E(k, o_{N-1} \oplus d_N)$

therefore $MAC(k, d) = o_1 \oplus o_2 \oplus ... \oplus o_N$

where $d_X$ are block size parts of the message (ex.: message is 32 bit long = 4 x 8-bit blocks).

In order to forge the message, the Oracle offers 2 methods:

  $mac0(n)$ -> performs $MAC(k,msg)$ with msg = n x d (where d is a 8-bit block full of zeros and n is the number of block asked)

  $mac3(input)$ -> performs $MAC(k, d)$ with any input (if the input is bigger than 3 blocks, it truncates it to 3 block; if smaller, it pads the remaining parts with zeros until the input is 3 blocks long).

In the case of the example I'll use an 32-bit long input (4 blocks).

The first thing that I currently do is that I use mac3 with the first blocks which will result in $o_3$. I, then, XOR $o_3$ with the last block ($d_4$) and send the result through $mac3$ again. When comparing with the actual result from the Oracle, I find that it is not equal.

So that's where I'm stuck.. According to what I understood, this might be due to the padding done by $mac3$ since the input is not 3 block long. This is the part I don't know how to solve. Would there be a way to revert the result to find the actual forged message?

Any other ideas?

Let's say $b$ is our block size. We can easily see that if the message has the size $b$, the following holds $MAC(k, d) = E(k, d)$. So, let's first try to solve this for a single block message (let's call it $p$).

One block message

The goal is to compute $E(k, p)$, because that is $MAC(k, p)$.

The message must go through $E$ at some point. The only function that can take the message is $mac3$ (in contrast, $mac0$ takes a number). The problem is that $mac3$ takes exactly 3 blocks of input. So, our one block message $p$ has to be expanded to a three block message in some way. If we put our message block at the beginning of the 3 blocks, the first invocation of $E$ would produce $o_1$ which will be mangled in the second and third invocation of $E$. We can't do that.

What happens if we put our message block $p$ at the end of the 3 block input to $mac3$? The $o_3$ which contains the encryption of our message block $p$ will only be XORed, but not encrypted again. There we have a winner, because it is easy to reverse XOR, since we don't need a key.

Let's recap the way XOR works: if $x \oplus y = z$ then $x \oplus z = y$. Also, $x \oplus x = 0$ and $x \oplus x \oplus y = y$. We're going to need it.

Back to our problem. We can control $o_3 = E(k, o_2 \oplus d_3)$ to be our MAC of our one block message if we can control $o_2$. This is where $mac0$ comes in.

What happens if we set the 3 block message to $0^b | 0^b | p$ where $|$ means concatenation and $x^b$ means to repeat $x$ $b$-times?

$o_1 = E(k, 0^b)$
$o_2 = E(k, o_1 \oplus 0^b) = E(k, o_1)$
$o_3 = E(k, o_2 \oplus p)$
$m = o_1 \oplus o_2 \oplus o_3$

We know that $o_1 = mac0(1)$, but that isn't enough to control $o_2$, because we don't know key $k$. What exactly is $mac0(2)$ then? ...

$o_{1,m2} = E(k, 0^b) = o_1$
$o_{2,m2} = E(k, o_{1,m2} \oplus 0^b) = E(k, o_{1,m2}) = o_2$
$m_{m2} = o_{1,m2} \oplus o_{2,m2} = o_1 \oplus o_2$

From that, we can calculate $o_2$:

$$o_2 = o_1 \oplus m_{m2} = mac0(1) \oplus mac0(2)$$

OK, now we control $o_2$. We still want to calculate $E(k, p)$. So let's set $d_3 = o_2 \oplus p$. This leads to

$$o_3 = E(k, o_2 \oplus d_3) = E(k, o_2 \oplus o_2 \oplus p) = E(k, p)$$

OK, now we're nearly there. The final MAC is $m = o_1 \oplus o_2 \oplus o_3$. Since we already know $o_1$ and $o_2$ from before, we have

$$m = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus p\right) \oplus mac0(2) = E(k, p)$$

Multi-block message

The last formula contains the way how $E(k, p)$ can be calculated for any single-block message $p$. This can be used to calculate the intermediate values $o_x$ if the composite message.

Let's say, our message is

$$d = d_1 | d_2 | ... | d_N$$

Then the final MAC can be calculated as

$o_1 = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus d_1\right) \oplus mac0(2)$
$o_2 = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus o_1 \oplus d_2\right) \oplus mac0(2)$
$...$
$o_N = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus o_{N-1} \oplus d_N\right) \oplus mac0(2)$
$m = o_1 \oplus o_2 \oplus ... \oplus o_N$

Here is the (untested) Java code for this.


Discrete logarithm over prime modulo: small input, large exponent, larger prime I am considering using modular exponentiation as a one-way hash function. More specifically, here is the scenario.

1) Input ($m$): the input messages are small (16-bit)

2) Exponent ($e$): the exponent is a 160-bit integer, chosen only once, and randomly; the exponent is not public

3) Prime ($p$): a 2048 bit safe prime, chosen only once and is public

The hash of the message is then computed as: $h=m^e$ mod $p$.

My question is whether there exists efficient algorithms to compute the exponent $e$ given a certain $h$, especially since there are only $2^{16}$ possibilities for $m$?

Since attacker does not know $m$, he can't directly apply discrete logarithm methods. On the other hand, small message space allows to run discrete log algorithm on each possible $m$.

There are subexponential algorithms for dlog, but I am not sure if they are directly applicable here. But the general BSGS algorithm will find $e$ in $sqrt(e)$ operations, so for each $m$ candidate we need $~2^{80}$ operations to find some possible $e$ (total $~2^96$ complexity). Notably, most of the wrong candidated for $m$ will not yield any $e$ so this can also be used to "unhash" your "hash". Though complexity is quite high, there are high chances that more effective discrete logarithm can be applied.

Another note: assuming you use odd $e$, this "hash" leaks some information about the message: Legendre symbol (e.g. if the message is quadratic residue mod p or not).

PS: It's not completely clear how you are going to use it and why your attack model assumes only knowledge of $h$, not $m$ (since even then finding $e$ is hard). But this confuses as it may seem that you want also to hide information about $m$, which is really a bad idea here.


Why do we assume un-security of communication channel on every cryptography system While reading about a few cryptographic systems, I noticed that we always assume the communication channel is not secured. Why is this assumption made?  And, why the effort is being put into designing cryptographic systems rather than working on making these communication channels more secure? I know the question is basic, but really cannot find a complete answer.

The goal of cryptography is to create these secure communication channels. However, keep in mind that a secure channel is more than just an encrypted channel. A secure channel should be able to provide confidentiality (using encryption), data integrity (using something like signatures), and data authentication (using something like certificates, MACs). The goal of cryptography is to create these properties to make a "secure channel" out of an unsecured channel.

Note that some cryptosystems build on top of other types of channels. For instance, in public-key cryptography, you generally need to assume that you have access to a authenticated channel for key exchanges (which is a stronger assumption than a completely unsecured channel).


Is $E′(k,m)=E(0^n,m)$ semantically secure? $(E,D)$ is a (one-time) semantically secure cipher where the message and ciphertext space is $\{0,1\}^n$. $E'(k,m)$ is defined as

$E′(k,m)=E(0^n,m)$

The question is whether $E'(k,m)$ is (one-time) semantically secure?

I thought that the random chosen key $k$ might be $0^n$, therefore the adversary cannot distinguish the messages $m0$ and $m1$ when encrypted with the key $0^n$. Therefore, the scheme is semantically secure. However, the answer states that

  To break semantic security, an attacker would ask for the encryption of $0^n$ and $1^n$ and can easily distinguish $EXP(0)$ from $EXP(1)$ because it knows the secret key, namely $0^n$.

Can you elaborate on the answer more? I don't understand how the key is known ("because it knows the secret key") and how we can find that the messages $0^n$ and $1^n$ should be used to break the semantic security (Can we try the whole message space?)?

The algorithm $E'(m)=E'(k,m)=E(0^n,m)$ is defined with a hard-coded key, thus the key is part of the algorithm definition of $E'$.

Because of Kerckhoff's principle we generally assume the attacker to know our algorithm definition.

Because of this, the attacker can just try decrypting the challenge ciphertexts of the eavesdropper security game himself (or try encrypting the challenge messages himself if encryption is deterministic).

The choice of the messages $0^n$ and $1^n$ is entirely arbitrary and any message would suit the purpose here with these two having the advantage of the shortest possible description (instead of something like $0^{n-1}||1$).


Why is Blakley secret sharing in finite space? The paper says it requires a finite space. I wonder what the reason is, since from my understanding it should be perfectly fine to use the "normal" infinite space.

So why does Blakley use a finite space? Is there a possible attack in infinite space?

So why does Blakley use a finite space?

There are multiple reasons:

It is really inconvenient to use and represent infinite sets with computers, because the representation takes a potencially infinite amount of storage.
If you use floats or doubles for representation, then you also have to fight the problem of rounding errors, which are especially notorious in linear algebra when you are solving linear systems of equations, potentially preventing you from learning the accurate secret even if you have all the shares.
There is very few practical downsides to using finite spaces, especially as you can use finite fields of arbitrary size with exact precision rather easily.

However, I think that for theoretical / mathematical purposes the restriction to finite spaces is not needed though I haven't checked whether this fact is used in the security proof for perfect security somewhere.


Why pairing based crypto is suitable for some particular cryptographic primitives? Why pairing based crypto is being widely used in some special crypto primitives as ID based crypto and variations of standard signatures? I mean taking as deep as possible what makes it suitable for that schemes while other schemes do not feet?

Crypto based on cyclic groups is (at a very high level) about "hiding" things "in the exponent" and then manipulating those values as they live in the exponent. As an example, in a cyclic group $\langle g\rangle$, you can "hide" a random value $x$ as $g^x$.

Without a bilinear pairing, all you can really do "in the exponent" are linear/affine (degree-1) combinations of these hidden values. That is, given $g^{x_1}, \ldots, g^{x_n}$, you can obtain $g^{a_0 + a_1 x_1 + \cdots + a_n x_n}$ for known coefficients $a_i$.

With a bilinear pairing, you can do degree-2 combinations. This is huge, it allows you to "multiply hidden values together in the exponent". This extra expressivity is what lends itself to a wider variety of cryptographic primitives, like identity-based and functional encryption, etc.

There are other tools like lattices that also have a lot of algebraic structure. The capabilities of lattices are somewhat incomparable to those of groups with bilinear pairings. But more of these "functional encryption" applications are now being achieved using lattices as well. So none of these applications are probably unique to bilinear pairings, it is a bit of a historical accident that we have seen an explosion in techniques and applications of bilinear pairings.


Safety of a pre-keyed DH-Key Exchange Asuming this scenario:

Bob and Alice each have the public key of the other party for a D-H function and want to exchange data.

Now, if they each generate their shared secret, is it safe to assume that:

They can exchange messages safely without the fear of a MITM
Can reuse the shared secret n times

And what would be a estimated count for how many messages may be exchanged before the need for new public and private keys arises?

If Alice and Bob both use static DH keys, they only have to perform the DH operation once to get their shared secret. The number of messages that are safe to exchange encrypted with something derived from that shared secret is not really a function of the DH problem, except to the extent that the size of the modulus and of the private keys put a limit on the maximum security strength of the shared secret.

However, there are other factors that might entail such a limit, such as whether or not they exchange nonces for the key derivation from the (calculated once) shared secret, which symmetric cipher they use for bulk encryption, which mode of operation is used, etc.

Another thing that might entail such a limit is their confidence in the key management of both Alice's and Bob's private key. If either private key is compromised, this will mean complete loss of confidentiality of all messages sent encrypted with a key derived from a shared secret calculated using that key. Again, this is a key management issue and not a security issue specific to static DH in any way, but it might be mentioned as the reason why there exist various hybrid schemes that mix long term asymmetric keys with ephemeral asymmetric keys.