No, that is not correct.  You appear to have a misconception about how RSA signatures work.

Here is how an RSA signature is generated:

You take your message $M$
You apply a padding function to create a value $m = pad(M)$
You then use the RSA private key to compute $m^d \bmod N$

Now, this last step isn't always done in the straight-forward manner.  With blinded RSA signatures, it's done using a random value $r$ to defeat some side channel attacks; however that isn't that important for how RSA signatures work in general.  In particular, the value that a blinded RSA computes is precisely the same as a nonblinded version; it just uses a different algorithm to get that value.  In addition, that's the only part that's different for "blinded RSA signatures"; in all other respects, they are computed precisely like any other RSA signature.

You appear to be expecting that you can skip step 2, and step the value $m$ to the message $M$.  However, that can be dangerous; one of the issues with using  RSA without padding is that the RSA operation (either public or private) preserves multiplication, that is:

$RSA(a) \times RSA(b) = RSA( a \times b )$

(where both multiplications is done modulo $N$).

What this means is that if someone gets a series of messages $m_1, m_2, ..., m_n$ with their unpadded signatures $RSA(m_1), RSA(m_2), .., RSA(m_n)$, they may be able to find a message $m_{evil} = m_1^{e_1} m_2^{e_2} ... m_n^{e_n}$ (for some set of exponents $e_1, e_2, ..., e_n$; note that some exponents may be negative).  The attacker typically can do this if some of the $m_1, m_2, ..., m_n$ values are smooth (consists of only small factors); if there are enough smooth values, the attacker may be able to find a subset that they can recombine to form $m_{evil}$.  If that attacker can do that, that means that he can immediately deduce the signature $RSA( m_{evil}) = RSA(m_1)^{e_1} RSA(m_2)^{e_2} ... RSA(m_n)^{e_n}$

Signature padding methods are designed to prevent this; the value $pad(M)$ are large values, and hence are extremely unlikely to be smooth.

Hence, it is considered a Good Idea to always have a padding method when generating RSA signatures.


How is encryption using XOR represented?

This answer assumes it was meant stream cipher, not shift cipher (because the later, also known as Caesar's cipher, has nothing to do with XOR; but that assumption turned out wrong).

In a stream cipher, a keystream generator is initialized with a secret key, and a (typically random) Initialization Vector (which will be transmitted to the receiver in clear). From that, the keystream generator deterministically produces the keystream, that is a sequence of random-looking bits as long as the plaintext is, here $5\times8=40$ bits, say
10111100 01110110 00100010 01100000 01101001
This keystream is combined by (bitwise) XOR with the (binary form of the) plaintext
01001000 01100101 01101100 01101100 01101111
yielding the ciphertext
11110100 00010011 01001110 00001100 00000110

For each bit, XOR (often noted $\oplus$ ) can be defined by this truth table
$$\begin{array}{cc|c}
k & p & c=k\oplus p \\
\hline
0&0&0\\
0&1&1\\
1&0&1\\
0&0&0
\end{array}$$
and that's the same table as addition modulo 2. In yet another equivalent definition, the output is 0 when the inputs are equal, 1 when they are different.

Somewhat, the IV and ciphertext reach the receiver (typically thru a public channel e.g. radio). The receiver rebuilds the keystream from the IV and secret key (conveyed secretly and separately), using the same deterministic keystream generator. The keystream is then combined by bitwise XOR with the ciphertext, and that rebuilds the (binary form of the) plaintext, since $p=k\oplus c$.

In computer practice, the plaintext, keystream and ciphertext could be handled as octets (8 bits) or wider chunks, and combined with bitwise XOR over an entire octet/chunk. The C, C++, Java, Go.. languages have an operator ^ doing just that. Beware however that at least keystream and ciphertext octets/chunks can take any value, and that might require special care (for example, C strings are not directly usable for keystream and ciphertext).

The keystream generator and resulting stream cpiher tend to share the same name. Cryptographic literature is ripe with excellent ones, including ChaCha, or a block cipher such as AES enciphering a counter initialized with the IV, yielding AES-CTR.


Converting raw ECC private key into ASN.1 DER encoded key

ASN.1 is a way of defining structures for data, and DER is a binary encoding of those structures. But they aren't describing any structures by themselves. Saying that something needs to be ASN.1 / DER encoded is like saying that the key needs to be represented in XML without specifying the tags or tree structure.

What you are required to generate is a PKCS#8 (inner) encoded private key. The SEC1 document link that I provided before defines the inner SEQUENCE in there. The PKCS#8 inner structure is used to identify the type of key. Most of what is in SEC1 was copied to X9.62. And yes, it clearly contains the optional public key. If you look for ways to encode your private key to PKCS#8 you'll find a lot more information. It's for instance the default encoding for OpenSSL, but most other libraries will use the same.

I can generate the same in Java (ECPrivateKey.getEncoded() for curve "secp256k1") but without the optional - and in my opinion spurious - public point included. You can see the structure you've provided in the Lapo online ASN.1 decoder. Yes, it clearly includes the public key as optional BIT STRING at the end (appending it yourself means adjusting the length encodings of the SEQUENCE's though).

If your structure lacks a public key, I would first just try and import it; it's pretty easy to compute the public key from the private key and parameters: just point multiplication with the base point G. Likely the device is capable of doing that.

You will generally want to create a "named" curve where the domain parameters are given by an OID (as in the example you've been given). It is more likely that explicit domain parameters are rejected by devices that only operate on a limited set of curves.

I've however encountered HSM's that require you to provide the unnamed parameters. In that case you may need to construct your private key using the explicit parameters and then encode...


So if I have 128-bit key - then it seems to be natural to have every
  different key produce different ciphertext for a given plaintext - p1.

That is not so. AES is a keyed permutation of a 128-bit block, that is, each different key produces a unique permutation. But the key space is not a permutation on the output! In fact, it is very likely there are two different AES keys out there which will both encrypt plaintext A to ciphertext B, for any A and some B (not all A and B, of course, since that would mean the keys are equivalent).

In any case...

  How AES differentiate between the two?

You (hopefully) know the encryption key, and that tells you which permutation you want (even in the case that there exist two equivalent keys, which is not the case for AES, afaik).

  The second question: what about AES-256? Here I have 2^256 keys, but
  again for given plaintext - p1 I can get no more than 2^128 output
  blocks, is it that I only have 2^128 unique keys even for AES-256?

No, all $2^{256}$ keys produce distinct permutations (well, at least they are supposed to). You need to think in terms of permutations here. There are $2^{128}!$ possible permutations of a 128-bit input/output space. This is an unimaginably large number, and $2^{256}$ is considerably smaller than $2^{128}!$.

However, one thing which occurs here, is that it is no longer likely that there exist two distinct 256-bit keys which both encrypt any A to some B. In fact, it is now certain, due to the pigeonhole principle. And that is not a problem.


Does anyone have any hard ciphers to be cracked for fun?

Not sure anyone here has a sense of humour.  But in case they do:-

Obviously Kryptos, CIA headquarters, Langley.

Less obviously, this sad one time pad message, Surrey, England (also proving that OTPs did exist and were useful).

Good luck, and please post your answers here :-(


Given an AES-CBC encrypted string, IV, and plain text, how can I compute the key?

If I had a way to do this, I would be rich (at least temporarily, until I moved on to smashing the capitalist system before the money got to my head), because trillions of dollars of economic value in communications across the world are secured by the assumption that you can't.

It's kinda one of the design principles of modern cryptography.  Not only can you not figure out the key, but you can't even distinguish another encrypted message under the same key from random noise, no matter how many plaintext/ciphertext pairs you have of your choosing, up to limits that are beyond the reach of humanity.  This property is sometimes called ‘indistinguishability under chosen plaintext attack’, or IND-CPA.


How to solve high exponent attack for same message in RSA

If you have $e$ ciphertexts for the same message, then the attack is the same, you just have to apply the CRT with $e$ values, then computing the $e$'th root of the resulting value might need some work.  And this is assuming that all moduli are relatively prime of course. If that's not the case, there is $i,j$ and $gcd(N_i, N_j) \neq 1$. So you can factor one of  $N_i$ or $N_j$ and decrypt the message. Lastly, depending on the size of $e$ and that of the $N_i$ you might want to investigate attacks on "small private exponents" such as Wiener's attack or from Boneh et al.


Why are we not using multiple ciphers per message?

I don't know about computing things in parallel, so I will ignore that part of the question.

First, please note that the encryption algorithm is rarely the the weak point of the security. It is far more likely that

you will have problems with the implementation,
some spyware installed on your computer,
a weak password (If you use qwerty as your password, it doesn't matter how awesome your algorithm is).

That is, you have to remember that security is about much more than choosing a nice algorithm.

Second, the security of, for example, AES has been studied and it is secure. There are no known practical attacks that breaks AES (assuming strong password of course). So using another algorithm doesn't really do a whole lot more.

That said, you can of course do it. But again, if you really want to do it, you have to do it right. I am sure that in your studies of cryptography you have come across the idea that you should not "roll your own crypto". And in some sense, combining two algorithms, you risk violating that principle. If you, for example, had an implementation of AES that as output produces a file that always starts with, say, 10 bytes identifying the file as having been encrypted by AES (your implementation?), then (since you can assume that your attacker knows your method of encryption) an attacker know has part of the plaintext for the second encryption. (This is not necessarily a problem!) This doesn't give it all away, but you have now given an attacker some information that he might be able to use. Another problem is if you accidentally pick two algorithms where one undoes part of the other.

The point is, that there is a good chance that you will make a mistake in doing the actual implementation of the combination of the two algorithms.

But, if you get all this right, then sure, it would be perfectly fine to encrypt as you suggest. In fact, some might already be doing things like this.

To finish let me quote a blog article:

  ... It's entirely possible to combine encryption schemes in secure
  ways (many of which are not cascade constructions), but the amount of
  extra security you'll get is subject to some debate.

Other interesting things:

http://eprint.iacr.org/2002/135.pdf
https://security.stackexchange.com/questions/32247/will-double-encryption-increase-the-security-of-cipher-vs-bruteforce
How secure is AES-256?


Implementation of Leighton-Micali Hash-Based Signatures

It is stated, that LMOTS private key generation creates a 32B SEED at the start of the process, although does it create a new SEED for every new key from 0 to q=2^h-1?

If you use the suggested key generation method found in Appendix A, you use the same seed value for each Merkle tree.  If you use multiple Merkle trees (in HSS with L>1), then each tree gets its own SEED value

although it is not stated for what q the LMOTS public key is generated, or does it mean, that this public key is the LMS public key, which is the root of the tree created by leaves of LMOTS public keys K?

It is the HSS public key, which is the LMS public key of the top level Merkle tree.

I have a slight problem using the reference implementation, as it is created for HSS. Do you know how can I force it to use only LMS?

Tell it to use L=1; that is, when you call hss_generate_private_key, pass it a 1 as the levels parameter (the second one).


Hide a weakness in ECC by choosing the prime or one of the curve coefficients

Bernstein and Lange says that there has been no progress for prime-field elliptic curves since about 1999, when the NIST curves were chosen. No large class of weak curves were known then, and no large class is known now.

Some small classes are known, (as Neves says) the curves with small embedding degree and the anomalous curves (order $n$ equals the prime $p$), but all of these were known back then (though not all of them by everyone in 1985, the MOV attack was a real attack, and the anomalous curves were an attempt to block the MOV attack, I think). So these classes are hard to hit at random, and are easily detected anyway.

The problem of embedding trapdoors in elliptic curves has been studied by Edlyn Teske, but she uses curves over extension fields, not prime fields. (Her techniques rely on it being hard to find isogenies between curves, but it is possible to find curves with isogenies. You choose one curve over an extension field that is secure, another that is not secure, and an isogeny between them. The isogeny is the trapdoor and allows you to move the DLOG instance from one curve to the other. The extension field attacks this relies on do not apply to NIST's extension field curves, as far as I know.)


What goals is homomorphic encryption aiming to solve?

Homomorphic encryption in and of itself solves the problem of computation on encrypted data. For example, if I give you only the encryptions of $a$ and $b$ ($E(a),E(b)$) can you compute $E(ab)$ and $E(a+b)$. That is the problem that fully homomorphic encryption (FHE) solves. There are also partially homomorphic encryption methods that allow you to only compute one operation (e.g., Paillier and Elgamal).

Cloud computing is "the use of computing resources (hardware and software) that are delivered as a service over a network (typically the Internet)." So, you push your data to the cloud then tell the cloud what computation to perform. The cloud computes the result and sends the answer back to you. The benefit of FHE when applied to the cloud is that all of this can take place without the cloud learning your data. You upload encrypted data, the cloud performs the comptuations on that data, returns the result. That said, it appears that FHE alone is not sufficient for privacy-preserving cloud computing.

Of related interest, I'd suggest you look at In what ways does Full or Partial Homomorphic Encryption benefit the cloud?


What stops a physical attacker to use a dumped uninitialized SRAM with SRAM-PUF?

Does it mean that the response is only derived from the content of the SRAM in an uninitialized state?

For the raw RAM-PUF response, that's my understanding. How that is turned into a stable value (in practice identical across power-up cycles) is more complex, and requires long-term storage like conventional Flash for associated error-correction data (which at least in principle needs not be secret).

  How can this be tamper-proof?

My understanding is that the implicit attack model here includes: the adversary has no physical access to the RAM, and can't remotely read it in its power-up state. Perhaps the early stages of boot read the initial state of the RAM, use that, then zero that RAM.

Update: as noted in comment, if we assume that getting access to the content of the RAM-PUF at power-up is impossible without de-caping the IC, and such de-caping alters the RAM-PUF beyond the error-correction capability of the associated error-correction data, then the RAM-PUF can become a tamper-resistant vault for a secret key. I have no information about if the above assumptions hold in practice (and welcome input on that).

Another attack model commonly considered for RAM-PUF is that the attacker only attempts to make a silicon-level exact copy, or steal ICs on the fabrication line (perhaps rejects). That adversary is unable to write in Flash the associated error-correction data which, together with the unique content of the RAM-PUF, makes the device operative. In this model, reading the initial content of the RAM won't help the adversary bound to not redesign the IC.


Does it matter whether the KDF salt is integrity protected?

No, integrity protecting the salt is probably not required.

For confidentiality this is pretty obvious because changing the salt only throws away information for the attacker.
Concerning integrity things are a bit more complicated.
Suppose, these files are stored on a central server where an attacker can manipulate them and suppose that some client will automatically retry downloading the file if decryption failed or something like that.
Can an attacker learn anything about your password from knowing about decryption failures or the like for different salts?

You could construct KDFs where this is possible but for any decent KDF (it just needs domain separation) it won't be. If you have domain separation changing the salt will never influence your password in a useful way and this makes incremental testing impossible.


An efficient SPEKE protocol with curve25519

One small issue is that it can be detected if the x-coordinate lives on the base curve or on its twist.

There's not a small issue; this allows a passive attacker to halve his dictionary by listening into a single exchange.

That is, if $s$ is on the curve, then so will be $s^x$; if $s$ is on the twist, so will be $s^x$.

So, what the attacker can do is listen in, and see if the exchanged $s^x$ and $s^y$ values are on the curve or not.  If they are, he can discard the half of his password dictionary that would place $s$ on the twist.  If they aren't, he can discard the half of his dictionary that places $s$ on the curve.

SPEKE can be done security based on X25519; however you can't just select $s$ arbitrarily; you have to make sure that it's consistently on the curve (or on the twist).


Why does PSS produce an EM message that's almost as long as the modulus?

To prove that, for a generic hash function, forging PSS signatures is not much easier than computing arbitrary $e^\mathit{th}$ roots modulo a large composite of unknown factorization, we need to grant the attacker, who is trying to compute $e^\mathit{th}$ roots, oracle access to a forger for a signature scheme that uses the entire set of residue classes $\mathbb Z/n\mathbb Z$.  That way, any attack enabling forgery also implies way to solve the RSA problem at only slightly more computational cost than forgery.

If we granted the attacker access to a much more limited signature scheme that only revealed $e^\mathit{th}$ roots of a very small subset of possible residue classes, then an attack on that would not necessarily imply an easy way to solve the RSA problem.

And there are pitfalls with signature schemes involving subsets of the residue classes: e.g., if a signature on a message $m$ is defined to be an integer $s$ with $s^3 \equiv H(m) \pmod n,$ you may be tempted to test the similar-looking criterion $(s^3 \bmod n) \equiv H(m) \pmod{2^{256}}.$  Although $e = 3$ is a good sensible choice for near-fastest verification in a well-designed signature scheme (only $e = 2$ with Rabin–Williams will beat it), this modified criterion gives the adversary leeway to find a cube root by varying the higher-order bits of $s$ until they get an integer perfect cube whose low 256 bits happen to coincide with $H(m)$ for some chosen $m$.  Our friend poncho here sketched a similar attack on a variation on this theme several years ago.

This doesn't mean that a variant of RSA-PSS using a short hash would be insecure: only that we don't have confidence it can't be much easier than solving the RSA problem in general.  Compare, for example, Rabin–Williams, which can't be much easier than factoring the modulus—but we don't discard RSA-PSS simply because we haven't shown a reduction of the RSA problem to factorization.  For a similar example, see my proposed not-quite reduction of RSAP-KEM to factorization.

That said, having the security reduction helps cryptanalysts to focus their attention on a small number of problems—the RSA problem, factorization—for a large number of cryptosystems, instead of having to divide it among potentially much easier problems for each cryptosystem like RSASSA-PKCS1-v1_5, of which naive implementations may be vulnerable to the low-exponent attack I described above.  The security reduction guarantees that there isn't any much easier attack on the specific cryptosystem, so the cryptanalyst's attention might as well be focused on the general problem.


Relationship between AES GCM and AES CTR

That's correct.

In most cases you can do what you are proposing. However be warned that by disregarding the authentication you clearly loose message authentication and bit flipping in AES-CTR encrypted stream is trivial.

You can do what you are proposing if the AES-GCM IV size is of 96 bits. AES-GCM supports also longer sizes for IVs and for those cases you would need GHASH to find the correct IV used by CTR. That having being said I believe 99% of implementation supports only 96 bit IV for AES-GCM (and rightfully so).

To obtain the CTR IV, just append the value 2 encoded as 32-bit big endian integer to the 96 bit GCM IV (equivalently adds in C notation "0x00,0x00,0x00,0x01").

Edited to change from 1 to 2 of the initial counter value. GCM acutally defines the starting counter as starting with 1, but increments it before the first encryption, thus resulting in a 2. Thanks to @TrickyDixon for pointing this out.


What is the difference between KDFs for key derivation vs password stretching?

Deriving multiple keys from a strong source key material (which is what HKDF is for) is not key stretching.

The important bit from from the Wikipedia excerpt is this one:

  2./ To "expand" the generated output or an already reasonably random input such as an existing shared key into a larger cryptographically independent output, thereby producing multiple keys deterministicly from that initial shared key, so that the same process may produce those same secret keys safely on multiple devices as long as the same inputs are utilised.

As CodesInChaos' comment on the original post you referenced states, there the two types are "fast" and "slow".

Fast KDFs are designed to securely derive multiple keys from source key material that is already strong, with high entropy.  HKDF is one of these.

Key-streching or password-stretching is a term used to indicate the the source key material is weak, or low entropy, and a slow KDF needs to be used to create a key while simultaneously protecting (as best it can) the low entropy source material.  PBKDF2 is one of these.

If you attempt to use a fast KDF (like HKDF) with low entropy source material like a password, you create similar problems to those you have with using fast hash functions to protect passwords for authentication. Because passwords are predictable, the ultimate set of hashes (or keys) that will be created from will be much smaller than the full keyspace.  A fast KDF would let an attacker test far too many candidates far too quickly, making it much more likely that the correct key will be discovered, and so is not in fact suitable for key-stretching.


Comparing messages given only the ciphertext

Under RSA protocol I was wondering how a message sent could be verified under the following scenario

RSA is not a protocol, it's a crypto system. It contains several algorithms that utilize the same trap door function but different encryption and signature generation methods.

  Can Bob send Alice a second message in plain-text to determine what he had originally sent?

Of course. He could also send a hash of the message he send, so that an attacker cannot view the message that was send, but note that brute force attacks may be possible. In general it doesn't make sense to send a message in plaintext if you're after confidentiality.

  Does Alice send back Bobs message encrypted using her public key so that bob has cipher-text he can compare? Can bob only compare cipher-text? or can he do anything else?

No, because a ciphertext is supposed to be CPA-secure. That means that - in general - a random padding or IV is used. So the ciphertext should not give any information about the plaintext, including equality of the plaintext.

  With messages bob sends or receives is there anything bob can do to verify/check if the two message he sent are the same or not?

No, not unless he had access to the first plaintext message, but it seems that's not envisioned in your question.

  Can Bob decrypt a message with just the public key? Is he allowed to get private key from alice?

No, and no.

This question contains answers for generic RSA. You may want to have a look at homomorphic encryption to see if anything in there suits your needs. Currently it is not clear to me if homomorphic encryption would meet your requirements.


Ciphertext size of RSA, ELGamal, and EICES encryption

A compressed point - which makes up the ephemeral public key for ECIES - only takes the key size, possibly prefixed by an indicator byte with value 02 or 03 (which is required by some libraries).

So for e.g. BrainpoolP256R1 you'd get 32 bytes, and maybe one more for the byte indicating that it is a compressed point. That is enough to derive a data encryption key. As the public point is already ephemeral there is no need for an IV. After key agreement you would just require the ciphertext bytes - which for CTR is identical to the plaintext message size.

So that would come down to a ciphertext size of 32 + 8..40, or 40 to 72 bytes (not including the indicator byte), while still giving you 128 bits of security (and no protection against quantum computers of sufficient size, of course). That's way less than the 256 bytes required for RSA, while RSA would be less secure on top.


Wouldn't encrypting a message with AES, then encrypting the (randomly
  generated) AES key and IV with the EC public key suffice?

Yes it would suffice and is what is usually done. However for this to work you'd have to have a way to reliably convert a random integer to a curve point and back which isn't trivially possible. And even if you could reliably encode the key to be a curve point you may be vulnerable to some attacks using collision properties resulting in a much smaller security margin than expected, much like encrypting "small" values with RSA.

This is why ECIES randomly chooses a curve point, encrypts this one and uses the secret point to derive keys.

  What attack vectors does ECIES protect against, that an AES-then-EC-encrypt wouldn't?

ECIES provides chosen ciphertext security meaning it provides security against most known attacks. Simple AES-then-EC-encrypt may not be secure against such attacks if you don't do authentication of the plaintext. If you'd use something like AES-GCM with the above mechanism to encapsulate the keys you're pretty much at ECIES although ECIES uses its KDF to derive the keystream and uses HMAC to authenticate the ciphertext.


What is largest prime factor in Diffie-Hellman?

How to determine if the largest prime factor of $p-1$ is in fact large?

Most often, it is not determined from $p$ that $p-1$ has a large prime factor. Rather, a large prime factor $q$ is chosen, then it is chosen a prime $p$ of the form $p=2\,q\,r+1$ for some $r\ge1$, which insures that $p-1$ has large prime factor $q$.

Sometime, we want $r=1$, in which case $p$ is a safe prime and $q$ the matching Sophie Germain prime. See last paragraph for how these are searched.
For some other applications, we want $r$ large so that $p$ is much larger than $q$ (e.g. $p$ 3072-bit with $q$ 256-bit). This the Schnorr group case. For the search of $r$ making $p$ prime, when that does not hold, we typically add a small value to $r$; perhaps $1$, or a small random value in order to make $p$ more randomly seeded.Standard generation procedures for Schnorr groups are in FIPS 186-4 appendix A.

More rarely, it is checked after the generation of $p$ that $p-1$ has a large prime factor.

For a safe prime, that boils down to checking that $(p-1)/2$ is prime.
Otherwise, we could compute the small prime factors of $(p-1)/2$, multiply them (with multiplicity) to get $r$, then check if $q=(p-1)/(2\,r)$ is prime. If it does, and is suitably large, that validates $p$ (but we could fail to pull enough factors). This would only be useful for exploration or forensics: prime $q$ is typically needed to use $p$, therefore such $q$ is usually moved along $p$.

Quick search of safe primes (larger than $5$ and $7$)

Typically, we also want a certain generator $g$ (often $2$ or $3$) known to be of order $q=(p-1)/2$ (maximal prime order) or order $2\,q$ (maximal order, which is not possible for $g=3$ ). The search can be as follows:

for each candidate $q$ (necessarily: with $q\bmod6=5$; and further with $q\bmod12=11$ for $g=2$ of order $q$, or with $q\bmod12=5$ for $g=2$ of order $2\,q$ )

compute $p=2\,q+1$
compute $t=g^q\bmod p$
if $t=1$ (for $g$ of order $q$) or if $t=p-1$ (for $g$ of order $2\,q$)

if $q$ is prime

if $p$ is prime

output $p$ and stop.

The test of $t$ is a Fermat pseudoprime test. It quickly filters out most candidates $p$ that are not prime, and all primes $p$ with $g$ not of the desired order. If for some reason we do not care for a generator, it still pays to compute $t$ with $g=2$ and accept both $t=1$ or $t=p-1$.

The search can be made faster by selecting thru sieving only candidates $q$ with neither $q$ nor $2\,q+1$ divisible by a small prime.


How to implement access control for Automotive Embedded Systems using mbedTLS?

As stated in the comments we can't / won't advise on whether PolarSSL is suitable to perform the operations required.

However, for your needs $N_1=N_2=N_3=32$ sounds like a reasonable choice, giving you a solid 256-bit security and no need to worry about truncation and the alike.

As for $f_1$, HMAC-SHA256 sounds like the obvious choice, also giving you $N_3=32$. You'd input the secret data as a key and the challenge and the fixed bytes as a message and you're good.

Finally for $f_2$, this needs to be the same choice as $f_1$ paired with a simple constant time comparison.

I can't promise anything, but all of this functionality is required for any TLS implementation right now, so if the low-level primitives are provided you can use the library.


Is the software that uses PGP broken, or is it PGP itself?

Draft paper linked from efail.de.

TL;DR: the vulnerability is in some popular email client software, often combined with an extension simplifying the use of an OpenPGP (e.g. GnuPG) or S/MIME implementation within the said software; e.g. an extension bundled in popular distributions of GnuPG v2, thus common.

The issue is that un-validated deciphered ciphertext is made available to the email client, and it acts upon it (e.g. following HTML links to addresses that an adversary collects), yielding a decryption oracle capable of deciphering a past or current ciphertext, and exfiltrating the plaintext.

It is fine to disable decryption functionality in the email client. It should remain so until that software (and any extension  it relies on) is checked or improved to suppress (or at least not automatically act upon and preferably flag as suspect) any deciphered plaintext that did not explicitly pass the Modification Detection Code test for OpenPGP, or a similar check (to be defined) for S/MIME.

For OpenPGP, we can get back to the manual use of the bare OpenPGP tool (e.g. gpg), checking from stderr output that an MDC check explicitly passed, otherwise not acting based on what's received, be it programmatically or manually. I have no workaround suggestion for S/MIME.

From an official statement by the GnuPG and Gpg4Win teams:

  This paper is misnamed.  It's not an attack on OpenPGP.  It's an attack on broken email clients that ignore GnuPG's warnings and do silly things after being warned.
  This attack targets buggy email clients.  Correct use of the MDC completely prevents this attack.  GnuPG has had MDC support since the summer of 2000.

Update: based on that comment and other answer, and subject to dust settling, in GnuPG v2 two things are questionable, even if done on purpose so as not to break compatibility:
- Returning a status code of 0 (and a mere warning) in the absence of MDC, at least by default.
- A quirk specific to the Twofish algorithm prevents MDC error catching.


Complexity of number field sieve theorem does not match with security of elliptic curves

But in many places I saw that BN256 curve provided 128 bit security. Where I am doing wrong?

There are two potential attacks against the DLog problem in BN256

The first is to attack the DLog problem in the finite field; that is, given the points $G$ and $H$, we compute $e(G, G)$ and $e(G, H)$, and then find the value $x$ with $e(G, G)^x = e(G, H)$.
The other is to attack the DLog problem in the elliptic curve itself; that is, given the points $G$ and $H$, you use Pollards Rho (or Big-Step-Little-Step) to directly solve $xG = H$ (ignoring the pairing operation entirely).

As BN256 is a 256 bit curve, we know that the cost of the second approach is no more than an expected $2^{128}$ point additions, hence the security of the curve can be no more than 128 bits.


Security of integrity protection with HMAC vs AEAD

For any $k$-bit MAC, an attacker blindly guessing a tag has a one-in-$2^k$ chance of successfully forging a message.  Thus, the expected number of attempts needed to forge a message by brute force is $2^{256}$ for a 32-byte tag, $2^{128}$ for a 16-byte tag, and $2^{64}$ for an 8-byte tag.

In practice, attempting $2^{128}$ forgeries is far beyond the reach of any plausible attacker, whereas $2^{64}$ attempts might just barely be feasible in some scenarios.

As far as I know, the best non-brute-force attack on HMAC-SHA-256 is the generic birthday attack on iterated MACs described by Preneel and Oorschot (1999), which allows an attacker to forge a message after finding an internal state collision in the MAC computation.  For SHA-256, this would require obtaining MACs for about $2^{128}$ messages, and can thus be safely ignored.

In fact, Bellare (2006) has proven lower bounds on the security of HMAC that are close to the upper bounds given by Preneel and Oorschot, assuming that the hash function used satisfies certain security assumptions (in particular, that its compression function is a PRF, or at least a PP-MAC).  Thus, assuming no disastrous new attacks on SHA-256 arise, HMAC-SHA-256 with at least a 16-byte tag should be secure against any feasible attacker.

For GCM / GHASH, there do exist attacks better than brute force.  In particular, Ferguson (2005) shows that an attacker can forge an $n$-block message with a $k$-bit tag with probability $n/2^k$.
GCM limits the maximum message length to $2^{32}-1$ blocks, so, for a maximum-length message, the forgery probability is about $2^{32}/2^{128} = 1/2^{96}$ for a 16-byte tag, and about $1/2^{32}$ for an 8-byte tag.

While the former is still generally acceptable, the latter may not be, especially as GCM has an unfortunate property, also described by Ferguson, whereby each confirmed successful forgery reveals information about the authentication key, and thus makes successive forgeries much easier.  Thus, echoing Ferguson's recommendation, I'd advise against using GCM with a tag length shorter than 16 bytes.

As for CCM, I'm also not aware of any attacks better than brute force.  The Preneel and Oorschot attack is not directly applicable to CCM (even though it does apply to CBC-MAC), because the tag is encrypted using CTR mode with a unique nonce, and thus an attacker cannot directly detect internal collisions in the CBC-MAC state.  Even if it did apply, the CCM specification limits the total amount of block cipher evaluations made with a single key to at most $2^{61}$, which is less than the expected number of queries needed to find one collision (although not very much less; a more conservative limit would be, say, $2^{40}$ cipher evaluations per key).

Jonsson (2002) has proven a lower bound on the security of CCM mode that is similar to the Preneel and Oorschot bound, in that the success probability of an attacker making $q$ forgery attempts comprising a total of $m$ blocks, and having access of $n$ blocks of valid messages, has a success probability less than $q/2^k + (m+n)^2/2^b$, where $k$ is the bitlength of the tag, and $b$ is the blocksize of the underlying cipher ($b = 128$ for AES).

This bound is rather conservative, and indeed, Jonsson himself has conjectured, but not proven, a bound on the forgery probability that is linear rather than quadratic in the number of encrypted blocks.  In fact, Fouque et al. (2008) have managed to prove this, but only for a variant of CCM mode using independent encryption and authentication keys.  As far as I know, for regular CCM, this question is still open; of course, as long as the number of blocks processed with a single key remains well below $2^{64}$, it is purely of academic interest.


The answer to your question is contained in the Authenticity bound (Theorem 5.1).  This is because Authenticity implies non-malleability (see e.g. http://eprint.iacr.org/2011/092.pdf).  Note that only one term in the bound refers to the length of the tag (referred to by the variable $\tau$):

$$\mathbf{Adv}_{OCB}^{auth}[\mathrm{Perm}(n), \tau] (A) \leq \dfrac{1.5\overline{\sigma}^2}{2^n}+\dfrac{1}{2^{\tau}},$$

where $\overline{\sigma} = \sigma + 2q + 5c + 11$, such that $q$ is the number of chosen plaintext queries of aggregate length $\sigma$ blocks, and $c$ is the total length in blocks of the attempted forgery.

As you can see, the length of the tag only matters for the last term.  So if the tag is 128 bits then the last term adds $\frac{1}{2^{128}}$ to the total Adversarial advantage.  But if the tag is truncated to only 32 bits then the advantage will increase by $\frac{1}{2^{32}}$, which is about 1 in 4 billion.  Depending on your risk tolerance and threat model, the latter increase in Adversarial advantage might be acceptably small in exchange for the space savings of shorter tags.


RSA Encryption that only my family could decrypt

I was thinking they could add it to the end of the private key and but I don't think that is how RSA works.

Indeed it is not.

How could the decrypt a say RSA-encrypted message using this information?

One solution is to encrypt a private key with the password and encrypt the message under that private key. This also allows you to add new messages / remove old ones w/o having to recover the private key first. Of course if you'd always do that anyways, you could also just forgoe the asymmetric encryption and just use plain password-based encryption.
The cleaner solution would of course be to encrypt the message under everyone's public key, but given that it sounds like the family is not so much up to tech, a simpler solution like the above one will probably be better.
Of course note that the security of passwords like a dog name is very questionable and for a proper security level one would probably have to combine a dozen or so such information pieces (assuming that every question has ~2000 equiprobable answers).

[What] [...] would be the easiest [way] for someone with limited computer knowledge to decrypt a RSA encrypted message?

Using a standard tool and writing a detailed guide (ideally with pictures) on how to use it. A GUI is probably preferred as quite a few people are scared of command lines.


How to encrypt the truth table in garbled circuits?

Yao, encodes AND curcuit as;

the $x$ values as $k_x^0,k_x^1$,
the $y$ values as $k_y^0,k_y^1$,
the $z$ values as $z_k^0,z_k^1$.

Here the upper script represents 0 or 1.

\begin{array}{|c|}
\hline GCT \\\hline
  E_{k_x^0}(E_{k_y^0}(k_z^0))  &  \\\hline
  E_{k_x^0}(E_{k_y^1}(k_z^0))  &  \\\hline
  E_{k_x^1}(E_{k_y^0}(k_z^0))  &  \\\hline
  E_{k_x^1}(E_{k_y^1}(k_z^1))  &  \\\hline
\end{array}

Where $E$ is Symmetric Encryption Scheme, and in these schemes Block Ciphers can be utilized. One can use Asymmetric Encryption schemes but that will be slow, and non-standard.

so, given to keys, only one of the rows can be decrypted correctly.


Accoding to UMAC RFC Section 6.1, you can use any other "cryptographic objects" instead of AES:

  The strength of UMAC depends on the strength of its underlying cryptographic functions: the key-derivation function (KDF) and the pad-derivation function (PDF).  In this specification, both operations are implemented using a block cipher, by default the Advanced Encryption Standard (AES). However, the design of UMAC allows for the replacement of these components.  Indeed, it is possible to use other block ciphers or other cryptographic objects, such as (properly keyed) SHA-1 or HMAC for the realization of the KDF or PDF.

This is how Poly1305, another MAC based on universal hashing, is used in NaCl, for example: it uses the first 32 bytes of cipher stream as a one-time key for MAC, and the rest of the stream for encryption.

The advantage of applying hash to ciphertext instead of plaintext is that you can reject invalid ciphertexts earlier without decrypting them, making rejection faster and, possibly, more resistant to side channel attacks, and implementation errors (e.g. forgetting to check the return code of decrypt() function, which indicates whether the MAC was correct).


If a prime $q$ is large enough discrete logs and CDH in $\mathbb{Z}_q$ are traditional hard problems in cryptography.

Your other example $\mathbb{Z}_{2^n}$ is typically easy to solve because it can be solved progressively modulo increasing powers of $2$.

May be you intended to consider the finite field with $2^n$ elements $\mathbb{F}_{2^n}$ and not numbers modulo $2^n$.
If so, you might be interested be this related question: How robust is discrete logarithm in $GF(2^n)$?


Can OTP still be broken if there are several messages being sent with only a slight variation in a password?

What do you mean 'a one time pad with a password'?  One time pads don't take passwords, they take samples of truly random data as long as the message.

If what you're doing is taking the password, repeating it N times, and using that as if it were a random one-time pad, well, that can usually be broken even if you don't send a second message.

If what you're doing is you do have a truly random pad (which you are calling the password; however if you message is 10,000 characters long, so is your 'password'), and if you send a second message with a slight modification of the pad, then yes, it can be broken; the standard attacks against a 'two-time-pad' will work well (even if the pads are slightly different).

Bottom line: if you're relying on a 'one time pad', then it is mandatory that the pad be random, as long as the message, and not related to any other pad you may use.  If you violate this, the security proof for one time pad does not apply (and you are usually, in fact, insecure).


How does the Flame malware take advantage of MD5 collision?

I think you missed reading a part of that Wikipedia article:

  … Flame was signed with a fraudulent certificate purportedly from the Microsoft Enforced Licensing Intermediate PCA certificate authority.  The malware authors identified a Microsoft Terminal Server Licensing Service certificate that inadvertently was enabled for code signing and that still used the weak MD5 hashing algorithm, then produced a counterfeit copy of the certificate that they used to sign some components of the malware to make them appear to have originated from Microsoft.…

(emphasis mine)

In simpler words this means that the malware author(s) didn’t need to apply for a certificate himself/herself/themselves. Instead, the malware author(s) used a genuine Microsoft certificate he/she/they found and created a fake certificate based on that. That way, it seems as if Microsoft itself has signed some files – which Microsoft (of course) didn’t.

So, your …

  thus the only way to get a fake cert is to generate the fake cert when applying for a legitimate cert.

… is partly correct, but it’s only one side of the coin. The other way to get a fake certificate is to find a legitimate but weak and exploitable certificate from someone else – like one from Microsoft in this case.

Having said that, let’s answer your two questions:

  Isn't it too dangerous for the malware author(s) to do this? (We can check who applied for the legitimate cert and catch him)

No, since the fake certificate was based on a Microsoft certificate the malware author(s) got his/her/their hands on. That way, the fake certificate points to Microsoft (just like the genuine certificate it was based on), not the identity of any malware author(s).

  If he can apply for a legitimate cert, why bother making a couterfeit cert? Why don't use the legitimate cert to sign anything he like?

Not being Microsoft, the malware author(s) would hardly have had a chance to apply for a legit Microsoft certificate… and a certificate on his/her/their own name(s) would indeed have been pretty useless for his/her/their intended purposes as that would have added his/her/their name(s) to the equation.

Applying for his/her/their own legitimate certificate would have been a pretty stupid move while having the option to impersonate a trusted company like Microsoft. Remember the fact that the malware author(s) had access to a genuine Microsoft certificate with code signing enabled. (see first quote of my answer)

All in all you could say the malware author(s) found "a pot full of gold at the end of some rainbow" (read: a weak and exploitable Microsoft certificate with code signing enabled) and used what he/she/they found to his/her/their fullest malicious advantage.

Microsoft dropped a ball, and the malware author(s) picked it up. It was that simple for them. After Microsoft became aware of the situation, they handled the situation accordingly.

Quoting "Microsoft releases Security Advisory 2718704" dated June 3, 2012:

  We are taking several steps to remove this risk:

  First, today we released a Security Advisory outlining steps our customers can take to block software signed by these unauthorized certificates.
  Second, we released an update that automatically takes this step for our customers.
  Third, the Terminal Server Licensing Service no longer issues certificates that allow code to be signed.

  These actions will help ensure that any malware components that might have been produced by attackers using this method no longer have the ability to appear as if they were produced by Microsoft.

(emphasis mine)

But how did they do it?

Quoting an article from “nakedsecurity” – Sophos‘ blog:

  …

  In the Flame case, the attackers took a legitimate Microsoft certificate using MD5 for its hash and RSA-2048 for its public-key encryption. They then generated a similar-but-different certificate with the same MD5 hash. This means that the RSA-2048 signature from Microsoft’s genuine certificate could be grafted into their forged certificate to make it appear valid.

  …

Obviously, the above quote doesn’t really provide any real details.

In fact, explaining all the details would be a bit too broad to post as an answer here, but if you really want to dive deeper into an analysis of the Flame MD5 case, check the PDF: “Analyzing the MD5 collision in Flame”. Those 40 pages/slides walk you through details with screenshots etc.

Long story short: For Flame, a chosen-prefix collision attack against MD5 has been used. Its malware author(s) used a new variation of a chosen-prefix collision attack to spoof code signing of its components by a Microsoft root certificate that still used the compromised MD5 algorithm.


Recover plaintext from truncated ciphertext using AES for FPE

In the decrypting steps use AES_encrypt itself instead of AES_decrypt, AES decrypt is never needed.

Remember while encrypting, AES_encrypt is only used as a Pseudo Random Function, we don't really need AES_decrypt method even in decrypting phase. This might seem little confusing at first but not needed. Please check the proof given for this answer


It's 0x11B. Basically, you shift left by 1 bit, and if the upper bit is 1 (and only in that case), you XOR the value with 0x11B. In C terms, it will look like this:

static inline unsigned
mul2(unsigned x)
{
    x <<= 1;
    if (x & 0x100) {
        x ^= 0x11B;
    }
    return x;
}

Now this can be done without a conditional (which, on some architectures, will result into a conditional jump) with some trickeries like this:

static inline unsigned
mul2(unsigned x)
{
    x <<= 1;
    x ^= (-(x >> 8)) & 0x11B;
    return x;
}

This relies on the fact that -1, cast into an unsigned type, yields an all-ones pattern.

It really pays off, in these matters, to take the time to understand what is going on at an algebraic level. What really happens here is that we work in the finite field $GF(256)$. A value is a polynomial of degree at most 8 with coefficients in $GF(2)$. For instance, 0xB2 (in binary 10110010) really represents:

$$ v = X^7 + X^5 + X^4 + X $$

The coefficients are always 0 or 1. Addition is done for each coefficient independently, and in $GF(2)$, so $1 + 1 = 0$. In practice, this means that addition of two elements in $GF(256)$ really is bitwise XOR.

For multiplication, this is again done with polynomials, and a modular reduction, using a specific degree-8 polynomial, which happens (in the case of AES) to be:

$$ P = X^8 + X^4 + X^3 + X + 1 $$

which corresponds to 0x11B (100011011 in binary). This is defined in section 4.2 of FIPS-197. Thus, multiplication by 2 (0x02, i.e. 00000010 in binary) really is multiplication by the polynomial $X$, followed by reduction modulo $P$. If we take our value $v$ above (0xB2), then multiplication by $X$ "bumps up" the monomials:

$$ v\times X = (X^7 + X^5 + X^4 + X)X = X^8 + X^6 + X^5 + X^2 $$

In the binary representation, this is a left-shift by 1. However, the result must be reduced modulo polynomial $P$. In this specific case, $v\times X$ is a degree-8 polynomial, which is one too many (since $P$ has degree 8, all polynomials modulo $P$ must have degree 7 or less). Modular reduction really is subtracting a multiple of $P$ such that the result will have degree 7 or less (note that subtraction and addition are the same thing: a bitwise XOR). In this case, it suffices to subtract $P$ once:

$$ \begin{eqnarray*}
v\times X \pmod P &=& (X^8 + X^6 + X^5 + X^2) + (X^8 + X^4 + X^3 + X + 1) \\
 &=& X^6 + X^5 + X^4 + X^3 + X^2 + X + 1
\end{eqnarray*} $$

so the result will be 01111111 in binary, 0x7F in hexadecimal. You can check that, indeed, left-shifting 0xB2 by 1 yields 0x164, and XORing that with 0x11B results in 0x07F.

Multiplication by 3 in $GF(256)$ is polynomial multiplication by $X + 1$, followed by modular reduction. To implement that easily, reuse the multiplication by 2:

static inline unsigned
mul3(unsigned x)
{
    return mul2(x) ^ x;
}

because for a polynomial $Q$, you have $(X + 1)Q = XQ + Q$, so really it is "multiply by $X$ (i.e. "2") then add (XOR) the operand one more time".

Similarly, multiplication by 9 will be:

static inline unsigned
mul9(unsigned x)
{
    return x ^ mul2(mul2(mul2(x)));
}

because "9" is really $X^3 + 1$ so that is "multiply by $X$ three times, and add once more the operand".

This whole polynomial business, and in particular the "addition is XOR", takes some effort wrapping your mind around it; but once you get it, the rest is "easy".


How to compute a smooth-degree isogeny given a generator point of its kernel?

The complexity of Vélu's formulas scales linearly with the size of the kernel subgroup, so directly applying them to a point of huge order is not feasible for isogenies of "cryptographic" degree.

Instead, SIDH implementations decompose an isogeny of degree $\ell^n$ into $n$ isogenies of degree $\ell$. An easy way to do this is the following:
Suppose given a point $P\in E$ of order $\ell^n$, where $\ell$ is "small"; we wish to compute $E/\langle P\rangle$.
We decompose the isogeny $\varphi\colon E\to E/\langle P\rangle$ as:
$$
    E = E_0
    \xrightarrow{\psi_1} E_1
    \xrightarrow{\psi_2} E_2
    \xrightarrow{\psi_3} \dots
    \xrightarrow{\psi_{n-1}} E_{n-1}
    \xrightarrow{\psi_n} E_n = E/\langle P\rangle
    \text,
$$
where each $\psi_i$ has degree $\ell$.
A straightforward calculation shows that the kernels of the isogenies $\psi_i$ can be obtained by pushing $P$ through the previous isogenies $\psi_1\dots\psi_{i-1}$ and multiplying by an appropriate cofactor:
$$
    \operatorname{ker}\psi_i = \langle[\ell^{n-i}](\psi_{i-1}\circ\dots\circ\psi_1)(P)\rangle
    \text.
$$
Since $\lvert\operatorname{ker}\psi_i\rvert=\ell$ is small, computing each $\psi_i$ is efficient.
(Of course, this representation can also be used to efficiently evaluate $\varphi$ at a given point by simply passing the point through the chain of $\psi_i$s.)

Notice that it is this decomposition that gives the legitimate users of the system an advantage over attackers: It allows Alice and Bob to compute an isogeny in time logarithmic of the computational effort that an attacker needs to perform. In that sense, it is serves the same purpose as square-and-multiply (and its variants) for group-based Diffie-Hellman instantiations.

Finally, note that this straightforward strategy for computing $E/\langle P\rangle$ is not necessarily the most efficient possible: Depending on the relative costs of isogeny computations and point multiplications, there may be better strategies; see the original SIDH paper (Section 4.2.2) for details.


Quick and dirty solution: split the ciphertext to be transmitted into blocks with par2 and encode each block using codegroup.  Join the blocks together with some unambiguous and easily identifiable separator.
For this specific combination you could use e.g. ----- as the separator when encoding (and maybe accept any sequence of dashes as the separator when decoding).
When decoding, split the message into blocks, decode each block into bytes using codegroup (discarding any blocks that fail to decode) and them combine them using par2 to (hopefully) recover the original ciphertext.

The reason for this particular combination is the way that par2 and codegroup work:

Par2 apparently implements an erasure code that splits the input data into a sequence of blocks (of some arbitrary number of bytes, which I believe is configurable but typically on the order of kilobytes) and adds a number of redundant extra blocks that allow the original data to be recovered even if some blocks are lost.  Being an erasure code, it doesn't even attempt to correct errors within blocks — rather, it assumes that all blocks are received either correctly or not at all.

Codegroup apparently adds its own CRC checksum to the encoded message to detect errors, and refuses to decode it if the checksum does not match.  Thus, even partial message corruption will generally result in full decoding failure.

Thus, there's no point in trying to do error correction within a single codegroup-encoded message — the CRC ensures that, with very high probability, a message either decodes correctly or not at all.  (A CRC is not a cryptographic checksum, and it's possible and even quite easy for a deliberate attacker to modify a message in a way that it won't detect.  But against random message corruption it's quite effective.)
However, codegroup and par2 actually pair up pretty well, as long as you encode each par2 block separately.  Par2 wants corrupted blocks to be discarded, and that's exactly what codegroup does.  You just need to make sure that the encoded blocks are combined in a way that lets any intact blocks be reliably separated from each other and from corrupted ones.
The resulting combined scheme may not be optimal in terms of error resistance vs. length expansion, but it should work fairly well at least against rare and/or bursty errors (which, if the message isn't entirely garbled, are likely to leave enough whole blocks intact to allow decoding).  If you expect having to deal with a high rate of non-bursty errors (e.g. single bit flips), you may need to tweak the scheme (e.g. by modifying codegroup to apply a convolutional error-correcting code instead of just a CRC to the data).

Anyway, your question doesn't really deal with encryption, so its topicality here seems marginal at best.  If you do want to also encrypt your data (which you briefly allude to in your question), the general consensus seems to be that you should do encryption and error correction in separate layers: first encrypt, then apply error correction to the ciphertext.
While error-correcting codes do share some underlying mathematical similarities with some encryption schemes, in practice their goals are different enough that trying to make a single scheme do both at once seems futile.  Separating the encryption and the error correction into independent layers simplifies the design and analysis of both components and allows you to use well tested and optimized standard designs for each purpose.
(FWIW, I tried to find a good existing canonical question on that, but the closest I got was Encryption-then-encode or encode-then-encryption?, which isn't really as definitive in its conclusions as I perceive the overall consensus to be.  But it'll do for now.)


Crafting secure block ciphers that lack key expansion

The Even-Mansour construction gives you a block cipher from public, unkeyed permutations $P_1, \ldots, P_n$. It works like:

$$ x \mapsto  \cdots  P_2(P_1(x \oplus k_0) \oplus k_1) \cdots \oplus k_n $$

In original/traditional Even-Mansour, the round keys $k_i$ are independent. But recently there have been many papers studying the security of various "minimalistic" variants of Even-Mansour (basically any variant where the round keys are not independent).

The most minimal variant uses a "trivial key schedule" where $k_0 = k_1 = \cdots = k_n$. This variant naturally leads to a cipher that has no need for key expansion (key size is naturally equal to the block size). The following recent paper shows the security of 5-round Even-Mansour with trivial key schedule:

  Yuanxi Dai, Yannick Seurin, John Steinberger, Aishwarya Thiruvengadam: Indifferentiability of Iterated Even-Mansour Ciphers with Non-Idealized Key-Schedules: Five Rounds are Necessary and Sufficient, Crypto 2017


There is already enough transposition in usual block ciphers to provide enough security. You could add a simple transposition cipher on top of a block cipher but there is little reason to do so.

It would be pretty easy to perform time based side channel on the cipher is it is spread across a disk or SSD. So that would already bring down the added security.

There may also be horrible performance decreases on certain media, as already mentioned in the comments.

Basically I don't see how such a scheme would add much security, and the implications of performing the transposition are too severe.

So yeah, I guess that block ciphers + common disk encryption schemes are already "secure enough" if there is such a thing.

Besides all that, if the block cipher gets broken, don't you think it would be relatively easy to put the blocks in the right position again?

Axapaxa also makes good observation on how this won't protect single block messages.


Security benefits of Ed25519 generating signatures deterministically

The paper itself has more details on this:

  ECDSA, like many other signature
  systems, asks users to generate not merely a random long-term secret
  key, but also a new random secret session key $r$ for each message to be
  signed. ... If the same value r is ever used for 2 different messages the
  secret key can be computed as well, as ElGamal... It was reported in
  [24] that the latter failure had occurred in Sony's ECDSA
  implementation for code-signing for the PlayStation3, immediately
  revealing Sony's long-term secret key.

As is also mentioned in that section, but to avoid me quoting the TeX, actually knowing $r$ lets you recover the key directly - you don't actually need two messages using the same $r$, although as I understand it the PS3 hack used two messages.

  Since Curve22519 is Diffie-Hellman based

I think there's a slight confusion there. I believe the origin of Curve25519 was for use with ECDH,but:

Curve25519 is just an elliptic curve - that is, a curve of the form $x^2 = y^3 + ax^2 +b$. Curve 25519 is just a specific set of parameters $a,b$, as opposed to nistp-521, which is again just a different set of parameters. See Curve25519,

You can perform any group operation over a rational points on an elliptic curve (it turns out they form a group) so you can perform DH in elliptic curves. You can also perform DSA, hence ECDSA, ECDH (DSA, DH over EC).

This is the beauty of algebraic number theory :)

In this paper they are concerned with signature verification, hence the use of DSA.

  EdDSA avoids these issues by generating
  $r=H(h_b, \ldots, h_{2b-1}, M)$ so that
  different messages will lead to different, hard-to-predict values of
  r. No per-message randomness is consumed ...

From this it sounds like they're taking a hash of the message and the key (the $h_b$) and using this to derive the per-message secret (hence determinism - it is directly related to the message).

At first glance, this looks a little insecure since knowing the message and assuming a relatively short key length you could potentially compute the inverses of the hash using a rainbow table. However, bear in mind $r$ is supposed to be secret too - knowing $r$ breaks DSA.

I can't comment on its security beyond that as I am not qualified to - someone with far deeper knowledge of DSA would have to say something - but the authors are all well respected cryptographers.

  ts also not clear to me why a "fast" verification is needed in this case. It seems to me it should not matter how fast (or slow) a node or device is when verifying a signature since its not a frequent operation.

I think it depends really. If you have an embedded device, which I believe is the target here, a lower clock speed (and fewer cores) makes any verification more costly. If you go as far as say smartcards, then fast verification is desirable. Likewise, if you are producing for example a HSM or any other dedicated, embedded cryptographic device you might be concerned about performance.


SHA-1 hash where each of the first 16 bytes is even

An input with the property you are looking for can easily be found by brute force:

#!/usr/bin/python

from hashlib import sha1

def good(s):
    for c in sha1(s).digest():
        if ord(c) & 1:
            return False
    return True

for n in xrange(10**7):
    if good(str(n)):
        print n
        raise SystemExit

To double check the correctness of the result I used this command:

printf 1014746 | sha1sum | grep '^\(.[02468ace]\)*  -$'


What type of groups does Microsoft's U-Prove use (Schnorr... etc?)

U-Prove Recommended Parameters describes the groups used by U-Prove.

For the subgroup variant it references Appendix A.1.1.3 of FIPS186-3 which is about groups for finite-field based DSA. AFAIK these groups are Schnorr groups, even though NIST never refers to them as such.

The ECC variant uses standard NIST curves such as P-256, P-384 and P-521.


Any good file format alternative to PGP for encrypting data at rest?

The more I think about this, the more I think it'd be better to not do this.

I couldn't think of a single file format that would be simple enough for this - they all have atleast some structure that is hard to replicate via shell-scripts and the like. Also, security considerations for the file format crop up very easily, especially if taking passwords in to consideration as well.

From the existing utilities, I suggest a quick look at scrypt. It has a pretty simple on-disk file format and meticulous attention to detail in general. It doesn't do encryption with actual keys, only passwords, though. The problem with that is that the scrypt key derivation function uses Salsa20 internally and isn't that simple to reimplement.

But, never the less, I thought I'd create something akin to what you wanted, but without any password functionality.

genkey.sh:

#!/usr/bin/sh

openssl rand -out $1 64

enc.sh:

#!/bin/sh

KEY=$1
FILE=$2
OUTPUT=$3

HMAC_KEY=`hexdump -v -e '/1 "%02x"' -n 32 -s 0 $KEY`
AES256_KEY=`hexdump -v -e '/1 "%02x"' -n 32 -s 32 $KEY`

openssl rand -out $OUTPUT 16
AES256_IV=`hexdump -v -e '/1 "%02x"' -n 16 $OUTPUT`
openssl enc -in $FILE -K "$AES256_KEY" -iv "$AES256_IV" -aes-256-cbc >> $OUTPUT
openssl dgst -hmac $HMAC_KEY -binary -sha256 $OUTPUT >> $OUTPUT

dec.sh:

#!/bin/sh

KEY=$1
FILE=$2
OUTPUT=$3

HMAC_KEY=`hexdump -v -e '/1 "%02x"' -n 32 -s 0 $KEY`
AES256_KEY=`hexdump -v -e '/1 "%02x"' -n 32 -s 32 $KEY`
AES256_IV=`hexdump -v -e '/1 "%02x"' -n 16 -s 0 $FILE`

SIZE=`stat -c"%s" $FILE`
HMAC_BLOCKS=$(($SIZE/16 - 2))
AES_BLOCKS=$(($SIZE/16 - 3))

HMAC_FILE=`dd if=$FILE bs=16 skip=$HMAC_BLOCKS | hexdump -v -e '/1 "%02x"'`
HMAC_CALCULATED=`dd if=$FILE bs=16 count=$HMAC_BLOCKS | openssl dgst -hmac $HMAC_KEY -sha256 -binary | hexdump -v -e '/1 "%02x"'`
if [ "x$HMAC_FILE" != "x$HMAC_CALCULATED" ]; then
  echo "fuuuuu"
else
  dd if=$FILE bs=16 skip=1 count=$AES_BLOCKS status=noxfer | openssl enc -d -K "$AES256_KEY" -iv "$AES256_IV" -aes-256-cbc -out $OUTPUT
fi

Key format is:

32 bytes AES-256 key
32 bytes HMAC-SHA256 key

Encrypted file format is:

16 bytes AES IV (random generated each time)
x*16 bytes AES-256-CBC encrypted data with PKCS#5 padding
32 bytes of HMAC-SHA256 over the entire preceding file (including IV and padded and encrypted data)

The HMAC is verified first, so no data is decrypted in case the MAC is wrong. The IV is included in the HMAC, so there's no monkey business with that either. To get a less than 2-32 probability of a duplicate IV, the same key can be used a maximum of 248, which should be plenty. A single file is probably limited in length by the HMAC to be maximum of 260 - 1 bytes, which should also be plenty. There should be no attacks allowing forgery, recovery of the key or recovery of the plaintext under 2128 complexity. The entire resulting file should be indistinguishable from random except for the fact that the file size is always a multiple of 16. But no guarantees about security are given, peer review is a must.

The scripts do no argument validation and are in general written just to show how they work, not for safety or actual use. In particular, the actual encryption keys show up in command-line arguments and hence can be seen with ps by any user - so these really shouldn't be used for anything serious.


What does "Clocked" mean in alternating step generators

Clocked is an electronics term and here it applies to the LFSR's implementations;

Assume that the LFSRs are implemented with D-FLip-Flop that can store values in bits.

At each clock, the waiting input (D) passes the output (Q) and in LFSRs that go to the next cell. This is the shift operation.

The clock of the system simultaneously acts on D-fLip-flops if not controlled by some other logic. If one controls the clock with an additional logic/value as in ASG

then according to the logic, D-fLip-flop may not be clocked that result in keeping the same values. The LFSR still outputs the same value as the previous clock.

In software you can consider this like;

Have an LFSR class that hast two functions apart from the constructor, destructor, and some other utilities like the current step value;

advance() -> that shifts the LSFR and feedback the new value according to the feedback polynomial
getOutput()

According to control value, one call advance() then getOutput() or just getOutput(). The latter is keeping the previous values.


Can one construct OTPs without using XOR?

Both constructions are not perfectly secure!

In an attempt to express things a bit more mathematically, I'd say you can implement a one-time-pad with a message $m$ and a key $r$, when

$m$ and $r$ are elements of $\mathbb{Z}/n\mathbb{Z}$, the additive group of integers modulo n, or when
$m$ and $r$ are elements of a group $G$ isomorphic to $\mathbb{Z}/n\mathbb{Z}$.

Such groups would be a natural choice to implement an OTP.

There are however also other possibilities. For instance one can easily imagine a perfectly secure OTP construction where the key $r$ is an element of a group $G$ and the message $m$ is an element of a subgroup of $G$. (The key is then larger than the message).

Now, lets come back to your constructions. In both constructions you assume $r,m\in \{1,...,n-1\}$ using the unconventional notation $r,m\in(0;n)$.

Construction 1: You compute $c=r\cdot m $ mod $n$. If $n$ is a prime, then you have the multiplicative group of a prime field and it will work. As you already found out, it will not work when $n$ is composite.
Construction 2: You compute $c=r+ m $ mod $n$. It would be perfectly secure if you had $\mathbb{Z}/n\mathbb{Z}$. However, since you exclude the 0 element, you know that you always have $m\ne c$, and it is thus not perfectly secure. :)


What format should a salt be when it is concatenated with the password?

Is the salt format moot because the entropy of 32 binary bytes is the same as 42.7 base64 characters, or is one format really a better choice?

TLDR: moot, for the reason stated, as long as the whole thing is hashed and not otherwise used, and the hash used is secure, and the iterated hash construction on top of that is otherwise sound.

The fear that hashing constant bytes like =, or hashing characters from a reduced set such that of Base64, or hashing more bytes, could cause a cryptographic issue like a loss of entropy or increased risk of collision, is unfounded as long as all the data enters a good hash like SHA-256, and is not otherwise used: the loss of entropy, if any, is computationally undetectable. If it was, it would allow to distinguish the hash from a random function¹. Even though SHA-1 and MD5 are broken, they are sill safe from such problem, thus we can be quite confident about this for the stronger SHA-256.

Introducing a binary-to-text transformation (e.g. Base64) as a pre-processigng of the salt:

Slow downs the function, and that slow down benefits the attacker (which will perform the transformation only once in a password search attack). But for a well-parametrized function, that slowdown is negligible.
Increases the length of the salt as effectively used (at least it should: again truncation would be bad). If the salt was repeatedly hashed in the iterated hash (wjich is possible but not usual), that may slow down the iterated hash sizably (especially if the transformation reaches a threshold requiring more compression rounds per iteration), both for the attacker and legitimate user, thus

if the number of iterations is kept identical, the binary-to-text transformation will make the iterated hash slower, thus safer, but more costly for the legitimate user.
if the number of iterations is adjusted for constant duration, then there will be less difference in security (and we can't tell in which direction)

There can be other side effects. For example, when the key input of HMAC-SHA-256 (a common building block in iterate hash function) exceeds 64 bytes, that key is replaced by its 32-byte SHA-256 hash, requiring at least two extra compression rounds. Thus adding one byte to the key input can abruptly increase duration (and reduce the entropy from up to 512 bit to less than 256, but it's not a worrying security issue).

Notice that since Colin Percival's Stronger Key Derivation via Sequential Memory-Hard Functions (presented at BSDCan 2009), a decent iterated password hashing function must use sizable RAM memory, and ideally be memory-hard (that is, massively parallel implementation should require that same sizable amount of memory for each instance running). It considerably raises the cost of a password search setup, because RAM is expensive, and thus make iterated password hashes sizably more secure. Nowadays, using constructions that require little RAM, like PBKDF2, is either incompetent, or a deliberate way to make the system breakable by well-funded attackers, who can use ASICs to outrun legitimate users by a very large factor.

¹ Modern hashes are expected to be undistinguishable from a random function. SHA-256 is believed to match this except for its length-extension property, and there's reason to believe that it is not an issue in the context.


Is there a concept of embedding degree for non-pairing based elliptic curves?

As pointed out by @yyyyyyy, every curve does have an embedding degree, i.e., there is some $k$ for which $p^k - 1$ is a multiple of $r$, the order one of the subgroups of a curve defined over $\mathbb{F}_p$.

There is a relevant result from Koblitz and Balasubramanian that establishes that the probability that the embedding degree of a random $n$-bit curve of prime order is "small" is vanishingly low:
$$
\mathbf{Pr}[l \mid p^k - 1 \text{ and } k \le (\log p)^2] \le c_3 \frac{(\log 2^n)^9(\log \log 2^n)^2}{2^n} \,.
$$
As such, only "special" curves that are explicitly designed to have small embedding degree $k$, i.e., pairing-friendly curves, are effectively computable; but the pairing does exist for all of them.


The first method fails completely if one of the session keys gets to be known by an adversary. The idea of session keys is that a key can become known without affecting the security of other sessions. If $K_s = K \oplus R$ is known then the master key becomes known; $K = K_s \oplus R$ after all. So all sessions are now broken.

In the second method I presume that $K_s = \text{E}_K(R)$. In other words, $K$ acts as the key and $R$ as the message to be encrypted (usually we write this as $E(K, R)$ not $E(R, K)$ ...). In that case the session keys are secure, although an authentication step is indeed missing. I'm however assuming that verification of the session keys falls outside the question domain.

If $R$ is used as a key in the second method then the same issue as for scheme 1 arises: $K = D_R(K_s)$ and the master key is known.


Implications of identical round keys in AES (Rijndael)

Yes. less data complexity required to retrieve the master key.

Sub-keys can be represented by linear combination. try to xor between 2 consecutive sub-keys, you will find relations.

The paper (Low Data Complexity Attacks on AES) shows in observation 3 (page 8) a relation in consecutive sub-keys that can be exploited.


How can an unlimited adversary distinguish PRF's from Truly Random Functions (TRF)?

Let's first define the domain and range of the function we want to distinguish to be $M = \{0,1\}^m$ and $N = \{ 0,1\}^n$.

Now, what does it mean for a function to be truly random? It means that it was selected uniformly at random from the space $\mathsf{FUNC}(M, N)$, which consists of all functions from $M$ to $N$. How many such functions are there? I.e., how big is the space $\mathsf{FUNC}(M, N)$? Answer: $N^M = 2^{n \cdot 2^m}$ (exercise: prove this).

On the other hand, if the function is a PRF, then it was not drawn from the full space $\mathsf{FUNC}(M, N)$, but rather from a much smaller space indexed by the key of the PRF. That is, a PRF is formally a family of functions $\{F_k \}_{k \in K}$, where each member is a function $F_k \colon M \to N$. What we really mean when we say that the function is a PRF, is that we first pick a key $k \in K$ uniformly at random from the key space, and then we use the function $F_k$ indexed by this key to answer all queries. So how big is the PRF "function space"? It's simply the size of the key space $K$, i.e., $|K|$.

In the PRF distinguishing game we are then asked to distinguish a function which is either randomly selected from the set $\mathsf{FUNC}(M, N)$, or randomly selected from the family $\{F_k \}_{k \in K}$. For concreteness, suppose $M = N = K = \{0, 1\}^{128}$. Thus, in this case we are asked to distinguish a function which is either drawn from a set of size $2^{128 \cdot 2^{128}}$, or from a set of size $2^{128}$. Notice the massive difference in size between these two sets! The PRF family lives inside a tiny tiny tiny bubble of the whole space $\mathsf{FUNC}(M, N)$. In other words, the functions in the PRF family only exhibits a very tiny portion of all possible functional behaviors between the sets $M$ and $N$.

So how can we use this to distinguish whether the function we are given is truly random or only a PRF? Well, since we are an unlimited adversary, we can simply query the function at all possible inputs in $M$ to determine exactly which function in $\mathsf{FUNC}(M, N)$ we are dealing with. If the function does not belong to the function family $\{F_k \}_{k \in K}$, then we of course know that it was selected as a truly random function and not as a PRF. But if it does belong to $\{F_k \}_{k \in K}$, what should we guess then? I claim that we should guess that the function was selected as a PRF. Why? Well, if the function was selected uniformly at random from $\mathsf{FUNC}(M, N)$, what is the probability that it would happen to coincide with a function in $\{F_k \}_{k \in K}$? Answer: really tiny. (Exactly how tiny I leave to you to figure out).


Security Strength of BigInteger vs elliptic curve parameter value

A Type A curve has embedding degree 2. That means via the pairing we get an homomorphism from an ECC curve of bit length k to a finite field with 2 k bits (i.e. qbits).

You have to compare the complexity of:

calculating the discrete logarithm in the EC group with k bits and without using the paring homomorphism (i.e. by a generic algorithm)
calculating the discrete logarithm in the finite field with 2k bits by the number field sieve.

and take the minimum of both.

The complexity of a generic ECC DL algorithm is $2^{k/2}$

The complexity of the number field sieve for a finite field with k bits is approximately
$$\lambda (k) := \exp(1.9 (k \log (2))^{1/3} \log(k \log (2))^{2/3})$$

Therefore we have to compare $2^{k/2}$ with $\lambda (2k)$.

For big values of k, surely the factorisation in the finite field is faster then the generic ECC algorithm. So let us calculate the break-even point:

$$min_k (\lambda (2 k) = 2^{k/2})$$

This gives $k \approx 65$.
From that value of k on we can calculate the running time complexity as $\lambda (2k)$

For instance, an elliptic Type A curve with 256 bits gives you a strength of 63 bits only .

Please take this result with a grain of salt, because I have omitted the $o(1)$ term.

For real cryptographic use its maybe a better idea to use the table from the NIST SP 800-57 document:

Strength  RSA modulus size
      80        1024
     112        2048
     128        3072
     192        7680
     256       15360

For instance, that would have the following security implication:
In order to get a strong security (i.e. strength >100) type A curve, you need a finite field size of 2048 bits. This means your type A curve must have rbits=1024 and qbits=2048.


A multi-target attack on 128-bit ECDSA private keys

One $n$-bit ECDSA private key can be found from the public key with about $2^{n/2+1}$ group operations, by Pollard's rho, which is relatively easily distributed. Nothing more costly is worth consideration. For $n=128$, this is $2^{65}$ field operations and would be feasible with a large effort. This is why people use at least $\approx160$-bit ECDSA, and more like $256$-bit ECDSA or more nowadays.
It's a more interesting problem to determine if a multi-target attack can take sizably less time. I do not immediately see that it does.

How long would it take for a computer to perform $2^{64}$ ECDSA operations?

That depends a lot on:

The computer. This one is millions times faster than most others.
What's an operation. A full ECDSA signature at $n$-bit costs in the order of $n$ times more than a group operation, wich costs several field operations.
The $n$ parameter. For medium values, doubling it multiplies the cost of a field operation by like 3, of a full ECDSA signature by like 6.
The curve used. Binary curves allow faster implementation and attacks.
Competence of the attacker, which matters immensely.

Ultra rough estimate with my PC for $2^{65}$ group operations: $2^{31}\,\text{Hz}$, $2^3\,$cores, $2^7\,$cycles per field operation, we are talking $2^{65-31-3+7}=2^{38}\,s$, that's many centuries. We need too many PCs and too much energy.
Therefore the attack for $n=128$ has no practical interest, is feasible only at sizable cost, and it's better to run it as a mind or small-scale experiment.


Confusion on Private Information Retrieval by Keywords

The solution proposed in this (dated) work is an overkill considering more recent works on the subject. The simplest PIR by keyword construction I could think of is the one based on distributed point functions (DPFs).
see https://cs.idc.ac.il/~elette/FunctionSecretSharing.pdf

Distributed point functions are a special case of function secret sharing (FSS).
FSS is a primitive that is analogous to secret sharing for functions. A dealer shares a function $f:X\to Y$ by sending two shares $f_0$ and $f_1$ to two participants $p_0$ and $p_1$. Given a value $x\in X$ and his share $f_i$, every participant $p_i$ can compute a value $f_i(x)$. We require security: share $f_i$ does not reveal any information about $f$, and correctness: for every two shares $f_0,f_1$ and a value $x$, it holds that $f_0(x)+f_1(x)=f(x)$.

DPFs are FSS schemes for the class of point functions. These are functions that evaluate zero on all inputs, except one.

Now, to perform PIR-by-keyword over a databse, assume that every record in the data is of the form $(t_i,x_i)$ (a tag and a value). When the client needs to retrieve a value with the tag (or keyword) $t$, he secretly shares the point function $f$ for which $f(t)=1$ and $f(t')=0$ for any $t'\neq t$. He sends each of the shares $f_0,f_1$ to one of the servers. Server $i$, in his turn, computes $x^{(i)}=\sum_{j=1}^N f_i(t_j)x_j$. It is easy to see that from the security of the DPF, the scheme is secure, and from its correctness, the client can compute $x:=x^{(0)}+x^{(1)}$.

The DPF scheme proposed in the work mentioned above costs $O(n)$ bits of communication when the keywords are of size $n$ bits.

Notice that this construction assumes the keywords are all distinct.


Ok, it answer the specific question you asked:

Bernstein says that it needs 640383 cycles for one multiplication

Actually, when Dan talks about "multiplication", he is referring to a "point multiplication", that is, to the computation of $[n]P$ (given a large integer $n$ and a point $P$).
In your simple-minded brute force search, you don't need to do a full multiplication each time.  Instead, when you have computed $[a]P$ (and decided it is not $Q$), you can step to the next one by computing $[a]P + P = [a+1]P$; this is a point addition (and incrementing the value $a$ you're keeping track of), this is much cheaper than the full point multiplication operation.
Now that is mentioned the obvious misstatement in your analysis, some general advice; to do a reasonably thorough security analysis, you'd need to consider:

The various computational models that an adversary may have available; in addition to a single large computer, the adversary may have a large number of smaller computers, a set of GPUs, a set of FPGAs2 or even (if his budget allows) some ASICs.  Dan used floating point in his implementation, but that's because modern CPUs have some pretty fast floating point logic, and he took advantage - however, there are a lot of gates tied up in this fast floating point logic; some of the other computational models would use different strategies.

The various attacks; in addition to the rather naïve brute force search, you would also need to consider various "square root" attacks (such as Baby Step Giant Step and Pollard Rho (and parallelized versions), and also the MOV (which doesn't apply to Curve25519, however you'd need to learn why).

What Dan wrote is a decent starting point; however he assumes that the reader is already familiar with the basics of elliptic curves; I suspect you'd want to do some reading to catch up...


How exactly to concatenate two differential trails to form a boomerang disguisher in practice?

In this case because the trail $E_1$ begins at the stage in the cipher directly after the trail $E_0$ ends you can use $E_m$ as the identity map which preserves all differences with probability one.
Thus to generate data to exploit the distinguisher, start with an arbitrary plaintext, say 0x0123 and call the chosen plaintext resource for both this and its paired $E_0$ input (in our example 0x0122). Both of these will lead to outputs after four rounds, say 0xdead and 0xbeef. Now call the chosen ciphertext resource the paired $E_2$ outputs of these ciphertexts (in our example 0xdeac and 0xbeee). If any we fall off either difference trail these won't produce anything useful, but a positive proportion of the time they should decrypt to a pair with the input difference of $E_0$, say 0xf00d and 0xfooc.
To understand the interaction in the middle, suppose that all difference trails are followed precisely. Suppose also that our initial input 0x0123 reached the state, say 0x3141 after two rounds; by the $E_1$ path our input 0x0122 would have moved to state 0x3750. Now consider the states 0x0050 and 0x0641 after two rounds. The (0x3141, 0x0050) states are a $E_1$ input pair and the (0x3750,0x0641) are another $E_1$ input pair, which would both indeed lead us to an $E_1$ output pair (0xdead,0xdeac) and (0xbeef,0xbeee) respectively. Likewise (0x0050,0x0641) represents an $E_0$ output pair which should back up to a $E_0$ input pair (0xf00d,0xf00c) in our example.
Four difference trails have to be respected for this observation to be causal: 2 copies of $E_0$ and two copies of $E_1$. Thus if the probability that $E_0$ is followed is $p_0$ and the probability that $E_1$ is followed is $p_1$, the probability of the boomerang observation is $p_0^2p_1^2$.
The above contains a subtle assumption of independence. In differential trails we can usually assume independence of the individual steps by assuming that round key has a randomising effect. In boomerangs attacks we are tracking four trails and assuming that they behave more or less independently. The assumption of independence is strongest where the upper and lower trail meet and, say, in our example we assume that the probability that $F(x\oplus\Delta_{0,i})$ equals $F(x)\oplus\Delta_{0,o}$ is independent of the probability that $F(x\oplus\Delta_{1,i}$ equals $F(x)\oplus\Delta_{1,o}$ and also the probability that $F(x\oplus\Delta_{0,i}\oplus\Delta_{1,i})$ equals $F(x)\oplus\Delta_{0,o}\oplus\Delta_{1,o}$ when we're talking about the same input value $x$ for all three probabilities instead of randomising each $x$ with round key. This interdependence can greatly inflate or reduce the probability of observing the boomerang statistic and modern developments such as the Boomerang Connectivity Table try to account for this dependence by generating a single probability to account for all three events. To separate out this interdependent step, we can make it a separate stage of our encryption $E_m$. In our case, linear steps can be passed through with probability 1 and independence and we'll extend to that $E_0$ ends immediately before an $S$-box (as it already does) and $E_1$ starts immediately after an $S$-box (for this we pass back through $X^{-1}$ and $L^{-1}$ and append these to the start of our $E_1$ trail). We can now call $E_m$ the transition through our $S$-box and use the BCT to estimate the interdependent probability of transitioning between $E_0$ and $E_1$.


Is there a formula for calculating the inverse of a sum in modular arithmetic?

Is it possible to write $h_2^{((x+1)^{-1})}$ as some combination of $g$ and $h_1$?

No.  Computing $h_2^{((x+1)^{-1})}$ from $g, h_1$ is equivalent to the Computational Diffie Hellman (CDH) problem, which we believe is difficult for some groups.

Here is the proof in the forward direction (your problem is at least as hard); suppose that we had an Oracle that, given $g, h_1 = g^{x+1}$, was able to give us the value $h_2^{((x+1)^{-1})} = g^{x \cdot (x+1)^{-1}}$

First of all, let us set $y = x+1$, and rearrange the Oracle "given $g, g^y$, give us the value $g^{(y-1) \cdot y^{-1}} = g \cdot g^{-y^{-1}}$; with this Oracle, we can easily reconstruct the value $g^{y^{-1}}$.

It is well known that computing the value $g^{y^{-1}}$ given $g, g^y$ is equivalent to the CDH problem; given $h, h^a, h^b$ compute $h^{ab}$.  This is done by turning the inverse Oracle into a squaring Oracle (given $h, h^a$, compute $h^{a^2}$).  To do this, we set $g = h^a$ and $g^y = h = (h^a)^{a^{-1}}$; we give those two to our inverse Oracle, which returns us $(h^a)^a = h^{a^2}$

Once we have a Squaring Oracle, we can directly solve the CDH problem by computing $h^{a+b} = h^a \cdot h^b$, and then computing $h^{2ab} = h^{(a+b)^2} \cdot (h^{a^2})^{-1} \cdot (h^{b^2})^{-1}$, then a modular square root gives us $h^{ab}$

And there we are done.  (Showing the proof in the other direction isn't hard, but I'll leave that as an exercise for the reader)

Hence, if we have a generic way of solving your problem (e.g. by doing algebraic rearrangement of $g$ and $h_1$) that works in an arbitrary group, well, we just showed that the CDH problem is never hard, and we don't currently believe that.


Malicious party security model: When one party is corrupted at a time

$A$ has outsourced it's private data to the server, right? In that case $A$'s private data has already been leaked to the adversary when the server was corrupted. So there is no added leakage in $B$ also learning this data. In fact since only one of $B$ and the server can be corrupted (assuming static corruptions) we can conclude that $B$ is honest, and there is really no problem.


Why has the RSA factoring challenge been withdrawn?

RSA themselves (the company) say this in their RSA Factoring Challenge FAQ:

Why is the RSA Factoring Challenge no longer active?
Various cryptographic challenges — including the RSA Factoring Challenge — served in the early days of commercial cryptography to measure the state of progress in practical cryptanalysis and reward researchers for the new knowledge they have brought to the community. Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common symmetric-key and public-key algorithms, these challenges are no longer active. The records, however, are presented here for reference by interested cryptographers.

This, of course, does not really answer the question. Although there have been many optimizations, and computers have quite grown in both CPU power and RAM size, the best known algorithms for factorization have not qualitatively changed since the late 1980s, when the General Number Field Sieve was discovered. Even with GNFS, today's computers, and the fine brains of the authors of the RSA-768 factorization, a 1024-bit RSA modulus still seems out of reach. The money at stake was sizeable for an individual, but not that much for a company such as RSA (there was a 100k\$ prize on RSA-1024, 150k\$ for RSA-1536 and 200k\$ for RSA-2048; RSA Security appears to have a yearly revenue of more than 700 millions of dollars).
My guess is that they withdrew the challenges for a mixture of the two following reasons:

When a RSA challenge is broken, it makes bad press, and the press is worse if there is a prize, because it may serve as an highlight on the event (which is otherwise extremely technical).

An open challenge with a prize implies some kind of provisioning, which is bound to upset someone in the accounting department.

So, at some point, RSA Security decided that the inconvenience of maintaining the challenges exceeded the inconvenience of withdrawing (which your question incarnates: a suspicion of potential weaknesses).
One might notice that the withdrawal happened at about the same time than the bulk of the sieving work for RSA-768 began -- I do not have the exact timing, but it is conceivable that the withdrawal decision had been pending for awhile, and was triggered by rumours of the RSA-768 factorization effort.


RSA: Should the generation of random data used for primes include zero

When generating random data that is later tested for primality, should the random data include the value 0x0?

I'm reading this as: should the hexadecimal expression of the primes include the hexadecimal digit 0?

With hight likelihood yes. But that needs not/should not be tested. Common wisdom is that except for the few high-order bits (constrained by range considerations) and the low-order bit (which is set), all bit sequences much shorter than the prime itself should be random-like, thus about 1/16 of hexadecimal digits other than the low-order and high-order are expected to contain the hexadecimal digit 0x0.

  (Aren't) keys generated with no zero's easier to brute force?

Not sizably. Indeed, preventing the hexadecimal digit 0x0 to appear would reduces the possible primes. However, there remains so many that trying to factor an RSA public modulus by enumerating the candidate primes (roughly $2^{510\cdot15/16}/\log(2^{512})>2^{469}$ for 512-bit primes suitable for 1024-bit keys of FIPS 186-4 format) remains  hopeless anyway. And we know no efficient factorization algorithm that can take advantage of the special form of these primes.

  (..) my colleagues are of the opinion that having zero in the prime data makes the key operations consume less time / and or power, and thus make these keys more vulnerable to a DPA / timing based attack. They have also seen open source code that removes zeros from the random data.

To my knowledge, there is no evidence that accidentally having zeroes in the hexadecimal expression of the primes has sizable chance to enable a DPA / timing based attack. Arguments: long sequences of zeroes will be statistically rare; if there's data-dependent timing variation or potential for DPA attack in an implementation, that must be mitigated anyway; we could make the same argument for 0xF; on the contrary, knowing that there are not zero could conceivably speed-up some side-channel attack.

I do not know an open source RSA key generation code purposely weeding out primes with an excess of zeroes. And I'm reasonably confident that no public standard (from ANSI, BSI, ETSI, IEC, IETF, ISO, NIST, or the company formerly known as RSA security) asks for that. Do the person(s) with this recollection also remember what open source code does that, so that said recollection can be cross-checked, and perhaps a rationale found from comments or a reference?


If he gets the signature for the message 00000..00000, then the checksum will be $t_1 2^w$.  For any other message, the checksum will be smaller, and hence the there will be at least one digit $i$ within the checksum for which the $c_i$ digit with value $v$ for the signed message will be larger than the corresponding digit for the new message.  The attacker does not know the $\mathcal{H}^{v-1}(x_{i+t_1})$ preimage for that digit, and hence he is unable to forge the signature.

That is the idea behind Winternitz; for any two messages $M_0$ and $M_1$, then either there will be a digit within $M_1$ which is smaller than the corresponding digit within $M_0$, or there will be a digit within the checksum for $M_1$ which is smaller than the corresponding digit within the checksum of $M_0$


Is there a lower limit on message length for signature?

The lower limit is a single byte.  Ed25519 is not defined for units smaller than a byte, but if it were, there would be, in principle, no security issue with signing a single-bit message: the expected cost of forgery on a message of any length, from a bit to an exabit, remains near $2^{128}$ and therefore well out of reach for humanity.


Secondary private key that produces limited certificates

When a user which owns a private key produces a secondary key, they essentially say "I grant the carrier of this token permission to act as me for this purpose for this period of time".

You could use the original private key to sign that message exactly.

The original keyowner Alice signs a message encoding "The carrier of this signed message has permission to act as me (id/pubkey:XXX) with caveats A,B,C (ie. permissions to _, expires at _)", and gives that signed message to Bob. Bob can now make requests to the server and include that signed permission slip in his requests as his authorization to act as Alice.

You could then change the design to be freely re-delegatable by making the message instead be "The user identified as id/pubkey:YYY has permission to act as me (id/pubkey:XXX) and delegate with caveats ...". Alice can create a message like this specifying Bob's public key as YYY, and give the message to Bob. Bob could make requests to the server including this signed message as his authorization, but could also create his own version of this to delegate permission to Alice's account to Charlie. Bob would give Charlie this new message and Alice's original signed message. Charlie could then make requests to the server and present a chain of messages showing the delegation of permission to Alice's account from Alice to Bob to Charlie.

This final design is pretty much equivalent to Macaroons (see also the answer of cypherfox) with the bonus that anyone could verify the permission slips, not just the server. But if you don't need that, macaroons are likely to be much more compact than using asymmetric crypto.