about entropy and random number generator I am reading an article about cryptography of information and Pseudo Random Number Generator. The article said using 1$28$-bit entropy PRNG is safe in some cases of cryptography. I am not familiar with this field. But after doing some research, I got some understanding listed as follows (correct me if it is not correct)

entropy is used to measure how random the information is. One typical definition of entropy is the Shannon entropy which is defined to as $$H(F) = -\sum P(x) \log_2(P(x))$$ So if the information is carried by 128-bit data so each bit is occurred at probability $P(x)=1/2^{128}$, thus the entropy is 128.
I read several posts and they comes with a conclusion that PRNG does not add or increase entropy.

So based on above 2 points, can I say that a $n$-bit entropy PRNG is basically a random generator with initial state chosen as $n$-bit data not the algorithm of PRNG per se (assuming the PRNG implementation takes $128$-bit data of course). Is that correct?

If it is true, my question is as follow:

Should I get any $128$-bit data as initial state will make it result from PRNG random enough or that $128$-bit data should be prepared in specific way ?

Yes, this is correct. (up to the typos that "so each bit is occurred at" in 1. should read "so each 128-bit value occurs at", and that the unit "bit" is missing at the end of that sentence; as well as the not-mentioned assumption that every time a 128-bit value is randomly picked, its value is independent of the choices take before). If the state of a cryptographically secure PRG is exactly 128 bit, then it's not allowed to "loose" any entropy during operation to be 128-bit secure, and it has to be seeded by a perfectly uniform random source.

The problem is how to choose the initial state. An attacker should have only a chance of $2^{-128}$ to guess the initial state, as (s)he could otherwise just calculate the output of the PRG (after guessing the initial state) to predict its output. So you have to find a way to pick a uniformly distributed random 128-bit value for the initial value, which is a real problem: you need a random source (that cannot be observed by the attacker) and a way to extract 128 bit entropy.


ECDH security when no KDF is used Let's suppose our device performs ECDH with a fixed, unknown, private key $\text{prv}$.

It accepts as input any point $Q$ lying in the proper subgroup of the proper elliptic curve, then computes: $P = \mathit{prv}*Q$ and outputs $P$.

An attacker who:

has access to $P$
can choose any valid $Q$ as input
can call ECDH many times

can gain any information about the private key $\mathit{prv}$ ?

If not, then why a KDF is usually used on the x-coordinate of $P$ ?

Is it just to better distribute the possible outputs (since about half of possible x-coordinate won't be valid points on the curve) ?

NOTE: no smallgroups/invalid curve attacks or bad elliptic curves are considered here.

Maybe it doesn't help to recover the private key, but the private key is seldom the object of interest in a real application—instead, your private conversations, your money, etc., are the objects of interest.  Hashing the points is important for security of the composition of ECDH with another cryptosystem.  This is both for the benefit of the downstream cryptosystem, and for confidence in the DH security.

Standard encoding of uniform random curve points into bit strings is a bad way to get a uniform distribution on bit strings—so bad it was one of the first problems publicly reported about Dual_EC_DRBG in a comment by Gjøsteen[1] before everyone realized there was a back door.

Maybe the related-key attacks of Biryukov and Khovratovich on AES-256[2] don't specifically apply to the encodings of points satisfying $y^2 = x^3 + a x + b$ on your curve, but it's more confidence-inspiring to choose a distribution on keys much closer to uniform with a better hash function like HKDF-SHA512—you don't have to think about possible interactions.  For instance, what if you're using a curve over a binary field, and you use the key for a polynomial evaluation MAC over the same binary field?
Use of a standard hash function like SHAKE128 justifies using the standard argument of Bellare and Rogaway converting a decisional oracle into a computational oracle[3].  The cost of breaking the system can be studied by studying the costs of implementing the computational Diffie–Hellman problem of inverting $g^{x y}$ rather than the potentially easier decisional Diffie–Hellman problem of distinguishing $(g^x, g^y, g^{x y})$ from $(g^x, g^y, g^z)$ for uniform random $x, y, z$.

Maybe you don't believe in the random oracle model, but it is hard to imagine that the hashing step—whose cost is negligible compared to the elliptic curve scalar multiplication you just performed—could make the attacker's job easier; this argument suggests that it generally makes the attacker's job much harder.

E.g., Cheon's attack[4][5] (paywall-free) computes the secret exponent $x$ given $g, g^x, g^{x^2}, \dots, g^{x^d}$ in $O(\sqrt{p/d} + \sqrt d)$ group operations where $p$ is the order of $g$ and $d \mid p - 1$, or $O(\sqrt{p/d} + d)$ group operations if $d \mid p + 1$.  An oracle for $h \mapsto h^x$ can be used to find these powers of $g$ by iterating it, while an oracle for $h \mapsto H(h^x)$ cannot.

Consequently, the security conjecture of X25519 by Bernstein[6], for example, is that an adversary who knows everyone's public key $\operatorname{X25519}(n_1, 9), \operatorname{X25519}(n_2, 9), \dots$, and has oracles for $q \mapsto H(\operatorname{X25519}(n_i, q))$, can't do much better to generically break cryptosystems downstream of $H(\operatorname{X25519}(n_i, \operatorname{X25519}(n_j, 9)))$ than paying for the energy to compute $2^{125}$ curve additions needed by Pollard's $\rho$.


OTP from Sony BIOS password recover From Dogbert's blog:

  Sony has a line of laptops ("Vaio") which compete mainly in the high value market segments. They implemented a master password bypass which is rather sane in comparison to the rest of the bunch:

  The randomly generated master password is only stored in RAM, e.g. it's lost after the next reboot ("one time password").
  RSA is used for encrypting the password which is then converted to a human-readable form (4x4 characters/8 bytes/64 bits).
  Their customer support apparently allows for one free password generation per device which is pretty decent by the industry standard.

Dogbert claims he was able to factor the password used to encrypt the OTP key because Sony used a key lenght of 64bits. And did this using an unoptimized python implementation of a general number sieve in less than a minute.

I was not aware that such small key length was even possible for RSA (I think pycrypto will not allow anything below 1024).

With a key (D63K-XFVF-TK7H-RJKX) and a password (43878945) is it really that easy to figure out the scheme used? How should I approach the problem?

[UPDATE]

  First of all, RSA works for any size modulus. 10 bits, 32 bits, 64 bits, 1 million bits. I'm having a hard time seeing exactly what the question is. You are given the key (D63K-XFVF-TK7H-RJKX). Is that key the RSA key? That key then encrypts the password (43878945)? Or is that key the result of encrypting the password with RSA? – mikeazo 2 days ago

@mikeazo: it is a challenge-response theft protection. Type the wrong password 3 times and you will be presented the 16 character challenge. You call Sony customer support, fax them a proof of purchase and based on the challenge they will give you a password. You can't brute-force it because it changes every time.

@Schwartz: of course, Dogbert disassembled the Sony Vaio BIOS and got the public key! Calculating the private key was the easy step... I was not thinking like a hardware hacker, thanks!

If they pad the key with some fixed value and apply RSA directly to it then it is just a textbook RSA scheme which is vulnerable to meet-in-middle attack: it runs roughly in time $2^{40}$ and requires $2^{32}$ space.


Why is the permutation in AES (and other ciphers) not random or key-dependent? If the permutation in AES (or other ciphers) were randomly generated or dependent on the key, would it not be stronger against differential attacks?

If this is so, then might we need fewer rounds for the same level of security?

You have clarified the question as asking about whether replacing ShiftRows with a random byte permutation would strengthen AES against differential attacks.  It would not.

ShiftRows and MixColumns were carefully selected to work in tandem, such that every byte affects every other byte in the state within just two rounds.  MixColumns ensures that every column of four bytes has a minimum of five differentially active bytes before and after that step (i.e. if you add the differentially active bytes in the column before MixColumns to the active bytes in the column after MixColumns, the number is at least 5).  ShiftRows ensures that every column after the step includes a byte from every column before the step.

Together, the two steps operate to put a high lower bound on the number of differentially active s-boxes over 4 rounds:  the AES creators proved that a minimum of 25 s-boxes are active over 4 rounds, minimizing the probability of any differential characteristic/trail.

There are alternatives to ShiftRows that do the same thing (see e.g. the cipher SQUARE which swaps columns and rows).  But a random byte permutation would likely not ensure such a high minimum number of active s-boxes over as few rounds as ShiftRows.


Could we use a more efficient hash for signature generation? Is it possible to use a more efficient hash - such as one based on GHASH - instead of a cryptographic hash for signature generation?

In other words, could a combination of a fast hash and the private key operation together provide the security that we expect from a cryptographic hash? Could such a scheme be proven to be secure assuming that the underlying primitives are secure?

As mentioned in the comments already, you do not need collision resistance. You can get away with target collision resistance (TCR). The security game for TCR considers families of hash functions and requires the adversary to select the message it will find a collision for before it learns under which function of the family it has to find it. This is applicable in hash-and-sign signature schemes where you have a fixed length signature scheme that works without first hashing the message (like RSA) and then add a hash function to handle arbitrary length messages by signing their hash (like RSA-FDH). With TCR, you select a random function index and sign it with the hash.

One problem here, if you want to go for standard model security, is that the function indexes (keys) have to have length logarithmic in the message length. At least we do not know any domain extenders for TCR better than this. However, I will omit the details. A "heuristic" construction is the RMX construction by Halevi and Krawczyk.

For Fiat-Shamir based constructions like (EC)DSA things are not that easy as you cannot just "additionally" sign the index. What you can do however is to reuse the random nonce (think of $g^r$ in Schnorr) as index as pointed out by Mironov  in this paper. Actually, that paper discusses a lot of the things I just wrote in more detail.

If you want to go weaker you start getting to run into issues. If you use the hash to compress the message you are signing, you need some sort of collision resistance (which TCR is). At least, you definitely need second-preimage resistance (which one might also consider a variant of collision resistance as you actually output a collision...). If your hash is not second-preimage resistant a malicious party, after seeing a message signature pair, can always come up with a colliding message for which the signature is valid.


Is there a construction for a variable length block cipher that uses a fixed length one? I'm looking for some way to take a fixed length block cipher (for example AES) and turn it into a variable length one with comparable security. The new length may be bigger or smaller than the underlying block cipher's.

I'm considering going about this with an unbalanced feistel network, but I'm asking if there's an already accepted way to do this.

Yes, there is standard work on this. You should see "On the Construction of Variable-Input-Ciphers" by Bellare-Rogaway (PDF). They give definitions and constructions.


How can an amateur introduce a cryptographic algorithm? I have a new cipher, and I want to get it properly vetted, but I don't have a strong way to prove its security properties.  I'm an amateur without ties to a strong cryptographer/university.  I have attempted a few indistinguishability proofs, but these are "back of the napkin" proofs and are likely not rigorous.  (I have colleagues that have done cryptanalysis on it, but they are not theorem types.)

As a result, I feel that I don't stand a chance of getting it published without a proof of security, but I feel that I can't find someone to help without it being published.

How can I find someone willing to join on and help write a compelling proof, and generally help write a compelling paper, (or identify a weakness that prevents me from doing something stupid with the cipher)?

Given that I have done these things:

Review previous ciphers, find they're not what you want, invent new cipher
Internally analyze it (plots, prototype code, etc.)
Socialize it to cryptanalyst peers, get tentative green light (rather, absence of red light - no new findings in a while)

Is this a reasonable path going forward:

Brief it at an IACR rump session
Have follow-on discussions at conference, express my need, find someone that way
Submit as a work-in-progress in lower tier, but bonafide crypto conference
Submit as a journal article

Is a rump session a good way to go to find interested math types, and/or as a first step to announcing the idea?  Are there other alternatives, such as quarterly meetings of some group that might be willing to hear the idea?

Similarly, is there a good "starter conference" for crypto open to new ideas that might lack the mathematical rigor?

In contrast to this thread, How to publish a cipher (concept), the main answer suggests that formalisms are a prerequisite to publishing: "If you submit a cipher, one would expect at least a formal analysis of why you think this is a good idea."  My question is what if you don't have that ability - how do you find someone that can help with that?  The rest of the answers on the thread went into how to make it into a bachelor's thesis.

In additional defense of this thread, there are many great suggestions that don't appear on that other post.  While I'm biased - but have nothing to gain - these threads are unique.  I'm okay with marking as duplicate as long as somehow you can merge the useful answers below into the other question.

First, if it's a secret-key cipher, then you'll never find any proof of security—at best you'll, exhaust the standard cryptanalysis techniques and exhaust the brilliant ideas of the brilliant cryptanalysts.  If it's a public-key cryptosystem, then at best you can prove reduction to a widely understood uniformly hard problem.  If you're not already familiar with these facts, you won't get the attention of serious cryptanalysts.

Second, you need to convincingly demonstrate (a) that you understand the standard cryptanalysis techniques, and (b) that it does not fall to them.  Cryptanalysts don't want to waste time doing your homework.  If you haven't already done your homework, you won't get the attention of serious cryptanalysts.

There's no good textbook of which I'm aware on this subject, but you might start with

  Bruce Schneier, ‘Self-Study Course in Block Cipher Cryptanalysis’, Cryptologia, 24(1), January 2000, pp. 18–34.
  https://www.schneier.com/academic/archives/2000/01/self-study_course_in.html

Third, if you want this to be anything more than an amusing intellectual exercise for bored cryptanalysts whose attention you've gotten, your cryptosystem has to fill a niche that nothing else does.  Is it faster or lower-energy on some significant platform than every other cipher providing comparable security?  Does it fill a specific need that no other cipher does, like a weird block size that is important for some particular reason?

For example, Gimli is a sponge with a much smaller state than Keccak-f1600, conveniently fitting in registers on more platforms, out of which one can build all manner of secret-key crypto gizmos.  (Gimli is a very new design, with some preliminary theoretical cryptanalysis.)

If you propose a general-purpose stream cipher that's not faster than software ChaCha or hardware AES-CTR, or a general-purpose collision-resistant hash function that's not faster than software BLAKE2b or hardware SHA-3, you won't get the attention of serious cryptanalysts who aren't either just bored or hoping their novel pet cryptanalysis techniques that failed to break the aforementioned ones might break something.

This applies even to designs that already have been published: Maybe RIPEMD160 resists collisions better than SHA-1 does, but it's not worth the time of most cryptanalysts to study it.  Maybe CAST6 is a better 128-bit block cipher than AES, but it's not worth the time of most cryptanalysts to study it.

Finally, if you want to get the attention of cryptanalysts, don't start with your cipher—start by showing that you are a competent cryptanlyst by using novel techniques to break crypto!  Best if you can break existing cryptosystems that were previously unbroken, or break them worse than the best published attacks.  This may be easier if you study cryptosystems that have received relatively little attention, including your own.

If you have a write-up demonstrating all of this—either a description of a novel cipher with evidence of resistance to standard cryptanalytic techniques and a reason to be interesting, or a novel cryptanalytic attack on an existing cipher—then a first step would be to submit it to the IACR cryptology eprint archive.  That won't impart the kind of serious review that, e.g., the AES and SHA-3 competitions did, of course, but it may catch the notice of some cryptologists and will be easier to show to someone whose review you are seeking, and if you do get the attention of a serious academic cryptologist they will likely have followup suggestions for publication venues.


Practical attack on md5 hashing algorithm? I have the following conditions:

String which consist of "STRING+key+ID+key" is hashed with md5. I have a knowledge of STRING (10 chars), ID is probabilistic (int 15), key is 15 chars long (a-z A-Z 0-9) and it's same on both occurrences. I can produce multiple hashes but without knowledge of key.

I guess collision is not going to work in this case as STRING is appended at the beginning and ID between keys. Is there actually any other option then brute force.

Produced hash is used as some kind of integrity check so you cannot alter the parameters. Key is hardcoded on the both sides (frontend and backend)

POST:
{"STRING":"ASDFGHJKLM","ID":"123456789012345","hash":"md5hash"}

Passwords, $p$, when only secured with a hash function $H$ on the database as $H(p)$ for login systems, is vulnerable to finding pre-image or secondary pre-image attacks.

Secondary pre-image : given $ H(p)$ find $p' \neq p$ s.t  $H(p)=H(p')$.

The famous rainbow tables are generated to more effectively find the pre-image or secondary pre-images. To countermeasure the rainbow tables, salt is one of the solutions.

As I can see from your problem there is a salt and these prevent the rainbow attacks.

As a result, you cannot benefit from the salts.

The only choice is the brute force.

And as you noted;

AWS p3.x16 has the power of 450GH/s.


Is MAC-then-encrypt with stream ciphers secure? While thinking about this recent question about a hash-then encrypt design, I reread the MAC-encrypt vs. encrypt-MAC question and noticed this answer quoting a paper showing that MAC-then-encrypt is secure with stream ciphers, even if not generically.

However, there's this attack when the MAC is deterministic and the cipher a stream cipher (or a block cipher in e.g. CTR or OFB mode, or even a OTP):

Assume the attacker knows the authenticated plaintexts of two different equal-length messages: $m_1||MAC(m_1)$ and $m_2||MAC(m_2)$.
The attacker intercepts the ciphertext of a third equal-length message: $E_k(m_3) = S_k(n) \oplus (m_3||MAC(m_3))$, where $S_k(n)$ is a unique keystream from nonce $n$.
The attacker can now modify the message in flight to $S_k(n) \oplus (m_1||MAC(m_1)) \oplus (m_2||MAC(m_2)) \oplus (m_3||MAC(m_3))$.
With a high probability, that is only a valid message when $m_3$ matches either $m_1$ or $m_2$, which the attacker could learn from whether the receiver e.g. asks for a new message (assuming corruption) or accepts it. If it was one of those two messages, it becomes the other instead.

This seems to both give the attacker information on the original message $m_3$ and allow them to forge communications.

Is there something wrong with the attack (e.g. did I assume too much) or is this just a lesser break than the paper (pdf) from that answer considers?

As correctly pointed out in a comment, the authenticated encryption model assumes that

the attacker knows the algorithm;
the attacker can query the encryption oracle with any plaintext $P$ (and a unique nonce $N$) and get MAC-then-Encrypt ciphertext $C$;
the attacker can query the decryption oracle with any string $C$ pretending to be a ciphertext.

No other data is available to the attacker. The assumption you made that the MAC alone is available is too strong.


How Does Prime Factorization Break ECDSA? I have heard that ECDSA will be broken in the not-to-distant future (roughly 15-25 years) by Quantum Computers running Shor's Algorithm. However, to my understanding, the only purpose of Shor's Algorithm is quickly finding the prime factors of very large numbers. Though time consuming, such factorization is by no means impossible on modern computers. The prime factors of public keys on the Secp256k1 curve can be found in a matter of hours with the proper algorithm. Is there a formula capable of deriving a private ECDSA key from a public one if the prime factors of that public key are revealed, or is there some other aspect of factorization which poses such a great security risk? I have been unable to find any information on the means through which these quantum attacks would be capable of breaking public key encryption despite the great concern over it. Any explanation, especially with mathematical examples, would be greatly appreciated.

However, to my understanding, the only purpose of Shor's Algorithm is quickly finding the prime factors of very large numbers.

Your understanding is incorrect. Shor's Algorithm is usable for both factoring integers and finding discrete logarithms.
Shor's algorithm works in two parts. First, it turns the problem (factoring or discrete log) into one of finding the period of a function. This first step is non-quantum. Then it finds the period using the Quantum Fourier Transform (QFT). Once you have the period of the function the first step can be reversed to find the solution to the original problem.
Shor's algorithm can be used without the Quantum part and simulating the QFT, though then it will be substantially slower than the best known classical algorithms. This python implementation simulates the QFT and may aid understanding.


ECDSA Compressed public key point back to uncompressed public key point From the ECDH demo here, if I generate a private key for Alice I can get _

P = 1175846487558108474218546536054752289210804601041

Which gives the following public key point.

X = 583857549063195252150226340830731484791130788759
Y = 1195037839477751118658084226553581900533276838164

For ECDSA public key compression the above coordinates would be prepended by 02 and the X coordinate would be used. So the compressed key for the above (based on X9.62) is:

02583857549063195252150226340830731484791130788759

If I only have the compressed key given above, how would I derive Y i.e. the uncompressed point?

All points on an elliptic curve verify, by definition, the curve equation, usually written as $Y^2 = X^3 + aX + b$, with two given $a$ and $b$ parameters (these two parameters actually define the curve). So, if you know $X$, you can use the curve equation to recompute $Y^2$. A square root extraction will yield $Y$ or $-Y$. The compressed point format includes the least significant bit of $Y$ in the first byte (the first byte is 0x02 or 0x03, depending on that bit): this bit is enough to know whether you got $Y$ or $-Y$ with the square root, and adjust in consequence.

All computations above are done in the base field, i.e. (usually) the integers modulo a prime integer. See this for square root extraction modulo a prime.

Edit: for binary curves, things are somewhat similar. We work in a field $GF(2^m)$, so addition is a XOR; the curve equation is $Y^2+XY = X^3+aX^2+b$ (generic equation for non-supersingular curves). When point $P = (X,Y)$, the opposite point is $-P = (X,Y+X)$. We assume that the point we are encoding and decoding has coordinate $X \neq 0$, because a point with such a coordinate $X = 0$ is equal to its opposite, i.e. has order $2$. In practice, when we work on such a curve, we really use a sub-group of order $r$ prime (generally, we arrange for the complete curve order to be equal to $2r$ or $4r$).

Since $X\neq 0$, we can define $Z=Y/X$, and divide the curve equation by $X^2$. This yields:
$$ Z^2+Z = X+a+\frac{b}{X^2} $$
Thus, given $X$, we can compute $Z^2+Z$. From that value, we can compute the two solutions, which are $Z$ and $Z+1$ (see below). Since $Y = XZ$, this yields $Y$ and $Y+X$, thus the points $P$ and $-P$.

This gives us the compression method for curves in binary fields: from $(X,Y)$, compute $Z=Y/X$; the compressed point then consists in $(X,z_0)$, where $z_0$ is the least significant bit of $Z$. When decompressing, you use the equation above to recompute $Z^2+Z$, then $Z$ (the knowledge of $z_0$ tells you which of the two solutions is the right $Z$), then $Y = XZ$.

To know how to solve for $Z$, we need to define the trace and the half-trace. We are in $GF(2^m)$; the trace of a value $x$ is:
$$ \mathrm{Tr}(x) = \sum_{i=0}^{m-1} x^{2^i} $$
We are in a field of characteristic $2$, which implies that squaring is an automorphism: $(uv)^2 = u^2v^2$ and $(u+v)^2 = u^2+v^2$ for all $u$ and $v$ (this is called the Frobenius automorphism). Moreover, for all $u$, $u^{2^m} = u$ (this is analogous to Fermat's little theorem, because the non-zero elements of $GF(2^m)$ are a multiplicative group of order $2^m-1$). This implies two important characteristics of the trace:

The trace is linear: for all $u$ and $v$, $\mathrm{Tr}(u+v) = \mathrm{Tr}(u) + \mathrm{Tr}(v)$.
The trace of any $u$ is either $0$ or $1$. Indeed, for all $u$, $\mathrm{Tr}(u^2) = \mathrm{Tr}(u)^2$ (by the Frobenius automorphism), and also $\mathrm{Tr}(u^2) = \mathrm{Tr}(u)$ (try it in the equation that defines the trace). Thus, for all $u$, $\mathrm{Tr}(u)^2 = \mathrm{Tr}(u)$. The equation $x^2=x$ is a polynomial equation of degree $2$, so it can have only (at most) $2$ solutions in a field, and $0$ and $1$ are solutions. Therefore, $\mathrm{Tr}(u)$ can only be $0$ or $1$.

Let's now define the half-trace. For now, I suppose that $m$ is odd (this is the normal case for binary elliptic curves, e.g. NIST curve B-233 is defined in $GF(2^{233})$). For any value $x$, the half-trace of $x$ is:
$$ H(x) = \sum_{i=0}^{(m-1)/2} x^{2^{2i}} $$
That is, we take the equation for the trace, but we keep only half of the operands in the sum.

Like the trace, the half-trace is linear. Also, for any $x$, we can see that:
$$ H(x)^2 + H(x) = \mathrm{Tr}(x) + x^{2^m} = \mathrm{Tr}(x) + x $$

Let's get back to our equation $Z^2+Z = \beta$ where $\beta = X+a+(b/X^2)$. Since the trace is linear, and since for $Z$ and $Z^2$ have the same trace, it follows that $\mathrm{Tr}(\beta) = \mathrm{Tr}(Z^2+Z) = \mathrm{Tr}(Z^2)+\mathrm{Tr}(Z) = 0$ (remember that addition is XOR in $GF(2^m)$). Thus, the equation can have solutions only if $\mathrm{Tr}(\beta) = 0$. Then, we have $H(\beta)^2+H(\beta) = \beta$, so the solutions for $Z$ are $H(\beta)$ and $H(\beta)+1$.

If $m$ is even (this will often be the case if using pairings over binary curves, although this is probably not a good idea since discrete logarithm in binary fields is a lot easier than previously expected), then most of the above hold, although we need another definition for the half-trace. Basically, we need a constant element $w$ such that $\mathrm{Tr}(w) = 1$, and we can define the half-trace as:
$$ H(x) = \sum_{i=0}^{m-1}\left(\sum_{j=0}^{i} x^{2^j}\right)w^{2^i} $$

In both cases ($m$ odd and $m$ even), the half-trace is linear, so it can be computed as a XOR of some precomputed values for the bits equal to $1$ of the source. This is rather inexpensive. The trace is even easier: it is simply a XOR of some of the input bits, and, in practice, often a XOR of very few of these bits.


What is the difference between LCG and Affine cipher? What is the difference between LCG and Affine cipher?

More specific: What are they used for, and what are the structural differences between them?

A LCG -- linear congruential generator -- is used to generate a sequence of pseudorandom numbers. Therefore, it takes the previous output to calculate a new number:

yi = (a*yi-1+c) mod N

With an Affine cipher, in contrast, you can encrypt and decrypt. You can convert your text to a number; for example, character for character "A"->0 "B"->1... "Z"-> 25

To encrypt a message m you use the following formula:

c = (a*m + b) mod N


why IPSec transport mode is restricted for host-to-host communication , or host-to-gateway where gateway acts as a host only? Transport mode is allowed between two end hosts only; tunnel mode is required when at least one of the endpoints is a "security gateway" (intermediate system that   implements IPsec functionality, e.g., a router.)
But in case all addresses are public and scalability is not an issue, why transport mode IPsec SAs cannot be used between two security gateways ?

That's because IPsec transport mode reuses the same IP header as both the 'outer header' (that is, the IP header that appears in front on the encrypted IPsec packet), and the 'inner header' (that is, the IP header that's the plaintext packet).

Suppose Alice wants to send an encrypted packet to Bob (who may be a security gateway); that packet must have an IP header with Bob's IP address as the destination (because, if it doesn't, the network won't forward the packet to Bob).  Then, Bob decrypts the packet; if he (and Alice) were using transport mode, he retains the IP header.  Hence, the decrypted packet will still have Bob's address as the destination.  Then, if Bob is a security gateway, who does he forward the decrypted packet to?  Well, the packet says that Bob is the destination, and so Bob it is (and even if Bob decides to ignore that rule, he doesn't have any idea who the real destination ought to be).

Now, actually, this isn't entirely true; there is a workaround.  I have seen cases where Alice and Bob use a tunneling protocol between the two.  In that case, you really can use IPsec transport mode.  What Bob will do is, once he decrypts the packet, removes the tunneling header, which may expose the real plaintext IP header.  Then, Bob knows who to forward the decrypted (and detunneled) packet to.  This works; IMHO, this really is only a slight variation on tunnel mode, however apparently it does have some sort of advantage in some cases...


ElGamal and Paillier key sizes for short messages I am using ElGamal and Paillier schemes to encrypt a large number of short messages: typical 4-byte integers. I do this for the homomorphic properties of these schemes.

However, the way the encryptions work, with, say, a 1024-bit key a 4-byte integer will blow up into two values of overall size of 4096 bits or 512 bytes, which is, well, mildly inconvenient :)

As I deducted from examining the ECRYPT II report, the recommended key size for ElGamal is at least 1024 bits. I did not find recommendations for Paillier, though. However, as I understood, these recommendations are typically for larger messages. Hence, some questions:

1. Is there a difference in choosing a key length based on the size of a message?

2. What would be acceptable key sizes in the situation described above for both cryptosystems? If possible, I would like references to analyses I could read.

Bonus question: Let's assume an adversary gets a hold of an array of encrypted integers and tries to crack the encryption. How would he be able to determine whether he found a proper private key or not, if we assume that he is unable to tell a properly decrypted array from a random array?

You should not use keys smaller than 1024, and even 1024 is considered too small today. However, if you want additive homomorphism, then you can you encrypt with "ElGamal in the exponent" over Elliptic curves. To explain what I mean by this, let $G$ be the base point (generator) for the Elliptic curve group, let $x$ be the ElGamal private key, and let $P=x\cdot G$ be the ElGamal public key. Then, you can encrypt a value $m$ by computing $(r\cdot G,r\cdot P + m \cdot G)$, where $r$ is random.

Note that given $(U_1,V_1) = (r\cdot G, r\cdot P + a \cdot G)$ and $(U_2,V_2)=(s\cdot G, s\cdot P + b\cdot G)$, it follows that $(U_1+U_2,V_1+V_2) = ((r+s)\cdot G,(r+s)\cdot P + (a+b)\cdot G)$. Thus, this is additively homomorphic.

The only problem with this scheme is that you cannot efficiently decrypt, since this requires solving the DLOG problem over Elliptic curves. However, if you are only encrypting 4 byte integers, then you can brute force decryption using the private key as follows: given $(U,V)$, for every $a$ check if $V=x\cdot U + a\cdot G$. If yes, then you know that this is an encryption of $a$. Now, this will take $2^{32}$ time which is too long. However, you can use this idea and run a generic DLOG algorithm that takes square-root time (e.g., Pollard's rho algorithm) to do this in time $2^{16}$. It is still expensive, but may be OK for your application (depending on what you want to do).

Using Elliptic curves, the size of your ciphertext can be significantly reduced. E.g., with curve P256, you can hold a ciphertext in just over 512 bits.


Is the one-time pad secure if the key is computed so the ciphertext will consist only of "A"? I recently learned about the one-time pad method, which has perfect security if the following conditions are met :

The key must be truly random.
The key must be at least as long as the plaintext.
The key must never be reused in whole or in part.
The key must be kept completely secret.

As a thought experiment, I wondered : what if you choose the key so the ciphertext will only be "A"s (or whatever other letter) ? This would break the rule n°1, since the plaintext is not random and the key is linked to it. Does that mean that such a ciphertext can be broken ?

You're missing the goal of a one-time pad: it's a key generated and distributed ahead of message transmission.
When using a one-time pad, the only secure time to exchange the pad is ahead of time. The message itself is encrypted with the pad to make up for the lack of a safe communications channel.
By computing a "one-time pad" such that the ciphertext is a fixed content, you are moving pad generation from "ahead of transmission" (when we have a secure channel) to "at transmission time" (when we do not).
You now need to send your "pad" instead of your "all As" message. This means that you have turned your pad into a message and have no secure channel to send it.


What are the typical instance parameters of non-commutative cryptographic schemes? Recently, I grew a tremendous interest for public-key cryptography based on "groupoids", and collaborated with someone on this topic. What I notice afterwards, is that there had been a huge body of work on "non-commutative" cryptography, with a book from 2011 dedicated to that topic titled "Non-commutative Cryptography and Complexity of Group-theoretic Problems" written by A.Myasnikov et al. (published by American Mathematical Society), although I haven't gotten access to its content yet.
Obviously, non-commutative cryptography had not been matured to the stage where they'd get hash-sign-numbered standards like PKCS#1 for RSA, SEC#1 for elliptic-curve, and EESS#1 for NTRU.
What this question asks is, what are the typical parameters proposed for non-commutative cryptographic schemes? What're their typical cryptogram sizes?

The most common proposals around non-commutative cryptography have been around braid groups. Its proponents have struggled to find parameter sets that are agreed to resist security analysis. Recent proposals have included the algebraic eraser key establishment system and WalnutDSA, a signature scheme that was entered in the NIST post-quantum crytpography process, but failed to pass the first round.
I don't know if there are currently any proposed parameters for the Algebraic Eraser scheme, but this 2016 paper gives a cryptanalysis of the scheme proposed for ISO/IEC 29167-20 standardisation (the standard was not published). The Algebraic Eraser authors' response is also available.
The WalnutDSA submission can be found on the website of the NIST process (the WalnutDSA website link no longer works), as can the cryptanalysis that led to its non-progression.


Cryptography system that limits the length of the encypted message I have two devices which communicate via sms.

This communication should now be encrypted.

The devices can only send messages with the lenght of 160 characters.

So i am looking for an encryption system which can limit the length of the encypted message to 160.

Is there such a cryptography system?
Which system that meets this requirement is the safest?

As encryption scheme that could only encrypt fix length message is a important essence in cryptography, e.g. one-time pad.  Block cipher is a better example, e.g. AES is a popular block cipher whose block size is 128 bits.  While given such block cipher who could only encrypt 128-bit string, you can construct encryption scheme that encrypt arbitrary length string.

The security of the encryption scheme is not determined by the length of message but by the length of the key.  For example, AES has variant using 128-bit, 192-bit, 256-bit key.  AES-256, who use 256-bit key, is considered to be safer.

Finally, for ultimate security, you should use one-time pad.  One-time pad is information-theoretically secure which means the most powerful adversary can not break the cipher.  The disadvantage is the key could be only used once.  You could store multiple keys in your devices.  10MB space could store more than 60000 pre-shared keys, which sustain 60000 secure SMS message.


Is it possible to reverse the birthday attack calculation? I find that for every 100 password salts in our database, we only average 94.73 distinct salt values (averaged over a total of around 18 million). Is there a way to take that observation and calculate the amount of effective entropy (or whatever is the correct term) we have in our salts?

Clearly we need to improve how we generate salts. But, meanwhile, I'd like to better understand the theory behind the observation.

EDIT: I have asked this question aimed at correctly generating our password salts.

It is possible to reverse the birthday bound calculation. You can get an easily computable approximation using the expected number of collisions:

If you had random $n$-bit salts, after $k$ values you would expect $2^{-n}\binom{k}{2}$ collisions. If the collisions are rare, they are mostly single collisions, so there are approximately $u = k-2^{1-n}\binom{k}{2}$ unique, non-colliding values. So your results $k = 1.8 \cdot 10^7$ and $u \approx 1.7 \cdot 10^7$ could be generated with $n \approx 28.3$. That is, they could be random numbers between zero and 340 million, give or take.

More exact formulas are found in the answers to this question Neil Slater linked in the comments. With your numbers they give an answer of around 27.3. This makes sense, because the approximation above ignored multi-collisions, which leave more unique values than estimated.

However, that does not imply they have 27-28 bits of entropy. They could have considerably less. For example, they could instead be the results of a counter that wraps around after ~17500000 items. There is no way to know with just the data you gave. They very likely do not have more than about 28 bits of entropy each, however.


Can we do modulus switching for number theoretic encryption? Can we do modulus switching for number theoretic encryption such as Paillier or ElGamal?

Security goals like confidentiality is the reason to ask for encryption.
Modulus is chosen (for particular group types) on the grounds of hard problems associated with that groups; encryption strength is defined by level of hardness of that problems.

It would be nice to discover a hard problem related to some change of modulus, comparable to indistinguishability of Diffie-Hellman tuples of 4 group elements for ElGamal or $n$-th roots for Paillier with modulus $n^2$.


How is the AddRoundKey operation performed in AES-256? Can anyone explain to me (or send a link to somewhere) how round keys are added in AES-256? I understand that the round keys is added to the state matrix for each round and how XOR works. But since the state matrix is always 128 bits, how do you add an 256 bit round key?

I might be confused on a higher level right now...

how do you add an 256 bit round key?

Actually, each round key is 128 bits, and so XORing them into the state matrix is easy.

What the AES key expansion process does is take the 256 bit AES key, and generate 15 round keys (one more than the number of AES rounds).  Now, for AES256, the first two round keys are, in fact, 256 bits taken directly from the AES key.  After that, it computed the next round key based on a simple function of the previous two round keys (plus a per round constant).


Security of one-time-pad without $\bmod $ operation? Assume $r_1,r_2$ are used only once, and picked uniformly at random (each time we want to mask a value) from finite field $\mathbb{F}_p$, where $p$ is a large prime number. Assume $r_i\neq0$ and $b$ is a (non-zero) fixed element of the field. Let $(r_i)^{-1}$ be multiplicative inverse of $r_i$.

Imaging there is a client  $B$ and a server.
The server does  some homomorphic operation on an encrypted value and then provides $c=E_{pk_{B}}(r_1\cdot b)$ to client $B$. Where the cipchertext space is much larger than $p$.

So the plaintext may overflows in field $\mathbb{F}_p$, in other words  $r_1\cdot b$  may not be in the field $\mathbb{F}_p$. Therefore, there is a rick that client $B$ after decrypting learns something about $b$. So we want to force client $B$, after decrypting the message performs $\bmod p$.

To this end, we compute $c'=E_{pk_{B}}(r_1\cdot b \cdot r_2\cdot (r_2)^{-1})$.

Question 1: Given $c'$, can client $B$ learn anything about $b$ after decrypting the ciphertext before it performs $\bmod p$ operation?

Simpler version: Given $r_1\cdot b \cdot r_2\cdot (r_2)^{-1}$ without involving $\bmod p$ operation can a semi-honest party learn anything about $b$ ?

Given $c'$, can client $B$ learn anything about $b$ after decrypting the ciphertext before it performs $\bmod p$ operation?
Given $r_1 \cdot b \cdot r_2⋅(r_2)^{−1}$ without involving $\bmod p$ operation can a semi-honest party learn anything about $b$ ?

These would appear to be the same question; it's just that in the first question, $B$ is handed a ciphertext for which he has the decryption key for;.
The answer: obviously, yes.  If $r_1 \cdot b \cdot r_2⋅(r_2)^{−1}$ happens to be relatively prime to a prime $q$ (for example, $q=3$), then the attacker knows that $b$ also is relatively prime to $q$.  This doesn't immediately tell him the value of $b$; however it allows the attacker to deduce what $b$ is not.
If the attacker can factor $r_1 \cdot b \cdot r_2⋅(r_2)^{−1}$, he can then put together a short list of plausible values for $b$; however it is likely that $b$ and either $r_1$ or both of $r_2, r_2^{-1}$ have large enough prime factors to make this intractable (this assumes that $b$ was ultimately chosen in a way that didn't favor smooth numbers).
However, if the attacker is given two such encodings of the same $b$, $r_1 \cdot b \cdot r_2⋅(r_2)^{−1}$ and $r'_1\cdot b \cdot r'_2⋅(r'_2)^{−1}$, then he is in luck; he can compute $\gcd( r_1 \cdot b \cdot r_2⋅(r_2)^{−1}, r'_1\cdot b \cdot r'_2⋅(r'_2)^{−1})$, and that's $r$, multiplied by a (likely small) integer.


Usage difference between x86 RDRAND and RDSEED Modern x86 CPUs often have the RDRAND and RDSEED instructions for hardware generation of random numbers.  I just don't understand the difference between them.

Intel has this document: https://software.intel.com/en-us/blogs/2012/11/17/the-difference-between-rdrand-and-rdseed

But I don't understand how this affects the usage of RDRAND and RDSEED.  Namely, in what situations can I use each, for features like generating an encryption key, or for initial seeding of a PRNG?

As for the possibility of an NSA backdoor, that really isn't an issue for us.

The processors come, at a first approximation, with three components:

A hardware noise source;
A pseudorandom generator that's periodically seeded from that noise source, whose output is available through the RDRAND instruction;
A true random generator that's driven off the noise source, whose output is available through the RDSEED instruction.

Intel's longer documentation has some explanations and a number of useful diagrams, which in turn refer to NIST's documents on random bit generators (SP800-90A, B and C).  But if I were to summarize the security goals of these two instructions, I think they are this:

No bit of the output of RDSEED should be predictable to a computationally unlimited attacker who observes any other output bits at any other time.
No bit of the output of RDRAND should be predictable to a computationally limited attacker who observes any other output bits at any other time.

But some such bits might be predictable to a computationally unlimited attacker under some circumstances.

In practical pseudorandom generators, even ones that reseed themselves periodically from fresh entropy input, it's generally the case that output bits are predictable from nearby bits, given enough computational effort.  For example, Intel's document tells us that their implementation of RDRAND uses NIST's CTR_DRBG algorithm.  This algorithm uses a block cipher in CTR mode to produce blocks of output data in caller-requested sizes, and the generator is only reseeded between output blocks.  So given a sufficient fragment of such a block, a brute force key recovery attack can predict the rest of the block with a better than chance success rate.

The document also tells us that both instructions use an "AES-CBC-MAC Based Conditioner" to process the output of the hardware entropy source.  This concept is explained in NIST SP800-90B (second draft) (p. 5):

  The optional conditioning component is a deterministic function responsible for reducing bias and/or increasing the entropy rate of the resulting output bits (if necessary to obtain a target value).

Basically, AES is here being used in a mode that, given true random but biased inputs, produces less biased, true random outputs.

Intel's document doesn't go at length about the "ENRNG" ("Enhanced Nondeterministc Random Number Generator," Intel's own term) used by RDSEED, but they refer us to NIST SP800-90B and SP800-90C.  Looking at the latter in particular suggests that this "ENRNG" might also use AES, but again in a mode that maps true random inputs to true random outputs.  There doesn't seem to be enough information to tell exactly what's going on here, but reading between the lines I'm guessing it's one of the NRGB ("Nondeterministic Random Bit Generator") constructions from SP800-90C, section 9 (pp. 32ff), which combine the true random output with that of a pseudorandom generator in an entropy-preserving fashion, as a practical safety mechanism:

  The advantages of using these NRBGs include the following:

  If the underlying DRBG mechanism in the NRBG has been instantiated securely, and the entropy source fails in an undetected manner, the NRBG will continue to provide random outputs, but at the security strength of the DRBG instantiation (the “fall-back” security strength), rather than providing outputs with full entropy.
  Small deviations in the behavior of the entropy source in an NRBG will be masked by the DRBG output.


Looking For Additively Homomorphic Encryption I have a construction that requires as primitive an Additively Homomorphic Encryption scheme that does not rely on hidden group order, meaning I can't use Paillier.

I now have two different instantiations of that primitive:

Additive ElGamal, with its issue of small message space.
Regev scheme based on LWE, which have bad parameters once you try to do homomorphic additions with a modulus bigger than 2.

My question is the following:

Do you know of some Encryption scheme which is not based on hidden group order and is additively homomorph for a bigger message space?

This probably doesn't actually qualify as leveled-homomorphic, since it doesn't extend nicely.

For integers $n$ and positive integers $m$, define $\operatorname{smod}$ ("signed mod" or "symmetric-ish mod")

by $\;\;\;\;\; (q\hspace{-0.04 in}\cdot \hspace{-0.04 in}n)+r \: \operatorname{smod} \: m \;\; = \;\; r \;\;\;\;\;$ for integers $r$ such that $\;\; -(m\hspace{.02 in}/2) < r \leq m\hspace{.02 in}/2 \;\;\;$.

(B and $m$ are  positive integers; B is a parameter, and vertical bars represent absolute value.)

The following is an encryption scheme that is significantly-additively-homomorphic over $\: \mathbb{Z}\hspace{.02 in}/m\mathbb{Z} \:$:

the secret/private key is a natural number $s$ that is coprime to $m$, and each reduction value is generated as $m \cdot e + s \cdot r$, where $e$ is a random element of {-B,-(B-1),...,B-1,B} and $r$ is a random element of a somewhat-large range of positive integers.

The decryption of a ciphertext $\:$ctext$\:$ is $\;\;($ctext $\operatorname{smod} s) \operatorname{mod} m \;\;\;$.

The secret/private key-holder can encrypt by outputting  $m \cdot e + s \cdot r + $ plaintext $ \operatorname{smod} m$, where $e$ is a random element of {-B,-(B-1),...,B-1,B} and $r$ is a random element of a somewhat-large range of positive integers.
The "noise" of such a ciphertext is at most $\:($B$\cdot \hspace{.02 in}m)+\big|$plaintext $\operatorname{smod} m\big|\;$.

Anyone with a large-enough set of reduction values can encrypt by sampling a subset $S$ of the reduction values such that $S$ does not have too many elements, choosing a non-zero integer $a_s$ for each element $s$ of $S$, and outputting
$\sum_{r\in S}s\cdot a_s+$ plaintext.
The "noise" of such a ciphertext is at most $|S|\cdot $B$ \cdot m + |$ plaintext $\operatorname{smod} m |$.

Homomorphing is done by applying the same integer linear combination to the ciphertexts as is desired on the plain texts.
The "noise"s of the resulting ciphertexts are at most $\sum_{\text{ctext}}\text{ctext}$'s noise $\cdot |\text{ctext}$'s coefficients$|$.

The reduction of a ciphertext $\text{ctext}$ by a reduction value $r$ is $\text{ctext} \operatorname{smod} r \;$.  The "noise" of such a reduced ciphertext is at most $\text{ctext}$'s noise $+$ B$\cdot m \cdot \lceil \frac{\text{ctext}}{r}-\frac{1}{2} \rceil$

As long as the upper bound on noise given by the relevant [[sentence about noise] in the previous paragraph] is less than $s/2$, decryption of the outputted ciphertext will yield the right plaintext.


Given $n$ bits, how many "truly random" sequences/numbers can be constructed? Suppose we have $n$ bits, so we can have $2^n$ different bit sequences. Some sequences don't look random, say, all $1$ or $0$. There are also other patterns like $10101010…$, $11001100…$ and such.

I'm not certain but aren't there ways to evaluate a given sequence as random with some given satisfied error? Given $n$ bits, how many "truly random" sequences/numbers can be constructed?

Update: The main question is we have $n$ events (coin flips). $n$ considered to be big enough. Now we want to know are those events random or not and we apply NIST suite for this.

As $n$ events cant be represented as $2^n$ number, we can have a function
$F(n)$, which gives 0 if NIST suite for given bit sequence represented by $n$ fails to satisfy and gives 1 if $n$ looks like random.

Question is what is sum $F(n)$ over all $n$? Approximately, for sure. And yes, NIST is just an example. Take any test which can by applied for given bit sequence.

I'm not certain but aren't there ways to evaluate a given sequence as random with some given satisfied error? Given n bits, how many "truly random" sequences/numbers can be constructed?

If you define "truly random" as meaning prior to generating the sequence, that each bit has an independent 50% chance of being 0 or 1, then all $2^n$ bit strings are equally likely. By that definition you can reject none of them.

So, there is not a way to "evaluate a given sequence as random". However, some random data may contain detectable signals. Good RNGs produce these signals sometimes because they are in the set of all possible results. Badly-constructed software RNGs produce these detectable signals more frequently than by chance. A well-known example of a bad RNG like this is the randu generator.

The NIST tests, and those like it (I've used the Dieharder suite for a PRNG), do not detect randomness. Instead they detect signals in the noise. If a RNG produces a clear "FAIL" signal for every (or nearly every) sequence that it produces, then it is considered a poor RNG, because an attacker who wanted to predict its output could use knowledge of that signal to reduce the amount of guessing they need to do to (to figure out a secret key, for instance).

If a good RNG produces a "FAIL" signal every now and then, then this is  not very meaningful. In fact you normally just set a p-value for the test, and a good RNG will fail with that exact probability each time you use that test against its output. You could even run a meta-test, where a good RNG can be expected to generate a certain number of failures from a test. In that case, you need to define a p-value for the meta test, which of course the generator might fail, and you could have a meta-meta-test . . .

If a specific sequence produces a "FAIL" signal from a test like one of the NIST suite, this is generally meaningless. Ideally, you should go back to your source and generate another sequence to see if that signal is consistently appearing in its output - i.e. you should test your RNG source, not the sequence itself.

You cannot meaningfully say: "This sequence is not random."
You can meaningfully say "This RNG is predictable."

It is still possible to assess a large enough individual sequence against the NIST tests or similar, and to declare it fit for some purpose or other. For instance, perhaps you have an RNG which you don't trust (it could hardware fail, or might be tampered with)? In which case you could decide to reject "suspicious" outputs from it. There is no fixed standard for that. You get to decide where to set the bounds. Worse than that, by filtering out test "FAIL" sequences, you make the output less than truly random. However, as that would be by some small factor - perhaps 5% of sequences might get rejected - it would not give an attacker much of an advantage, so it is something you could consider if you had good reason - such as a real possibility of someone tampering with your system's RNG.

This sort of sequence rejection is close to your proposed $F(n)$. You would have to implement a specific version of it before you could answer "what is sum $F(n)$ over all $n$?". You would want to keep that value as high as you can whilst cleanly rejecting sequences that represented hardware failure, tampering, use of incorrect RNG, or other failure modes that your test was protecting your system against. Allowing a low value - e.g. accepting only 1 in 10 attempts as being "random enough" - would make your RNG process less efficient, and might make your RNG more predictable to an attacker.

You could look at analysis like the Receiver Operating Curve if you need to quantify how well your system disambiguates systemic failure of the RNG compared to normal variation in a good RNG. Optimising the area under the curve would be a sign that you have a good series of tests, then you can set test p-values depending on the risks associated with false positives (rejecting random data) versus false negatives (accepting tampered data, or from a bad RNG).

If we take a very naïve view of the NIST test suite, we can set upper and lower bounds of "Sum $F(n)$ over all $n$" as follows:

There are 15 separate tests listed on NISTs web site.
You arbitrarily set a rejection p-value of 0.01 for your test, and reject any sequence that fails 1 or more tests.
The proportion of sequences that pass any single test is almost exactly 0.99 - by definition, you are rejecting 0.01 of anything that could happen.
A lower bound on your value is when each test finds a mutually-exclusive set of "suspicious" bit strings. That would suggest "Sum $F(n)$ over all $n$" > $0.85 * 2^n$

This is not a correct assumption, but it does set a lower bound. This is quite an encouraging value, since rejecting 15% of sequences from a perfect RNG does not give an attacker much to work with, and you have clearly included obvious failure modes such as all bits 0 or 1, and many repeated patterns.

An upper bound on your value is when each test finds the same set of "suspicious" bit strings. That would suggest "Sum $F(n)$ over all $n$" < $0.99 * 2^n$

This is not a correct assumption, because otherwise there would be no point in having the separate tests.


Partially Homomorphic Cryptographic Schemes - Deterministic vs Probabilistic While reading this paper I realized that textbook RSA was the only deterministic PHE scheme mentioned. I did cross-check the ones listed in the Wikipedia article also and, quite on the opposite direction to this question, I could not find any of them to be deterministic. Now, I am aware that, as drLecter points out in the answer to the question previously linked, the deterministic ones are weaker and are to be avoided. However, I would be very interested in knowing whether any other PHE scheme exists aside from RSA. I think it might be the reason why it is the only one I've seen where the operation is the same (modular multiplication) in the Plaintext and Ciphertext space.
Also, trying to respect the original notation on RSA's homomorphism but emulating the figure 2.1* of the paper which of these 3 diagrams would be more correct?

*I linked a cached version of the paper 'cause the only pdf I found gets directly downloaded when clicking the link. Unfortunately the figure 2.1 cannot be seen on the cached version, here is the link  for the actual pdf.

Yes, there exist other deterministic PHE schemes. Actually, you can turn any probabilistic PHE into a deterministic one. This is achieved by deriving the random coins for the encryption deterministically from the message to be encrypted, e.g., by computing the random coins as a hash of the message (using a suitable hash function compatible with the randomness space of the encryption scheme).

Moreover, the determinism of the PHE is not related to whether the operation on plain- and ciphertexts are identical (a simple counterexample is ElGamal encryption, which is a probabilistic PHE, and uses the same operations on plaintexts and ciphertext components).


Known vs. Chosen (plaintext and ciphertext) and RSA I want to know whether I can break RSA (textbook) with known plaintext/ciphertext attacks.

Known plain-text

Let $c$ be the ciphertext and $m$ the plaintext.

$$c = m^a \mod n$$

Since all I have is the plain and ciphertext, all I could do here is guess the decryption exponent $a$ until I find one that leads turn $c$ into my known $m$.

Known ciphertext

In this case, I would have to factor $n$ (hard) in order to find $p$ and $q$.

Is the above correct? I would appreciate if someone could point the right direction.

I'm not exactly certain what answer you're looking for; I tried to cover all the obvious bases.

Actually, with RSA, we generally assume that the attacker knows the public key (the modulus $n$ and the public exponent $e$); with that, he can encrypt as much plaintext as he cares to (by selecting a value $M$ and computing $M^e \bmod n$). So, in that sense, the term 'known plain-text attack' doesn't apply, as we assume the attacker can do a chosen plain-text attack.

As for the variant "what if the attacker has some plaintext/ciphertext pairs, but doesn't have the public key; what can he do?  Actually, it turns out that if the public exponent isn't too large, the attacker is in luck; if the attacker takes two known plaintext/ciphertext pairs $P_1, C_1$ and $P_2, C_2$, he can compute $gcd( P_1^e - C_1, P_2^e - C_2)$ for plausible public exponents; if he guesses the correct one, that value will be $k\cdot n$ for some integer $k$ which is extremely likely to be small.  That gives him the public key.

As for guessing the decryption exponent, well, I suppose that the attacker could try, but he's not likely to have success.  It is known that knowledge of encryption and decryption exponents is equivalent to factoring; that is, if you know $e$ and $d$, you factor $n$ (and if you know how to factor $n$, you can compute $d$ given $e$). Hence, guessing the decryption exponent is hard; if it wasn't, the problem of factorization wouldn't be easier.  (And, if you're asking "why can't you step through all the possible possible private exponents", the answer is that $d$ is generally only a few bits smaller than $n$; if $n$ is 1024 bits, $d$ might be 1020 bits; that's rather too many possibilities to step through).

As for a literal "ciphertext-only attack", where an attacker is given some ciphertext without either the corresponding plaintext or the public key, well, on the face of it, that looks to be difficult; however we generally don't assume that attackers are hobbled in such extreme ways.


Is the commitment $g^u\cdot x$ with $x\in\langle g\rangle$ and $u \gets \mathbb{Z}_n$ hiding and binding? Consider the following commitment scheme, where $x$ belongs to $\langle g\rangle$ and $u$ is uniformly chosen from $\mathbb{Z}_n$:

$$\mathsf{commit}(u,x) = g^u\cdot x$$

Is it binding and hiding?

The scheme is clearly hiding: the value $g^u\cdot x$ distributes uniformly at random when $u$ is.

However, it is not at all binding: for a given commitment $c$, the sender, assuming he can compute inverse of an element in the group, can find many pairs, more accurately, as many as the size of the group, $u,x$ for which $c=g^u\cdot x$.


Polynomial representation of the affine part of the AES S-box I have been reading up on the polynomial representation of the AES Sbox (PDF: “Essential Algebraic Structure Within the AES”  by Murphy and Robshaw) and I can't get it to produce the correct output.

Maybe I have a thinking mistake somewhere along the way, so here's what I did:

I picked a random byte: 10010101. This corresponds to $x^7 + x^4 + x^2 + 1$ in the AES-field, or $95_{16}$ in hexadecimal
I used the lookup table at Wikipedia to see what the solution should be: $2a_{16}$, or in binary 00101010 ( $ x^5 + x^3 + x $ ). I also computed it by hand with the matrix to get intermediate results and such.
I converted the coefficients of the interpolation polynomial from hex to bytes to polynomials and computed the interpolation polynomial mod the Rijndael polynomial. I used Sage to do this… my code is at the very bottom.
The result I get from this is not the result the Sbox yields. It's also not an intermediate result, nor do I get the right result when I use an intermediate result as input.

Where did I go wrong?

Sage code:

$R.<x>$=PolynomialRing(Integers(2))
f = x^8 + x^4 + x^3 + x + 1
a = x^7 + x^4 + x^2 + 1
l0 = x^2 + 1
l1 = x^3 + 1
l2 = x^7 + x^6 + x^5 + x^4 + x^3 + 1
l3 = x^5 + x^2 + 1
l4 = x^7 + x^6 + x^5 + x^4 + x^2
l5 = 1
l6 = x^7 + x^5 + x^4 + x^2 + 1
l7 = x^7 + x^3 + x^2 + x + 1
l8 = x^6 + x^5 + x + 1
s = l0*a + l1*(a^2) + l2*(a^4) + l3*(a^8) + l4*(a^16) + l5*(a^32) + l6*(a^64) * l7*(a^128)
q = s % f
print(q)

Your code is an attempt to implement the function $f$ which is a polynomial representation of the $\text{GF}(2)$ affine part of the S-box of the AES (usually referred to as $A$). Function $f$ is described on page 7 of the paper and your coefficients seems to be OK.

Your code is mapping $\text a$ to $\text q$ such that $\text q=f(\text a)$.
You're however missing a huge part of the AES S-box, that is, the inversion in $\text{GF}(2^8)$. What you actually want is to map $\text a$ to $\text q$ such that $\text q=f(\text a^{-1})$ where the inversion takes place in your ring $\text R$. Note that you must handle the special case $0$ aside...


What schemes support atomic decryption+reencryption What encryption schemes support this workflow?
Vendor encrypts and publishes information for the client

Client generates public and private key
Vendor encrypts private information
Vendor publishes that

ENCRYPT(PRIVATE_INFORMATION, CLIENT_PUBLIC_KEY) --> Publish

Client re-encrypts for benefit of a third party

Client generates re-encryptor using its own private key and third party's public key
Client publishes that

CREATE_REENCRYPTOR(CLIENT_PRIVATE_KEY, THIRD_PARTY_PUBLIC_KEY) --> Publish

Third-party decrypts data

The third-party decrypts the data

Other people

Nobody can decrypt PRIVATE_INFORMATION unless they have the THIRD_PARTY_PRIVATE_KEY or CLIENT_PUBLIC_KEY.

I know that the asymmetric scheme supports most of this workflow. However, it violates requirement 7. Is there another scheme that fully supports this workflow?

The blockchain network Nucypher offers something like that, through their cryptographic scheme, with a help of semi-trusted proxies. The scheme is secure as long as proxies don't cooperate, enough proxies don't reveal the secret and enough proxies stay online. They have papers on their website.


Scheme to verify AES key was correctly encrypted for public key recipient In our file sharing scenario there are three participants: $A$, $B$ and $C$. Each participant has a public-private key pair (let's assume RSA for now). $A$ wants to share a symmetric AES key $k$ with the other participants. $B$ is given access to the file for free, while $C$ has to pay a fee for it. Thus, $A$ may potentially cheat $C$ by providing a wrong key $k'$, and $B$ should be able to act as an arbitrator in case of dispute.

The sequence is as follows:

$A$ first shares the AES key $k$ with $B$ by encrypting it with $B$'s
public key and makes it available to $B$. Now $A$ and $B$ have access
to the symmetric AES key.
Then, $A$ shares the same key $k$ with $C$ by encrypting it with
$C$'s public key, making the ciphertext available to all
participants.
$B$ should now be able to prove that the ciphertext
provided to $C$ is indeed the key $k$ encrypted with $C$'s public
key.

This would be possible by using textbook RSA, where the ciphertext is deterministic. Since textbook RSA is insecure, this is not an option. I take it that this is similar to key escrow schemes/verifiable encryption, but I've been unable to figure out a scheme/crypto implementation for the proposed scenario.

This would be possible by using textbook RSA, where the ciphertext is deterministic

You have the right idea there, that a deterministic scheme is the way to go. However note that every scheme is deterministic if you explicitly fix the randomness used.

So suppose you encrypt $k$ for $C$ as $c=\operatorname{Enc}_{\text{pk}_C}(k;r)$ using $C$'s public key and the randomness $r$. Now for the arbitration you give $k$ to $B$ who checks that the $k$ actually is the correct one. Then you have $C$ send the received $c$ (call it $c_C$) to $B$ and have $A$ send the sent $c$ (call it $c_A$) along with the randomness $r$ used for the encryption to $B$. You could possibly encrypt the randomness here using $B$'s public key. Then $B$ re-computes $c'=\operatorname{Enc}_{\text{pk}_C}(k;r)$ using the received randomness and its own known $k$ and checks whether $c'$ matches $c_A$ and $c_B$. If it matches at least $c_B$ then $A$ was honest (because then $B$ got the right key). If it only matches $c_A$ then either of $A$ or $B$ is lying but we don't know which, because $B$ could have produced its own ciphertext and sent it to $B$ or $A$ could have produced a correct ciphertext for $B$ but sent a bad one to $C$. I don't think there is a way to resolve this issue and find out who lied at the end.


server_host_key_algorithms in SSH RFC 4253 "The Secure Shell (SSH) Transport Layer Protocol" states on page 18:

  server_host_key_algorithms
     A name-list of the algorithms supported for the server host
     key.  The server lists the algorithms for which it has host
     keys; the client lists the algorithms that it is willing to
     accept.  There MAY be multiple host keys for a host, possibly
     with different algorithms.

My question is,
In RFC 4253, "encryption_algorithms" is used for symmetric encryption and "mac_algorithms" is used for integrity protection, but what are "server_host_key_algorithms" used for?

I read RFC 4253, but still can't find possible uses for the algorithms.

In SSH, it is also necessary that the server authenticates itself to the client.
Otherwise, a man-in-the-middle (or any other party capable of manipulating the connection, e.g., via DNS spoofing) could impersonate the server and trick the client into revealing its password or, in the case of public-key authentication, a valid response to a cryptographic challenge (which the attacker may then use to log in at the real server).

This authentication step is done via the server's host keys.
Section 8 of RFC 4253 states:

  The key exchange is combined with a signature with the host key to provide host authentication.

Typically, servers support more than one signature algorithm for interoperability reasons, hence they need to tell the client which key types they have available: The server_host_key_algorithms field contains this list.

That mechanism is the reason you see the following (probably familiar) warning when first connecting to some server:

The authenticity of host 'example.org (192.0.2.121)' can't be established.
ECDSA key fingerprint is SHA256:Lj0PQQnA9K2NupAxdjJSnxQhVWoVvjTLcUQQWDFS+9A.
Are you sure you want to continue connecting (yes/no)?

Here, the client essentially asks you to confirm that you have verified the server's host key. After the first connection, the client stores the server's host key in its known_hosts file and will only warn the user again if the host key changes (for instance, if the server has been reinstalled or there really is an attack taking place).


Intuition for random variables in cryptography I have a simple question about the use of random variables for encryption schemes, to make sure my intuition is correct.

We say $P(K = k)$ to represent the probability that a particular key $k$ is chosen by the probabilistic algorithm Gen. Formally, $K$ is a random variable that denotes the value of the key.

So the expression $K = k$ denotes an event: specifically, a subset of the sample space. But all the keys are unique, so is this event really a set of size one? And is it then just an elementary event?

Then, why can't we just say $P(k)$ to denote the probability of $k$ being output? Do we use the random variable to be more explicit and clear?

We use the random variable to indicate the "by what" part of "the probability of $k$ being output".


What is the significance of the value $1/2$ within the first property of a LLL-reduced basis? In this lecture the lecturer notes that the projection of the vector $b_2$ onto the vector $b_1$ will always result in a vector that lies between $-b_1/2$ and $b_1/2$. Why is this statement true?

I recognize I could be mis-reading these lecture notes. More generally my question is: What is the significance of the value $1/2$ within the first property of a LLL-reduced basis?

The case considered in the suggested notes is in fact Gauss-Lagrange algorithm.
You can also see the notes here.

According to the terminology considered in the notes, you have :

${\bf \tilde{b}}_2={\bf b}_2-\mu_{21}{\bf b}_1$

${\bf b}'_2={\bf b}_2-\lfloor \mu_{21}\rceil{\bf b}_1$

${\bf \tilde{b}}_2-{\bf b}'_2$ is parallel to ${\bf b}_1$ and
$||{\bf \tilde{b}}_2-{\bf b}'_2||=|\mu_{21}-\lfloor \mu_{21}\rceil|\ ||{\bf b}_1||.$ But $|\mu_{21}-\lfloor \mu_{21}\rceil|<1/2$ so $||{\bf \tilde{b}}_2-{\bf b}'_2||\leq ||{\bf b}_1||/2.$ Also the length of the projection of ${\bf b}'_2$ over ${\bf b}_1$ (denote it by $||{\rm proj}_{{\bf b}_1}{\bf b}'_2||$) is  equal to $||{\bf \tilde{b}}_2-{\bf b}'_2||,$ so you get $||{\rm proj}_{{\bf b}_1}{\bf b}'_2||\leq ||{\bf b}_1||/2.$

The $1/2$ guarantees  that the vectors of the new basis of the lattice will have always smaller lengths than the previous.

In fact, if you repeat the previous steps, you will end up with the minimum vectors (with respect to the Euclidean length) in polynomial time bit complexity.
In general LLL (for dimensions $> 2$) provides two small vectors (not the minimum ones) in polynomial time bit-complexity.


How to force non-negative int64_t output for blowfish encryption with int32_t input? I would like to encrypt a series of small integers one by one. The range of them is about 0~10^8. The output must be non-negative int64_t integers.

Since Blowfish is 64-bit cipher, I prefer to use it as symmetric encryption algorithm.

The problems are:

Since 32-63 bits of input is always 0, do I need to do certain pre-process step to enforce security?
The sign bit of Blowfish's output may be 1. I have to prevent this happen. What should I do?
How to design correct decryption procedure to get original integer int32_t?

Thank you in advance.

One option is to encipher each number as follows:

concatenate one 0 bit, the index for the number to encipher (or a random value) on 31 bits, and the 32-bit number to encipher, to form a 64 bit value with the leftmost bit at 0
encipher with blowfish (and a fixed secret key)
if the leftmost bit of the result is set, loop to 2
output the 64-bit result (which matches the desired condition of having its leftmost bit clear)

Decryption is as follows

check that the input value matches the desired condition of having its leftmost bit clear
decipher with blowfish (and the same fixed secret key)
if the leftmost bit of the result is set, loop to 2
optionally, if the index is known: check that the leftmost 32 bits of the value match the intended index; that gives you a free Message Authentication Code with odds less than one in two billions of forgery!
extract the deciphered 32-bit number as the rightmost 32 bits of the result

That's cycling, a classical technique of Format Preserving Encryption. The average number of Blowfish encryptions is 2, and odds are about $1/2^n$ that more than $n$ Blowfish encryptions are necessary to encipher a number. It is not possible that steps 2/3 of encryption or decryption enter an infinite loop (including if the ciphertext was altered, thanks to the check made at step 1 of decryption); however it could be that we encounter by accident an input which requires 50 loops or slightly more, or (with a determined attacker knowing the key and giving us a rogue ciphertext) perhaps next to 100; and the only firm upper bound we have ($2^{63}+1$ iterations) is entirely impractical.

Other methods are possible that take bounded time, and can reduce the cryptogram size (at the expense of MAC robustness); but all the secure ones I know will have one of the following drawbacks:

they will require significantly more Blowfish encryptions on average (as if we build a 63-bit block cipher from Blowfish and a Feistel structure);
they will provide no integrity insurance (as if we encipher a 31-bit incremental index with blowfish, truncate the 64-bit result to 32 bits, XOR that with the 32-bit number to encipher, and form the cryptogram by prefixing the 32-bit result with a  0 bit and the index).


Minimum number of active s box to be resistance to differential cryptanalysis I am calculating the minimum number of active s_boxes for block cipher using mixed integer programming, when can we say that block cipher is resistance to differential cryptanalysis after which round?
For example AES algorithm or LED

The maximum differential probability of SBoxes should be first calculated.
Then, after finding the number of active SBoxes for some defined rounds, you should calculate the number of overall chosen plaintexts-ciphertexts by raising the probability to the power of the number of reached active SBoxes for this defined rounds. If the number that we computed, exceeds of some bounds of today's computational power, then this defined round is enough for resistance against differential cryptanalysis. Example: in Present cipher, any five round differential characteristics have a minimum of ten active boxes. If the maximum differential probability of a Present SBox is $2^{-2}$, so for five rounds, that has 10 active SBoxes, is $2^{-10}$. It means that for 5 rounds, this cipher is not immune against differential attack and by gathering $2^{10}$ numbers of chosen plaintext-chosen ciphertexts, we can set up this attack. But in own Present cipher, it has 25 rounds, it has 50 active SBoxes, so $(2^{-2})^{50}$ results in $2^{100}$, it means for setting up this attack, we need $2^{100}$ numbers of chosen plaintexts-chosen ciphertexts that it exceeds the amount available of today's computational power. So, we proved Present is immune in 25 rounds and 50 active SBoxes against differential attack.


Is the CBC weakness in XML Encryption a new discovery? Are other applications vulnerable? The RUB in Germany reports that XML encryption is broken.  This is essentially the W3C standard for protecting XML documents from prying eyes.

Does this mean that an attacker can only see a single message, or that they can actually infer the encryption key for all messages?

Is this a new vulnerability in CBC?

How is this relate to pre-existing applications that use CBC?

After reading the paper How to Break XML Encryption (thanks to Krzysztof for the link), here are my two cents.

This attack relies on the fact that a CBC-ciphertext C = (IV, C1, ... Cd) can be decomposed into pairs of (IV, C1), (C1, C2), (C2, C3), ... (C(d-1), Cd), each of which is also a valid CBC ciphertext for the same key, relating to the corresponding pieces of plaintext (ignoring padding).

Having such a pair C' = (IV, C1) (for example), we can modify its corresponding plaintext arbitrarily by modifying the initialization vector part.

Now we take an validation oracle - a function to which we can send a pair, and which tells us some information about the plain text. In this attack on XML encryption, the oracle tells us if (a) the plaintext is correctly padded, and (b) does not result in invalid XML (like characters not allowed in XML, or unmatched & or <). Such an oracle can be constructed from the error messages of the attacked web services.

Repeated querying of this oracle with slightly different values of of the initialization vector now allows us to reconstruct the individual bytes of the plaintext.

Some more analysis of the paper is in this blog post Attack of the week: XML Encryption by Matthew Green.

  Does this mean that an attacker can only see a single message,
  or that they can actually infer the encryption key for all messages?

The attack is an attack on the mode of operation - it works for any block cipher in CBC-mode if such a validation oracle can be effectively constructed and used.
It does not give back the key, since it actually circumvents the block cipher instead of attacking it.

It needs a number of oracle queries for each broken plaintext byte (the exact number will on the type of oracle), but can be applied to any intercepted ciphertext message. It also allows constructing ciphertexts with arbitrary plaintext (using more such oracle queries).

  Is this a new vulnerability in CBC?

From the introduction, it seems that similar attacks on other protocols using CBC-mode (attacking the padding scheme instead of the encoding like here) were already known before (as early as 2002). The fact that CBC-messages can be decomposed as shown above is certainly not a new insight.

But this specific way of breaking seems new (it was discovered in February 2011, they just waited a bit with writing and publishing the paper).

  How is this relate to pre-existing applications that use CBC?

Protocols like TLS, SSH and IPSec combine the encryption with a message authentication code for integrity/authentication (or even use a combined "authenticated encryption" scheme). A chosen-ciphertext attacker (like here) has usually no way of constructing a valid MAC tag, and if the application rejects messages with a wrong MAC instead of trying to parse the plaintext (and giving a suitable error message), there should be no problem.

XML Encryption also provides for a MAC, but it is optional - in a way that allows an attacker to strip off the MAC and still get a valid encrypted message.

For file or email encryption (like PGP), there is usually a key per message, and no easy way of using an validation oracle.


Why does WOTS+ need a checksum during signing operation? I was reviewing WOTS+ scheme for consideration in our private blockchain, and noticed that it had a small overhead of calculating a checksum as seen in the following pseudocode excerpt from the SPHINCS+ submission to NIST

wots_sign(M, SK.seed, PK.seed, ADRS) {
  csum = 0;

  // convert message to base w
  msg = base_w(M, w, len_1);

  // **compute checksum** <<<<============
  for ( i = 0; i < len_1; i++ ) {
    csum = csum + w - 1 - msg[i];
  }

  // convert csum to base w
  csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
  len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
  msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
  for ( i = 0; i < len; i++ ) {
    ADRS.setChainAddress(i);
    sk = PRF(SK.seed, ADRS);
    sig[i] = chain(sk, 0, msg[i], PK.seed, ADRS);
  }
  return sig;
}
//Algorithm 5: wots_sign – Generating a WOTS+ signature on a message M.

Why is it there? Is it necessary for the security of the scheme?

Update

According to "On the Security of the Winternitz One-Time Signature Scheme", the checksum deters "second-key" and "key-collision" attack should there be a functional forgery oracle. How relevant an attack is it to WOTS+ and to other regular signature schemes?

To understand why we need a "checksum", we can take a look all the way back to 1979 paper "A Certified Digital Signature" by Raphle Merkle.

From page 14 on the treatment of the Lamport-Diffie OTS:

  The method as described thus far suffers from the defect that B can alter m by changing bits that are 1's into 0's. ... However, 0's cannot be changed to 1's.

This is because, if one changes 1 to 0, she/he can simply calculate the image of the hash for that bit and get another valid signature.

The countermeasure as proposed was, quote:

  by signing a new message m', which is exactly twice as long as m and is computed by concatenating m with the bitwise complement of m.

The similar method was used in WOTS, except instead of concatenating m with its bitwise complement, it's concatenated with the "additive" complement of the sum of its indicies.

So this is more like a padding scheme (similar in purpose to that used in RSA), but since it's a number, we'll just call it a checksum.

As to the update in OP, the checksum also plays an important role in the provable security reduction of WOTS.


What advantage does facebook's new encrypted access_token have? When a user on facebook grants an app access to their account, an API key is issued to the app. This key is app and user-specific. This process is described in Facebook's developer documentation.

Until recently, API keys could be parsed- they contained the app's numeric ID, the user's ID, and other information (timestamps, validity, etc) encoded and used by Facebook to track the app and grant/revoke permissions.

As described in Facebook's documentation, https://developers.facebook.com/docs/oauth2-https-migration/, the access tokens given to apps are now encrypted. What does Facebook accomplish by encrypting the access token? Other than the fact that you can no longer tell by looking at it what user and app it belongs to, nothing is changed from what I can tell. If the token is stolen, it can still be used, encrypted or not, to access the user's account.

Disclaimer: I am writing this based only on what you write and my own guesswork.

Last I saw something about "encrypted tokens", it was about server load. When an app uses such a token, the token must be verified against what can be described as a big database of all existing valid tokens. Possibly, some people could have begun to try "random tokens" just in case it works (cost of trying a random token is about 0 for an amateur who will just try out a dozen or so, but the perceived potential gain is high). Risks of hitting a valid token are negligible (if the token includes enough secret random bits) but each such token must still be validated against the Big Database, and given the size of Facebook's user base, one can surmise that this implies a tremendous extra load on that database.

A way to reduce such load is to use a MAC: a keyed integrity check. Facebook's servers would first verify the MAC (with the secret key used to generated the MAC in the first place) and only tokens with a proper MAC would be forwarded to the database for the more expensive verification.

There are several methods to make a keyed integrity check; one of them is to add some "redundancy" in the token structure (e.g. a field consisting in a sequence of zeros) and then encrypting the whole with a pseudo-random permutation (a block cipher, using the whole token as a single "block"). To verify, the token is decrypted and the presence of the redundancy is verified. There is ample room for doing it wrong (e.g. if the token is longer than a cipher block, and an inadequate chaining mode is used) but it is still a possibility.

Therefore, without any other information, I find it possible that the "encrypted token" could be a keyed integrity check in disguise, meant to reduce server load.


What cryptography is suitable to motivate High School students to learn math? A High School math teacher in the Bronx asked me if I knew of any way to use cryptography in a way that motivates students (15 to 18 years old) to learn math.

I do know that many of them want to protect (encrypt) Snapchat pictures, and understand how SSL and encryption "works".

Is anyone aware of a curriculum, or is willing to share a mental outline of an age-appropriate set of challenges that will get them thinking in the right direction?    The focus is for non-math majors who need to "justify the reason" for learning math, and to gain a sense of empowerment and removing fear from the word "encryption".

One exercise could be to "use exponents to encrypt a password", or other weak crypto that can be done with a pen and paper.   I also want to get students thinking about prime numbers, and why they are important, and other similar "building block" concepts.

15-18 is an age where kids are looking for independence and question authority of adults.  Cryptography is often horribly implemented, and can serve as a teaching tool of where professionals have gone wrong.

So pick some real world blunders, and do some analysis on those blunders.   There's enough cryptographic blunders that are easy enough for HS students to understand to fill an entire course with.

A good recent example is the Adobe password leak.  A good writeup is available here  You could very easily find the leaked data, create a small, anonymized subset of it, and repeat the same analysis done in the article on that subset.

It's a great example because it uses something kids use every day that's highly mathematical (passwords on websites), but they're unaware of.  It also shows how adults screwed up, which every kid loves, but also how to do things right.  The mathematics is simple enough that you don't need advanced degrees in mathematics, and you don't really need to go into depth on how the crypto works.


Perfect Forward Secrecy with NaCl I would like to use the NaCl cryptography library (or TweetNaCl), but I would very much like to have perfect forward secrecy for my application.

From what I understand, all Bob needs to to decrypt a message from Alice with NaCl's crypto_box_open is the public key of Alice and his private key. Thus, if an eavesdropping adversary stored all messages and later gains access to Bob's private key, he can decrypt all previously stored communication.

Am I correct in this matter?
How would one best work around this problem? (preferably only using algorithms implemented in NaCl)

Yes, you are correct.

The simplest way without stepping outside NaCl would be to have both create an ephemeral, random crypto_box_keypair, then exchange public keys using their long term keys. Further communication would use that new keypair for crypto_box during that session. After they are done with the session, delete those ephemeral keys from memory.

The private keys would only exist for the session, so an attacker who later compromised one of their computers would be unable to decrypt any of the messages encrypted with those keys and could only find out their public keys from stored communications.


Chaining one-time signatures To introduce the notation for the question, consider a one-time signature algorithm:

There are a private signing key $sk$ and a corresponding public key $pk$, generated by $Gen(seed)$.
To sign a message, use $sig = Sign(sk, m)$, and verify the signature by $Ver(pk, m, sig)$.

The one-time signature works as usual, with one limitation: if more than one message is signed with the same $sk$, there is no assurance that an attacker cannot forge a signature of another message without knowing $sk$.
There is much work to expand this “one-timeness” to “many-timeness”, where “many” still stays limited.
I wonder, why one cannot use a plain one-time signature mechanism to sign an unlimited sequence of messages $m_1, m_2, ...$, as follows.

Assume I have $sk_1$ and the verifier has $pk_1$.
To sign $m_1$,

Generate $(sk_2, pk_2) = Gen(seed_2)$,
Calculate $h_1 = hash(m_1, pk_2)$, $sig_1=Sig(sk_1, h_1)$.
Send to the receiver $m_1$, $pk_2$ and $sig_1$.

The receiver uses $Ver(pk_1, hash(m_1, pk_2), sig_1)$ to verify both the message and the authenticity of the next signature verification key.
The new key can be used to sign the next message and so on. This method can be used, for example, to sign software updates, where the "messages" come in a natural sequence.

I am wondering, why I cannot use a plain one-time signature mechanism to sign an unlimited sequence of messages

You can; your method does exactly that.  However, it assumes that the verifier sees all previous signatures before verifying the next - not all use cases can assume that.


Can ChaCha20 be repurposed as a general purpose permutation function like Gimli? I like the idea behind Gimli and libhydrogen but in my benchmarks Gimli permutation function is considerably slower than ChaCha20 one. By considerably I mean four times slower using SIMD builtins. This is a big difference. Moreover, ChaCha20 is more mature and a more conservative choice.

Can ChaCha20 be repurposed as a general purpose permutation function as Gimli? What are the security risks to consider?

EDIT

My objective is to patch libhydrogen to use ChaCha20 instead of Gimli. I do not have the knowledge on this field nor the intention to do anything else.

There is a library called Monocypher* that heavily utilizes derivatives of ChaCha and Salsa. (Plus Poly1305, X25519, and Ed25519.) The algorithms it uses, XChaCha20, Blake2b, and Argon2 all use different permutations but those permutations are all extremely similar.

I don't know if any Salsa variant's permutation can be used as is. It certainly would be risky to decrease the round count by much. I'm not aware of published analysis of any variant used as a stand-alone permutation.

If ChaCha's permutation function (with 20 rounds) is a secure public permutation, then we know the algorithm ChaCha20 is secure. But if we know ChaCha20 is secure, that doesn't mean we know the permutation is secure. One reason why ChaCha20 is so robust (and therefore why it can get away with few enough operations to make it fast) is because of the algorithm as a whole, not just the permutation. The only thing you can qualify as attacker controlled inputs in ChaCha20 is the IV. Message bits (plain- or ciphertext) have zero influence in ChaCha20's permutation function. This is a smaller attack surface than what's possible with block ciphers, hash functions, and public permutations. All of which have security properties that ChaCha20 doesn't need to have. The permutation it uses wasn't designed to be one-size-fits all, so we don't have much evidence yet to say it's safe for general-purpose permutation use.

One property of the ChaCha permutation is that it does not use round constants. It's also an ARX (add rotate xor) construct. It has a trivial fixed point $P(0) = 0$. Which results from

Addition: $0 + 0 = 0$
XOR: $0 \oplus 0 = 0$
Rotation: $0 \text{ rotate-by } k = 0, \forall \space k$

The presence of a fixed point in a randomly chosen permutation function is to be expected. Finding one a permutation on a large block size is a harder problem if it requires brute force. This known fixed point might be a problem for some (but not all) applications. For Salsa, Chacha, Blake 1 and 2, their respective permutations are used with a portion of their input bits fixed to a non-zero constant so it isn't a problem there.

In the Gimli paper I found (ctrl-f) a reference to round constants, so I'm pretty sure it doesn't have a zero fixed point.

The number of rounds you use of a ChaCha-like permutation function obviously has an effect on security. It seems like even the algorithms that use less than 20 rounds probably are still safe. But that likely has a lot to do with how the permutations are used in addition to the robustness of the permutation itself. I can't tell you if 20 rounds are safe enough for all or most general purpose permutation uses, if you can safely decrease them, if you need to increase them, or if increase the number of rounds will help.

The safe answer to your question is no.

And although it doesn't seem like it, this is a sort of "Should I implement my own crypto?" question. I've considered the same idea. Breaking two secure constructs into pieces and recombining pieces Frankenstein's monster style doesn't make the end result secure.

* I'm aware of the project but haven't looked into it. It's probably safest to use NACL, but I can't and shouldn't endorse any option.


Order-Preserving Encryption (OPE) and leakage I recently came across OPE and Order-Revealing Encryption (ORE), but I didn't exactly got the idea why they are important. What's exactly important about them? Are they actually used in practice? My recent interest is leakage-resilient cryptography, and I saw there are some papers on leakage in OPE and ORE, but why is leakage important in OPE and ORE?

I do work in this area. OPE and ORE are important primarily because of their tremendous utility in building systems which can perform some computation on encrypted data. Contrary to general-purpose solutions like fully-homomorphic encryption, OPE and ORE can be used to provide drop-in (with no code change) security in applications like databases. They can do this with only a small decrease in efficiency of the application.

OPE and ORE are used in practice. Companies like CipherCloud and Skyhigh Networks deploy encryption software for cloud applications like Salesforce that use OPE heavily. Other major tech companies are also looking at OPE and ORE, though I can't say which ones for confidentiality reasons.

The 'but' (in cryptography there's always a 'but') is that all practical OPE and ORE schemes leak some information about the plaintext. This may seem obvious - to have order-preserving encryption you kind of need to, you know, preserve order. The hitch is that most actual deployable OPE and ORE schemes leak more than just the order of the plaintexts, and in some sense this is unavoidable because of a well-known impossibility result by Boldyreva et al. Further, nobody in the research community really knows how bad this leakage even is for real applications of OPE and ORE - we have precise simulation-based proofs which bound the leakage, but these proofs assume uniformly-distributed plaintexts. It seems like most use cases of OPE and ORE do not involve uniformly-distributed values, though. Extending and generalizing these analyses is a major (and important) open question right now.

I should note that when research papers talk about the "leakage" of OPE, it's not quite the same "leakage" discussed in leakage-resilient cryptography (LRC). LRC is attempting to provide a formal framework for reasoning about the effect of side-channel attacks which leak bits of the secret key, but in analyses of OPE and ORE the key is assumed to be fully hidden from the adversary.


Distribution of safe primes generated using different techniques Is there any difference in the distribution of safe primes generated by creating prime $q$ and testing $2q+1$ for primality, compared to generating a larger prime $p$ and testing $(p-1)/2$ instead? The former is what is used in practice for efficiency. For the purposes of this question, I am assuming primality is determined by creating an odd integer, subjecting it to a sufficient number of Miller-Rabin tests, and incrementing it by two if it is composite before testing it again.

$\{p \in \mathbb Z \mid \text{$p$ is prime and $(p - 1)/2$ is prime}\} = \{2q + 1 \in \mathbb Z \mid \text{$q$ is prime and $2q + 1$ is prime}\}$

With your intervals suitably adjusted, the algorithm considers the same candidates with the same probability whether you check $p$ or $q$ for primality first.