Knowing pre-encryption data, can we find the private key CryptoWall used? I'm just repurposing a question already asked about Cryptolocker for CryptoWall:

  "If we know exact contents of some of the files prior to them being encrypted, would it be feasible to use those files to discover the private key?"

There's an answer posted for the case of CryptoLocker, but what about for CryptoWall?  I've read it is not as thorough, for instance not using the type of RSA encryption meant for large blocks of data.

According to the Dell SecureWorks link from the comments, CryptoWall used/uses RSA encryption directly on the files:

  File encryption begins after CryptoWall successfully retrieves the RSA public key from an active C2 server. Therefore, using network-based controls to block this communication can prevent compromised systems from becoming encrypted. Unlike CryptoLocker's use of a symmetric cipher, such as AES, to encrypt bulk data, CryptoWall uses the RSA public key to directly encrypt files. Because the RSA algorithm is far more computationally intensive than symmetric ciphers, compromised systems experience significant CPU load after CryptoWall compromises as files are encrypted.

This alone could allow some data to be decrypted due to weaknesses of textbook RSA if it is naively blocking files and using raw RSA. For example, anything that can be guessed could be verified, and the last blocks of files could be small enough to be brute forced. It would not help in finding the private key, however.

Additionally:

  CryptoWall variants deployed before April 1, 2014 contained a weakness in the cryptographic implementation that allowed recovery of the key used to encrypt files.

According to Symantec the private key was present on the infected computer and sent to the command server:

  The Trojan then sends the private key back to the remote server. After the remote server confirms that it has received the key, the Trojan will send a screenshot of the computer’s desktop to the remote server.

More newly infected users would seem to be out of luck (from first link):

  This flaw appears to have been corrected in later versions of the malware. CTU researchers have not performed a rigorous assessment of CryptoWall's cryptographic implementation, but they have not discovered any obvious flaws that allow decryption without payment.


Why are there standards of encryption? Pardon me if this question seems a bit obvious, but if someone has a key to your encryption, knowing what type of encryption you are using (or running outputs against a lot of common encryption types) gives them the opportunity to reach your data using said key. So wouldn't it be better if you encrypted according to a non-standard form of encryption, hence removing the need for standards?

Maybe I misunderstood but it seems like you suggest hiding the encryption algorithm instead of your secret key, basically. Firstly, it is useless in any scenario that you want to send data to someone else to decrypt. If you aim to encrypt values so that only you will be able to decrypt them, think about which one is easier, hiding an algorithm from someone else or just a key?


Zero knowledge proof for a discrete logarithm Say a have a group $G$ chosen as $Z_N^*$ where $N=pq$ and both $p$ and $q$ are safe primes. The algorithm for discrete logarithm is as follows:

Pick $g$ as a random element from $Z_N^*$
Pick $x$ as a random element from $(0, N')$ where ${N' =  p' q'}$ where ${p=2p' + 1}$ and ${q=2q' + 1}$
Evaluate ${y = g^x \: mod \: N}$

For public $y$ and $g$, what is the easiest way to construct ZKP that the prover knows $x$ without revealing it?

This problem was studied in [BCK], and interestingly they showed that constructing a Schnorr-like zero-knowledge proof system (ZKP) in a group of unknown order with non-trivial soundness error is not possible in the plain model (i.e., without CRS). Their result is much more general and talks about homomorphisms in groups of unknown order.

However, if one considers the CRS model, then [BBF] recently showed that ZKP is possible in the generic group model under the "adaptive root" assumption. Boneh talks briefly about this work here.

[BBF]: Boneh, Bünz and Fisch, Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains, Crypto 2019

[BCK]: Bangerter, Camenisch and Krenn, Efficiency Limitations for Σ-Protocols for Group Homomorphisms, TCC 2010


Independent parameters basis for torsion-groups in SIDH: Is the Weil-pairing necessary? In the original SIDH paper by De Feo, Jao and Plût, the basis points $P_A$ and $Q_A$ are supposed to be independent points in $E(\mathbb{F}_{p^2})$ of order $\ell_A^{e_A}$ for some small prime $\ell_A$ on some supersingular curve $E$. To check independence, they suggest computing the Weil-pairing $e(P_A, Q_A)$ and check that the result still has order $\ell_A^{e_A}$.
My question is this: Is another valid approach to checking independence to check if some discrete logarithm exists from one point to the other? Of course, $|E[\ell_A^{e_A}]|$ is $\ell_A$-power smooth, so taking discrete logarithms is easy by Pohlig-Hellman, but I am sure if this approach is valid/equivalent with calculating the Weil-pairing.

As you mentioned, computing the discrete logarithm is an easy way to check for linear dependency. The usual way to compute discrete logs over elliptic curves relies on some pairing, but there are ways to do so without any pairing. See for instance "Isogeny-based key compression without pairings" at PKC'21 (https://eprint.iacr.org/2021/272.pdf), where pairing-less discrete logs are used for key compression.


Collision resistance of hash functions with short, fixed-length inputs? Regular hash functions like SHA-256 have a variable length input and measure security against collision attacks in bits. For SHA-256 this is 128 bits. When I limit the input length of SHA-256 to for instance a fixed 8 bits, the chance of a collision drops to zero (with SHA-256 there are no collisions possible with only 256 inputs, all inputs have an unique output).
How much can I truncate the output of the SHA-256 with a fixed input length of 64 bits so that I keep the same collision resistance strength characteristics as the original SHA-256 with variable length input?

SHA256
The Max File Size
First of all the variable length has a limit due to the padding of SHA256. A message with length $\ell$ is padded with a 1 with necessary minimal $k$ zero bits so that
$$\ell+1+k ≡ 448 \bmod 512$$
This upper limit, actually, due to the Merkle-Damgård (MD) design of SHA256. MD based hash functions are vulnerable to length extension attacks and appending the length simplifies the security proof.
The Collisions are inevitable
Since the output of the SHA256 is limited to 256 bits and the input to $2^{64}$ bits. By the pigeonhole principle there is a least one hash output that contains more than one input. Therefore, there is always collisions.
Actually, if we consider that the SHA256 behaves uniformly, then we expect that all of the output values are equally distributed. A simple and similar experiment done for SHA-1
The generic collision attack
The generic collision of hash functions is calculated by the birthday paradox, and in cryptography, it is called birthday attack.
For a hash function with $t$ bit output the attacks requires $\mathcal{O}(\sqrt{2^{t}})$-time with %50 probability. For SHA256 this is $\mathcal{O}(\sqrt{2^{256}}) = \mathcal{O}(2^{128})$-time with %50 percentage.
Questions

When I limit the input length of SHA-256 to for instance a fixed 8 bits, the chance of a collision drops to zero (with SHA-256 there are no collisions possible with only 256 inputs, all inputs have a unique output).

You consider the reverse case. You limit the input space to 8-bit, i.e. 64 elements. Seeing a collision here is near to zero. Now you tested it experimentally and it is zero. Actually, this is like one throws 64 balls into the air and you expect them to get some of them into the same bin from $2^{256}$ bins. Hopefully, SHA256 is not such a bad hash function that doesn't have a collision with these very related inputs that have almost 8 bits differs. Theoretically, we expect the hash functions have the avalanche effect that changing one bit flips the output bit with %50 percentage. This distributes them randomly.

How much can I truncate the output of the SHA-256 with a fixed input length of 64 bits so that I keep the same collision resistance strength characteristics as the original SHA-256 with variable-length input?

$2^{64}$ cannot be easily tested for this size due to the memory and CPU requirements, entities like Google can test it like in their SHA1 experiment.
If the time is not a problem then one can build a Rainbow table to see the existence a collision or not. We, however, can calculate a probability for this assuming the $n=2^{64}$ values are chosen randomly, not sequentially.
$$ 2^{64} \approx  \sqrt{2 \times 2^{256} \times p(n)}$$
$$2^{128} \approx 2 \times 2^{256} \times p(n) $$
$$ p(n) \approx \frac{1}{2 \times 2^{128}}$$
This is the probability of having a collision of randomly chosen $2^{64}$ values for SHA256. This is not going to happen.
Small input space
In Cryptography, we want the hash functions to have the pre-image resistance. Almost all cryptographic hash functions are secure against pre-image attacks. There is one special case of this attack that when the input space is small, then the attackers can calculate, too. In this case, the $2^{64}$ Input space may not be enough to protect the data. To mitigate a keyed hash function like HMAC or KMAC is advised.


Will changing the RSA Padding in OpenSSL cause issues? I'm currently looking at changing the padding type from one of the Oracle Padding attacks to a secure one. Would this break data already encrypted using the old method?

Yes, every RSA padding I'm familiar with is incompatible with the other schemes.


Generalization of the DL-assumption in bilinear group pair When thinking about a pairing-based cryptographic scheme, I encountered the following problem. Let $e \colon G_1, G_2 \to G_T$ be a Type 3 pairing. Then:

  Given $P, zP \in G_1$ and $Q, zQ \in G_2$, compute $z$.

I haven't found this problem in the literature anywhere, so I am not aware of any name of it. It clearly implies the discrete logarithm problems in $G_1$ and $G_2$, but those two do not seem to imply this problem on their own or combined. On the other hand, it is implied by the co-CDH* as well as the q-SDH assumptions - but those are stronger than I need.

I'm wondering the following two things:

Has this problem appeared anywhere in the literature?
Is it implied by any other common assumptions?

It seems very natural to assume the hardness of this problem in a Type 3 cryptographic scheme. Usually the point of working with a Type 3 pairing is exactly to have such a tuple, and use the pairing to decide if the fourth element indeed equals $zQ$ or some other element. So if this problem is not hard and $z$ is private, then you're in trouble.

Usually the point of working with a Type 3 pairing is exactly to have
  such a tuple, and use the pairing to decide if the fourth element
  indeed equals $zQ$ or some other element. So if this problem is not hard
  and $z$ is private, then you're in trouble.

From your explanation, I don't think you require a Discrete Log-like assumption. You are saying that the pairing is used to check if some element is indeed $zQ$ or some random value. This seem to imply that $P$, $zP$, and $Q$ are known to an adversary, and you want to ensure that an adversary cannot produce a value that passes the check you make with the pairing.

Assuming I understood this right, then this seems to be a fit for the Computational co-Diffie Hellman problem (co-CDH): given $P$, $zP \in G_1$, and $Q \in G_2$, the co-CDH problem is to output is $zQ \in G_2$. This output is what you are checking with the pairing, so it seems to me that the co-CDH problem is what you are looking for.

In this case, a Discrete Log-like assumption may be overkill, since an adversary wouldn't need to find $z$. It suffices to compute $zQ$.


How secure is a hash based signature scheme after signing assuming quantum computers? Consider a hash based signature scheme that requires taking the $k$-bit hash of an arbitrary length message to be signed (e.g. Lamport one-time signature scheme). My understanding is, assuming that this step is the weakest point of the signature scheme and that the hash function used is collision resistant, this signature scheme offers $k$-bit security before signing and $k/2$-bit security after signing (since anyone trying to forge a signature will on average get half the bits for free when taking the hash of any message they are trying to sign).

My question, then, is what is the security of such a signature scheme if an adversary is trying to find a hash collision with a quantum computer using the best quantum algorithm currently known for finding hash collisions?

The answer to this question:

Hash-based signature scheme XMSS/LMS susceptible to preimage/second preimage attack?

provides helpful information and implies that this scheme would still offer $k/2$-bit security as

"Grover’s algorithm allows us to find preimages with a complexity of $Θ(2^{/2})$ in a quantum world, however the birthday paradox bounds the complexity of the collision-resistance in the classical world already. (And we don't know a better way to go around it in the quantum world..."

citing this paper:

[1] https://cr.yp.to/hash/collisioncost-20090517.pdf

which appears to debunk the claims of this paper:

[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.5265&rep=rep1&type=pdf

that presents a quantum algorithm to find collisions more efficiently.

The argument presented by [1] seems to make sense (i.e. that the work presented in [2] makes the unrealistic assumption that communication is essentially free), but I am not knowledgeable enough in this area to analyze it more thoroughly. To those who are: is this argument valid? What is the general consensus of quantum cryptography researchers?

Finally, the author in [1] also states the following:

"In fact, time $2b/3$ had already been achieved by non-quantum machines of size just $2b/6$, and smaller time $2b/4$ had already been achieved by non-quantum machines of size $2b/4$. Anyone afraid of quantum hash-collision algorithms already has much more to fear from non-quantum hash-collision algorithms."

What algorithms is the author referring to here? Does this mean that the post-sigining security of signature schemes using a k-bit hash function is already less than $k/2$ bits even without quantum computers?

Two things:

The question "how hard is the oracle-based collision-finding problem be for a Quantum Computer" is an open question; we know that it is somewhere between $O(\sqrt[3]{n})$ and $O(\sqrt{n})$ effort (I recall a paper showing that $O(\sqrt[3]{n})$ Oracle queries is the lower bound, but I forget what paper that was) - we don't know where in the range it actually is.  Brassard et al showed an algorithm that found collisions with $O(\sqrt[3]{n})$ Oracle queries; however Dan pointed out that the other costs associated with the algorithm made it actually more expensive than just running a large number of second-preimage finders in parallel [1].  What is currently unknown whether there exists another algorithm that uses $o(\sqrt{n})$ Oracle queries [2], and doesn't have the other expenses that the Brassard algorithm has...

The three current 'hash based signature standards', namely, LMS, XMSS and Sphincs+ don't actually rely on collision resistance, even when doing the initial hash of the message.  What all three do is, when the signer is given a message $M$, the signer selects an unpredictable $R$ and then computes $\text{Hash}(R + M)$ (and then uses that hash for the rest of the signature operation).  If the adversary submits a message to be signed, he doesn't know what the value $R$ that the signer will select; instead, to perform a collision attack, he would need to select two distinct messages $M, M'$ for which $\text{Hash}(R + M) = \text{Hash}(R + M')$ with nontrivial probability (given the probability distribution of $R$), and that would appear to be far more difficult than finding a collision.

[1] The Brassard algorithm is essentially a large multi-target second preimage attack, and Dan's complaint is that the quantum logic to do a recognization over a large sparse unstructured space is quite expensive. In an unpublished work, I looked at the Brassard algorithm, and searched for the 'sweet spot' between 'number of targets per searcher' and 'number of searchers' - based on the published SHA-256 Quantum circuit, and a sketched out target recognizer circuit I drew, I came to the conclusion that this made the problem circa a factor of 1000 cheaper to attack than a single preimage problem (and the sweet spot was circa a million targets per searcher).
[2] For those who are unfamiliar with little-oh notation, $o(\sqrt{n})$ means 'fewer than $c\sqrt{n}$ queries, for any $c > 0$ (as long as $n$ is large enough, and the meaning of "large enough" depends on $c$).  More colloquially, $o(\sqrt{n})$ means 'grows slower than $\sqrt{n}$'


Recovering key in AES - Infinitely many known plaintext ciphertext pairs Is it possible to recover key/algorithm in AES encryption more efficiently than via brute force given attacker has access to arbitrarily many plaintext ciphertext pairs. If so, are there other known techniques which are secure even in the scenario of arbitrarily many known ciphertext plain text pairs?

For any given AES key there are only $2^{128}$ possible plaintext-ciphertext pairs, so you can never have arbitrarily many such pairs.  Moreover, if the attacker has access to all $2^{128}$ such pairs for a given key they can mount a "code-book" attack, whereby they don't need the key at all to decrypt any message that they want to decrypt.  For example, if they see any particular 128 bit block of ciphertext the attacker can simply query their database of possible plaintext-ciphertext pairs and directly find the corresponding plaintext, without ever needing to go through the trouble of breaking the key.


FIPS 140-2, Level 1 validation vs. compilation I'm working on a system that needs to use cryptographic functions that must be FIPS 140-2, Level 1 validated. The challenging part is that some of this system needs to run in the browser. For maintainability reasons and ease of use, I would really like to avoid having to resort to applets or browser plugins or Active-X controls or something of that sort, and would much rather build this part of the system in JavaScript.

So, I've been searching for validated JavaScript modules, but this website:

https://csrc.nist.gov/Projects/Cryptographic-Module-Validation-Program/Validated-Modules/Search

which lists all (?) currently validated modules if you click on "Show All", does not give me much hope to find one.

So, here's what I'm thinking:

Can I take one of the Java modules (like Bouncy Castle) and cross-compile them to JavaScript using something like GWT?

Or can I take one of the C or C++ modules and compile it into asm.js?

Or, to ask the question even more generally: How does (cross-)compilation or translation of validated code affect the validation?

I wouldn't give much hope in finding a native Javascript crypto implementation that's FIPS certified.  The reason is zeroization; FIPS is particular about knowing when CSPs [1] are zeroized; Javascript does garbage collection, which means that you're never quite sure when things are zeroized.
And, if by cross-compiling, you mean taking a certified implementation, and automatically converting it into Javascript, well, you won't solve the problem.
Sorry, but I wish I had better news for you.

[1]: Critical Security Parameters; essentially FIPS terminology for keys


Universally verifiable random beacon I am developing a network where potentially many many nodes (billions, in principle?) should be able to agree on a random number. I would really prefer to avoid $O(N^2)$ procedures where everyone contributes with some randomness and then everything is shuffled together. So I am looking for a random beacon.

I would also prefer to avoid random beacons generated from $O(N^2)$ sources, like Bitcoin. So I wonder: is there a random beacon that is:

Unpredictable
Universally verifiable
Impossible to pilot (i.e., no organization, no matter how powerful, could alter its values or predict them)

I don't really care about its bitrate (if it produces just a few random bits per hour, so be it).

Here are some solutions I thought about (but they don't seem very feasible):

Solar flares: their occurrence is random, and they interfere with VLF communications. But their time is not so narrowly defined, and their occurrence is really rare, in then order of once a week. Also this requires everyone to have an antenna. And maybe an attacker might interfere itself with VLF transmitters.
Lightnings: they strike much more often, but their signal can be detected (also with VLF antennas) only maybe a few thousands kilometers from the lightning. So it wouldn't be global.
Earthquakes: detectable everywhere, but again, not such a precise time definition, and requires a very sophisticated instrumentation.
Random beacon satellite: we could send a cubesat in orbit to generate random numbers and broadcast them down to Earth. I could add proximity sensors or accelerometers so that any approach results in terminated communications to prevent tampering. This would also be great because I would only need a receiver station and then the numbers could be broadcasted via the Internet. But maybe a motivated enough organization could find a way to... I don't know, tamper with it so as alter its behavior? Even in space?
Same as above, but with an hidden verifier that knows the satellite seed and is able to check that the numbers are correct, and is always silent and undetectable. But then, how do I hide it? Without a human that can be tortured or whatever and disclose its position? Also this wouldn't protect the satellite from having its seed copied. And how would I go about maintenance for the hidden verifier?
One that might also work: VLF receivers tuned on encrypted shore-to-submarine transmissions of multiple nuclear powers. Transmissions can be received basically anywhere in the world, but being encrypted I guess they can be used as a more than decent source of randomness? Obviously a nuclear power could send gibberish to its submarines to make its beacon non-random, but if I use multiple sources then multiple nuclear powers should agree to at the same time jam their own communications with their nuclear submarines... while also letting every other nuclear power know about it, since they should coordinate! Quite unlikely. Might this work? But (sigh) it requires everyone to have a VLF antenna.

Here is where I stop. Any more sensible solution?

There is no sensible solution to this.  It is impossible, even if this was not a hypothetical question.  It cannot be done for primarily two reasons:-

You cannot have the nodes measure any analogue quantity.  Analogue measurement noise will govern the accuracy of the reading.  Coupled with the typical hash based randomness extractors, the avalanche effect will guarantee that every node will generate a different random number.
So you're left with digital entropy acquisition.  Lottery results are good but there's not a lot of them to get the few bits /hr (maybe just - you'd have to do the math).  This was done for the Million Dollar elliptical curve. Much larger quantities of digital randomness can be obtained from international market information acquired via the appropriate APIs.  This will gradually fail though.  Spotty developers will change the access APIs every 18 months.  The nodes will gradually lose access to the digital entropy.    This gradual degradation of sources will affect the nodes no matter what sources they use.  The API degradation issue would also affect the lottery technique. And.  You can't update the nodes as that would put them under singular control breaking your initial premise.

The only kinda solution (breaking many requirements) is to use a distribution network sending out randomness like the NIST Randomness Beacon.  But it would have to be under international /UN control and inspection and outside of US jurisdiction.  It can't be NIST itself as that is a politically controlled arm of government (US Department of Commerce.)  Or do the same for updating the nodes with new market access APIs.  If the nodes were open hardware /open source based and not sealed, it would then be possible for hackers /scientists and journalists to verify their on going correct function.  But that would then allow prediction of the random numbers as the entropy and algorithm would be known.


Disk storage of RSA and DSA keys I have generated one RSA-2048 signing key and one DSA-2048 signing key, using gpg command

gpg --full-generate-keys

I would expect the key to have size 2048 bits, however, running the command

gpg --export-secret-keys <key-id> | wc -c

gives a size of 1353Bytes for the RSA private key and 1103Bytes for the DSA private key. The public keys are 656Bytes and 1020Bytes.

Why is this? Is this because the exponent and primes, passphrases, my name etc are stored together with the keys?

Yes. There is a difference between key strength, key size and the size of the encoding of a key.

The modulus of the RSA private key determines the key size, for instance, but an RSA key commonly also contains the public, private exponent and CRT parameters, an encoding structure etc. etc.

In GPG indeed the "key" consists of many additional parts as well (as you can see from the size). You can packet-inspect the keys in GPG by simply performing gpg <exported-key>.

See here for more information (and note that the question really belongs on Superuser, but whatever).


Lehmer random number generator - cipher? Let's consider linear congruential generator:
$X_{k+1} = a \cdot X_{k} \mod 2^{128}$
Such that $a$ is some number which for every 128-bit input $X_{k}$ from $0$ to $2^{128}-1$ will give us different output $X_{k+1}$ from $0$ to $2^{128}-1$. So we got bijection here (we can find many such $a$).
Now let's say we will choose such 128-bit $a_{1},a_{2}, ..., a_{10}$ as a keys, randomly. We make $10$ rounds of encryption and every round compute:

$a_{i} \cdot INPUT \mod 2^{128}$
Reverse 128-bit block.

So the next round input is an inverted block of previous round output. And it looks like it make a big difference. If we wouldn't reverse block - we got just keyed Lehmer random number generator with a modulus which is a power of two - and it is definitely not secure (because the low $k$ bits form a modulo-$2^{k}$ generator all by themselves).
But with "reversing" we get completely different results! It looks chaotic. I have no idea is 10 rounds enough - just guessing. Is this type of encryption secure? Do you see any obvious weaknesses? To analyze it we can choose smaller keys and smaller operating mode - for example 5-bit or 10-bit. A detailed analysis of this cipher can be difficult, my question is rather about some obvious weaknesses. The cipher appears to be unexpectedly good, despite being only a minor modification of the linear congruential generator. So either I don't notice something or it is quite a non-trivial proposition.
Comment 1: let's skip the encryption problems with zero-block - it can be solve easily, for example if we will use xoring before every round.

Is this type of encryption secure?

Nope (even if you make all the $a_i$ values odd, which you need to make it invertible).
It turns out that there are high probability differentials in this structure; in particular, you have a one-round differential with an input xor difference of (01111...11110) (that is, all bits except the first and last are flipped) and the output xor difference of (01111...11110); this differential holds with probability $> 0.5$.  Because the output differential of round $X$ is the input differential of round $X+1$, the entire differential holds through the entire cipher with probability $> 2^{-10}$


SPHINCS and HORST: can we sign the same message twice? I was reading about SPHINCS which uses layers of WOTS+ trees and a bottom layer of HORST trees. HORST is a few time signature scheme, using a selection function you can sign at least twice without compromising security.

I was then reading this blogpost where for the description of SPHINCS says:

  Signing the same message again should use the same HORST, signing two
  different messages should make use of two different HORST with good
  probabilities.

So as I understand, given the fact that the random bit masks are constant after instantiation of the scheme, SPHINCS is a deterministic scheme. Also it is susceptible to replay attacks since signing the same message twice produces the same signature. Am I correct?

So as I understand, given the fact that the random bit masks are constant after instantiation of the scheme, SPHINCS is a deterministic scheme.

Actually, Sphincs as originally proposed is deterministic; however there is nothing preventing a signer from selecting a path randomly (rather than making it a secret function of the message).

But yes, if we assume that a signer doesn't decide to do this, you are correct; signing the same message twice will produce the same signature.

  Also it is susceptible to replay attacks since signing the same message twice produces the same signature. Am I correct?

I'm not sure what a 'replay attack' would mean for a signature algorithm.  For any signature algorithm, the adversary can take a message and valid signature pair, and present it multiple times; the verification algorithm would accept it every time; this is not unique to Sphincs.  Now, there may be other things in the protocol to reject this situation; that's not the job of the signature verification algorithm.

In addition, seeing the same signature multiple times would inform the adversary that the same message was being signed multiple times; on the other hand, we don't assume that signature algorithms provide privacy, and so that is also not considered an issue.

BTW: if you look at Sphincs+, things change; they made the signature algorithm nondeterministic (not because they are afraid of determinism, but instead to try to avoid relying on collision resistance of the hash function; everything else within Sphincs+ relies on preimage or second preimage resistance).


Is AES_CMAC specified to double ciphered zeroes during initialization? Reading the SIV RFC https://tools.ietf.org/html/rfc5297#page-9, I found that the S2V function starts by calculating the MAC of a "zero" block, doubles it and then XORs further data to the result.

Now looking at the BouncyCastle implementation, the exact same thing happens during the initialization of AES-CMAC.

How do I have to understand the S2V specification? Do I have to do all the "zero" stuff and doubling and XORing? Or does this already happen inside the AES-CMAC function? Would that mean, that AES-CMAC(key, plaintext) is equivalent to S2V(key, plaintext)?

Do I have to do all the "zero" stuff and doubling and XORing?

If you are implementing the S2V primitive, using an AES-CMAC function, then yes, you will need to do all that "zero" stuff and doubling and XORing.

Yes, if you peek inside the AES-CMAC function, you will find some logic that looks sort of like this; processing an all zero block, doubling the result, and doing some xor's with it.  However, CMAC is doing something a bit different with it (the result of the processed 0 block goes at the end of the chain, not at the beginning), and in any case, the S2V primitive assumes the CMAC logic as a primitive; what CMAC does internally is actually irrelevant to how to implement S2V.

  Would that mean, that AES-CMAC(key, plaintext) is equivalent to S2V(key, plaintext)?

No, if you look at the RFC, then the S2V of a vector that consists of a single plaintext (remember, S2V takes a vector of plaintexts) would be either:

AES-CMAC( key, plaintext XOR AES( key, 0 )) (for plaintexts >= 128 bits; the xor applies to the end of the plaintext), or
AES-CMAC( key, PAD(plainext) XOR double(AES( key, 0 ))) (for plaintexts < 128 bits).


Matrix Trapdoor AB+BA I believe I'm probably not the first person to think of using this as a trapdoor.

  Let $R$ be a square matrix ring, and $S$ a commutative subgroup of its multiplicative monoid.

  Let $P \in R$ be a publicly-known matrix such that for all $x \in S$, $x$ can be constructed by calculating $x = P \cdot D \cdot P^{-1}$, where $D$ is some diagonal matrix ($D$ isn't necessarily in $S$, and $x$ isn't necessarily a diagonal matrix).

  The trapdoor problem being: given $a \in S$ and $u = a \cdot b + b \cdot a$, find $b \in R$

What I don't know about is:

How difficult is it to find $b$?
What are some of the cases where finding $b$ would be easier than average?

My Guess:

Because it's not possible to retrieve $b$ using ordinary matrix operations, some search is required.
If $u = 0$, then $b = 0$ would be a trivial answer. If $u \in S$, then $b = (u \cdot a^{-1})/2$ would be another.

A bit of explanation on $S$: its elements are guaranteed to be commutative in multiplication because:

1) diagonal matrices are commutative in multiplication,

2) multiplying an element constructed as $a=P \cdot A \cdot P^{-1}$ with $b = P \cdot B \cdot P^{-1}$ where $A$ and $B$ are diagonal matrices yields $a\cdot b = P \cdot A \cdot P^{-1} \cdot P \cdot B \cdot P^{-1} = P \cdot A \cdot B \cdot P^{-1} = P \cdot B \cdot A \cdot P^{-1} = ... = b \cdot a$

How difficult is it to find $b$?

If the matrices within $R$ are of dimension $n \times n$, then we can express the equation $u = a \cdot b + b \cdot a$ as $n^2$ linear equations over the finite field the matrices are over; a simple minded Gaussian Elimination would recover $b$ in $O(n^6)$ steps.

If $u$ is specified explicitly in the public key or the ciphertext or the signature, that'll take $O(n^2)$ space; in other words, to get $n$-bit security, you'll need to take $O(2^{n/3})$ space (field elements).

Currently, the lowest level of security we consider is $n=80$ bit (and that's for constrained devices that really can't do any more); even at that level, you'll end up with using multimegabyte public keys/ciphertext/signatures (at the very least, assuming that there's no better attack).

Now, if your cryptosystem has nice properties, for example, is at least partially homomorphic, it might be of some interest.  However, if it's just a simple public key encryption or signature system, well, something with a relatively low-exponent polytime solution doesn't look at all promising...


Random oracle model proofs and programmability Proving the security of a scheme with the random oracle model (ROM) involves two steps: first you prove that the scheme is secure in an idealized world where a random oracle exists, and then you implement this scheme in the real world by replacing the random oracle with a hash function. Why wouldn't you prove the security of the scheme with the hash function that you end up implementing the world with? Is it because no proof has been found or are there any other reasons? Could you give me some examples?
Could you explain to me the "programmability" feature of the random oracle model? In my book (Katz-Lindell) it says: The reduction may choose values for the output of H as it likes (as long as these values are correctly distributed, i.e. uniformly random).
If I understand correctly, the function $H$ that will act as a random oracle can be fixed beforehand or it can be generated "on the fly", by generating a table of inputs and outputs and when there is a new input the function generates a new output and enters it into the table. What is the theoretical difference between the two?

Your second question was about programmability. This hasn't been directly addressed yet by Thomas' answer or the comments, so I'll focus on that question only. Unfortunately I don't know of a simple primitive that is secure in the random oracle model that requires programmability, but I'll use one that is hopefully clear once I explain the background. It's called the Fiat-Shamir heuristic; it's a nice trick to make non-interactive zero knowledge proofs.
Before getting to Fiat-Shamir, consider how your favorite basic zero-knowledge proof works. Since this is Crypto SE, not CSTheory SE, hopefully you are thinking about proving knowledge of discrete logarithms and quadratic residues, not graph isomorphisms or 3-coloring graphs. ;)
[Aside: technically these are not true zero-knowledge proofs, they are honest-verifier zero-knowledge proofs (sometimes called $\Sigma$-protocols) but we don't care about that distinction here]
Schnorr's proof of knowledge of a discrete logarithm
$P$ (for prover) comes along with two values $g$ and $y$ in some group $\mathbb{G}_q$ where the discrete logarithm is hard. She claims: I know the value $x$ such that $y=g^x$. As $x$ is the discrete logarithm of $y$ base $g$, computing $x$ directly is infeasible so $V$ (verifier) cannot initially be sure if she really knows $x$ or not.
The Schnorr protocol lets $P$ prove knowledge of $x$ to $V$ in a way that does not disclose anything about $x$. It goes as follows:

$P$ generates a random value $a$, computes $b=g^a$, and sends $b$ to $V$
$V$ generates a random value $c$ and sends $c$ back to $P$
$P$ computes $d=a+cx$ and sends $d$ to $V$
$V$ accepts $\langle b,c,d\rangle$ as proof for $\langle g,y \rangle$ iff $g^d=by^c$

Security Analysis
We can ask ourselves, what do you we want in terms of security from such a protocol? $V$ is concerned that sending a bunch of numbers back and forth might not actually constitue a proof that $P$ knows such an $x$. If he can actually conclude that $P$ must know $x$ if $P$ can produce many accepting $\langle b,c,d\rangle$ transcripts, the proof is said to be sound.
$P$ may be concerned that $V$ might learn some information about $x$ from seeing one or more accepting transcripts. This is supposed to be a proof that leaks zero information about $x$ (glossing over the honest verifier technicality). If it leaks zero information, it is said to be zero-knowledge.
Soundness (via Extraction)
To show the Schnorr protocol is sound, we are actually going to do it indirectly. We are first going to show it is something called "extractable" and then show that extractability implies soundness. I'm not going to give actual definitions or proofs, just a sketch of what is going on.
Schnorr protocols have a special soundness property (called, you guessed it, special soundness): if there are two accepting transcripts $t_1=\langle b,c,d \rangle$ and $t_2=\langle b,c',d' \rangle$ where $t_1$ shares the same value of $b$ with $t_2$ but $c$ (and thus $d$) are different, then it is possible to calculate the value of $x$: $x=(d-d')/(c-c')$. If $P$ can reliably generate accepting transcripts, then there is no reason to suppose she couldn't generate $t_1$. Likewise $t_2$. And if she can produce both, then she "knows" $x$ in the sense that the knowledge required to produce $t_1$ and $t_2$ is sufficient to produce $x$ itself.
When we eventually get to Fiat-Shamir, it will be important to have formalized this notion of "extractability" a little bit. Consider the situation where $P$ is a compiled binary program instead of a person. You can run $P$ which will perform the protocol and you can rewind $P$ to a previous internal state, but you can't decompile it or look at the internal state (this is called rewindable blackbox access; why these special powers are allowed in proving extractability is a topic for another time).
We say that a protocol is extractable if you can get $x$ from interacting with such a black box. And we say a protocol is sound if it is extractable in this way (a blackbox that you can rewind). Both of these propositions have proofs in the literature with lots of fine-print I am omitting. Note that you can prove soundness in other ways than extractability or other flavours than blackbox-rewindable extractability (extractability is sufficient but not necessary).
For Schnorr, it should be obvious how, but you do the following:

Let $P$ output $b$
Give $P$ a random $c$ as input
Let $P$ output $d$
Rewind $P$ to after step 1 and before step 2
Give $P$ a different random $c'$ as input
Let $P$ output $d'$
Compute $x$ from $\langle b,c,d \rangle$ and $\langle b,c',d' \rangle$

Zero-knowledge (via Simulation)
Similarly, we can indirectly prove the protocol is zero-knowledge by showing it has a different property: simulatability. In this case, we get a compiled binary of $V$ and have to reliably supply it with acceptable $b$ and $d$ values for the $c$'s it gives us. However the protocol is for knowledge of an $x$ we do not actually know! If we can simulate acceptable protocol runs without knowing $x$, then the values in the protocol must not really be leaking any information about $x$. So if the protocol is simulatable in this regard, then it is zero-knowledge.
I mentioned before that Schnorr is not actually a zero-knowledge protocol. This creates some problems with simulating Schnorr transcripts that will get resolved when we use a random oracle with Fiat-Shamir. To simulate Schnorr protocols, we do the following:

Generate random value $d$
Guess the value of $c$
Supply $b=g^dy^{-c         }$ as input to $V$
Let $V$ output $c'$
If $c'\neq c$ (you guessed wrong), rewind to step 2. Else continue
Supply $d$ to $V$ which will accept

If the values of $c$ are really short (say a bit), then the simulator is efficient. For longer values, you can't prove the zero-knowledgeness of Schnorr with this method. There are a handful of tricks to convert Schnorr into something that is true zero-knowledge.
Fiat-Shamir Heuristic
Reading the above, you might do a double-take: on one hand, you can show that $x$ must be known if transcripts accept and on the other, you can generate transcripts that accept without $x$: what gives? If you look closely, you'll see that the simulated transcripts are generated out of order while the extractable ones are generated in order. In fact, by generating out of order, we cannot produce $\langle b,c,d \rangle$ and $\langle b,c',d'\rangle$ transcripts since the value of $b$ is no longer being chosen: it is determined by $d$ and $c$.
The idea of Fiat-Shamir is to make Schnorr (and related) protocols non-interactive. This means $P$ can produce all three values $\langle b,c,d \rangle$ instead of relying on $V$ to provide $c$. Furthermore, since we know transcripts are simulatable, $P$ can produce a value of $c$ that has to have been generated after the value $b$ thus ruling out any simulation. How? It is really easy actually: set $c=\mathcal{H}(b)$. The verifier additionally checks that $c=\mathcal{H}(b)$. [Aside: there is actually a neat optimization here where you don't have to send the value $b$ at all but leave that aside].
Finally we can introduce random oracles. It turns out that if you use regular hash functions, you can't wrestle extractability or simulation out of the protocol. We'll try but ultimately we will require a random oracle that can be programmed.
Extraction with Fiat-Shamir heuristic
Recall that extraction relies on pairs of transcripts like $\langle b,c,d \rangle$ and $\langle b,c',d' \rangle$. With Fiat-Shamir, $c=\mathcal{H}(b)$ so if the values of $b$ between two transcripts are identical, then $c$ and thus $d$ will be as well. Therefore, we cannot get two such transcripts with a regular deterministic hash function. But if $\mathcal{H}$ is a programmable random oracle, we can get it to produce different values for the same input. Once again, we play the game of having rewindable blackbox access to $P$ but this time we also get the random oracle:

Let $P$ generate $b$
See $P$ query $O$ with $b$ for $\mathcal{H}(b)$
Generate random $c$ and program $c=\mathcal{H}(b)$ in $O$
Let $O$ answer query
Let $P$ compute $d$
Let $P$ output $\langle b,c,d \rangle$
Rewind to end of step 2
Generate random $c'$ and program $c'=\mathcal{H}(b)$ in $O$
Proceed as before and eventually let $P$ output $\langle b,c',d' \rangle$

A few notes: (1) because this is non-interactive, $P$ does not output $b$ after step 1, so we rely on the ability to see queries to the random oracle; (2) if the oracle generates answers "on the fly" (instead of entering the protocol with a codebook of all queries/responses), we don't actually have to program it with different values of $c$. We just rewind to before the point it is about to generate a response and let it generate a random value (which will overwhelmingly be different than in the first execution). This sheds some light on the original poster's third question.
Simulation with Fiat-Shamir
Similarly to extraction, the use of a random oracle makes simulation a breeze. Assuming you've read this far, you can probably see how so I will just say it in a sentence: Set a random value for $c$, compute $\langle b,c,d \rangle$ by choosing $d$ first, and when the verifier checks with the oracle that $c=\mathcal{H}(b)$, program $c$ as the response.


How to apply lagrange interpolation on bilinear pairings? I have seen in some places applications of Shamir secret sharing and lagrange interpolation mixed with bilinear pairings, however I fail to understand how this works. For instance, here I find the statements:

$pk_{common} = \sum_{i=1}^{t+1} l_{i}*pk_{i}$
$e(h, pk_{common})$

If $pk_{common}$ is a point in some $\mathbb{G}$, how can a lagrange interpolation result (the polynomial or an evaluation for $x=0$) transform into a suitable point that can be used in the pairing function?

Are you asking how we come up with the $l_i$ values?" Most probably yes

How we find these values is pretty much standard Shamir Secret Sharing, and has nothing directly to do with the pairing we'll do later.

To do a quick review, in Shamir Secret Sharing, we pick a finite field, and a $t$ degree polynomial $P$ (whose constant term is the secret we'll share, and the rest of the terms are random [1].  We generate shares by assigning each share a nonzero index $i_j$ (which can be public), and the value $y_j = P( i_j)$, that is, the polynomial evaluated at the index.

Now, if we know $t+1$ shares, we know enough to reconstruct the polynomial (and thus the constant term, which is the secret); the standard way to do this is to not bother computing the entire polynomial, but instead just compute the values:

$$l_j = \frac{\prod_{k=1,...,t+1, k \ne i}-i_k}{\prod_{k=1,...,t+1, k \ne i}i_j-i_k}$$

And, this we can reconstruct the secret as:

$$s = \sum_{i=1}^{t+1} l_j y_j $$

If you go through the math, you'll find that this value $s$ is precisely the constant term of the polynomial $P$.

The $l_j$ values are precisely what you are asking about.

Now, the standard Shamir method has the secret (and the coefficients of the polynomial) being elements of the finite field; what this paper does is tweak things a bit by making the secret, the rest of the coefficients and the secret $y_j$ values being elliptic curve points (one way of thinking of it is that, instead of having the secret being a value $s$, it is actually the point $sG$).  They then have the finite field that the $i_j$ values work in being $GF(q)$, where $q$ is the prime order of the curve.  Because the above algorithm never needs to multiply two different $y_j$ values, this all works out.

[1]: Note: we allow the high order term of the polynomial to be 0.  Standard terminology would state this would be a $t-1$ or lower degree polynomial; however, we need to allow this case to provide for the informational security that Shamir provides.


Choice of finite fields for use in elliptic curves this is maybe a basic question but I'm trying to better understand elliptic curve cryptography at a fundamental level.

I understand that a finite field is required in order to define a boundary for an elliptic curve.

Then, x,y values that satisfy the curve over this field represent the ec group of the curve.

My question is simple, how are the finite fields defined? They seem so arbitrary...

Example,

The finite fields for secp256k1 and curve25519 are

2^256 - 2^32 - 977

and

2^255 - 19 respectively...

My naive question is, how are these fields defined? The seem to be arbitrary bounds on the size of the ec group for the curves defined inside them.

I'm not asking why they are prime, but more why these numbers are chosen, and how the right size group is selected?

I did consider it was something to do with all of the elements satisfying some criteria, but really the values seem too large and arbitrary for that.

First, the size: the best attacks for breaking elliptic curve cryptography are algorithms that break the discrete log (given a point $P = kG$, find the integer $k$; which in ECC translates to: given the public key, find the private key).
These attacks have complexity of $O(2^{n/2})$, where $n$ is the size of the field. So, in a 256-bit field (i.e. with a 256-bit $p$), the best attacks can break the algorithm with $2^{128}$ steps, which is similar to what is needed to break a single instance of a 128-bit key symmetric algorithm by brute force. This is usually called "128-bit level of security". In short: the field size must be the double of the desired security level. (I've omitted some details about cofactors, but they don't change the picture that much for commonly used curves)

Now, the particular primes chosen: the computationally expensive part of ECC is field multiplication, which is composed of integer multiplication followed by reduction modulo $p$. Depending on the structure of $p$ this reduction can be computed faster. One example are primes having the form $2^k-c$ for small $c$ (Crandall primes), which is the case of secp256k1 and curve25519. The best case is a Mersenne prime, $2^k-1$, which is used by the NIST curve P-521 ($2^{521}-1$). Other common case is when the prime is composed of powers of multiples of a word size, such as P-256 ($2^{256}-2^{224}+2^{192}+2^{96}-1$), which are all multiple of 32. The reason why these lead to a faster implementation would probably required another question on the site, though; but for example, when $p = 2^k-1$, then $2^k \equiv 1 \pmod p$. If you write the result of the integer multiplication as $H + 2^kL$, then the reduction modulo $p$ will be simply $H + L \bmod p$.


Attacking any one in many public keys The problem of finding private key from public key is typically studied in the one-key setup: what's the expected cost of breaking one key (e.g. by factoring a public modulus, or solving a discrete logarithm in some group).

There is much less work on simultaneously attacking $k>1$ keys. One notable exception is Daniel J. Bernstein and Tanja Lange's Batch NFS, in proceedings of SAC 2014. They conclude that increasing $k$ allows asymptotic savings on the expected cost per factorization.

A different problem is attacking any one in $k>1$ keys. It seems understudied too, although it is of practical concern, especially in setups where there can't be a revocation list. For example, there are deployed systems such that an attacker could gather many thousands public keys of devices that can write in Smart Cards after authentication, and does not care which one is broken: whatever one allows falsifying records made in the Smart Cards. Also, from a public relations perspective, it's hard to convey that indeed, a hacker demonstrated breaking one key in your system, but it is still safe enough since there's no positive evidence that the adversary could attack a particular key.

We can trivially state that the expected difficulty of attacking any one in $k$ public keys is at most that of attacking one key. I conjecture that it is at least $1/k$ that, at least in the case of factorization.

Can we be more precise, in general, or in the special cases of factorization (RSA…), discrete logarithm in $\Bbb Z_p^*$ (DSA…) or elliptic curve group groups (ECDSA, EdDSA…)?

Update: Poncho quickly pointed that the problem is settled for the discrete logarithm with shared parameters like public prime modulus or curve, which is customary. The question remains in general, for factorization, and DL with per-key parameters.

Actually, a well known result is that, for any cryptosystem that relies on the hardness of the DLog problem (including ECDlog), there is no such reduction in strength if you have $k$ keys.  That is, the problem of "here are $k$ keys, break any one" is essentially as hard as the problem "here is one key, break it".
The proof is straight-forward; first off, we assume that the cryptosystem is based on Dlog, hence breaking the system is equivalent to solving some DLog problem.  Further suppose we did have a method of, given $k$ values $a_1G, a_2G, …, a_kG$, of finding $a_i$ for some $i$, and this takes effort $M$ [1].
Then, given $bG$, we can attempt to recover $b$ by selecting $k$ random values $r_1, r_2, …, r_k$; and compute $r_1(bG), r_2(bG), …, r_k(bG)$.  We then hand this off to our oracle, which gives us the value $c$ s.t. $cG = r_i(bG)$ for some $i$; we then compute $b = cr_i^{-1}$, and thus recovering $b$, at the cost of $M$ plus the time to do $k$ point multiplications (which is quite feasible assuming $k$ isn't ridiculously large).
Similar proofs would apply to DH-based cryptosystems as well.

[1]: I'm using additive notation, mostly because I find it easier to read...


Need to generate same ciphertext everytime I am developing in android and working with numeric ids. Say for e.g., 5001.

I upload videos with this id prefixed in in the uploaded video's name.

For e.g. 5001_profile_video.mp4 is a filename. Then if 5001 gets encrypted to xx841jf==, the file name would be xx841jf==_profile_video.mp4.

I need this to be same every time. Say I uploaded video for profile id 5001, the and the file name was xx841jf==_profile_video.mp4. Then, next time I retrieve video for id 5001 I should be able to form part of  the file name as xx841jf== for retrieving video from server.

I need to encrypt 5001 but I need it to be same every time I call the encrypt method. I am currently using Cipher class in java but the results are different every time.

What should I do? Is encryption what I should be looking for OR should I look for something else?

If you use a small value such as xx841jf== to retrieve a video then a hacker can simply brute force the URL by iterating over all the values. Similarly, if you use a hash over the number (5001) then the attacker can simply go over all numbers, perform the hash and perform the same attack.

There are a few good options for doing this:

Use a block cipher to encrypt the number value. In that case you need to pad the encoded number to a full block (using bit padding or PKCS#7 padding, for instance) and then the full result. This can be reversed to the number by the server.
Similarly you can use a hash over the number and a secret value (a pepper) to calculate a unique number, and then take the leftmost bits in case you want to shorten the URL (you'd still want at least 64 bits otherwise you may mistakenly reuse hash output values).
Often unique, large, random ID (a UID) is used to link to the number.

Notes:

For the first option you could use a 64 bit block cipher (e.g. Blowfish) or a 128 bit cipher such as AES. AES is more secure, but the URL will be much larger.
If direct encryption with the block cipher is not available then you could choose AES in ECB mode using PKCS#7 padding which is commonly available.
Of course you'd need to keep a table for the last two options, otherwise you cannot reverse the URL to the number and thus filename.
Instead of using standard base 64 encoding you could have a look at base-64-url encoding, which is URL-safe and thus doesn't require URL escaping.


Pseudorandom function of different keys Could someone explain to me how they formulated the equation and how it equals to $0^{n}$ (like what F(x, x) equals to or how they cancel each other out?) on the first box and if its related to the second. I know that PRF output plus itself would make all the bits 0, so $F_K(x) + F_K(x) = 0^{n}$

As kodlu previously said, this text is confusing because it uses the name $F$ for two different things.
For clarity, I'll use

$P$ (rather than $F$) for a function that we already know (or assume) is an n-bit pseudorandom function. Typically a pseudorandom function "encrypts" a n-bit plaintext block to a n-bit ciphertext block using a k-bit key.
$M$ (rather than $F$) for any function that we are trying to prove either definitely is or definitely is not a pseudorandom function. As the attacker, you win if you can find any way to distinguish $M$ from a random oracle -- in other words, you win if you can show that candidate $M$ definitely is not a pseudorandom function.
$D$ is a "function of a function" that can be applied to any keyed function $M$. The text leaves unstated a few details that it expects you to fill in, but to be explicit (where + represents xor):
$$D(M, K, K', x, y) = \begin{cases} 1, & \mbox{if } M_{K, K'}(x,x) + M_{K, K'}(x,y) + M_{K, K'}(y,x) + M_{K, K'}(y,y) = 0^n \\ 0, & \mbox{otherwise} \end{cases}$$

We separately apply $D$ to two different things: first we set $M$ to a true random oracle $R$ (or a pseudorandom function $P$, which should give the same results) and calculate D, and then we set $M$ to the function $G$ given in the problem and calculate D.
(When D calls the random oracle with the two keys of length k and the two inputs of length n, we concatenate the keys and we concatenate the inputs to call a random oracle with one key of length 2k and one input of length 2n and we only use the first n bits of the output of the oracle).

  what happens if the key is the same as message such as $F_x(x)$.

In this particular problem and solution, we set the message independently of the key, so they are almost certainly not the same.
Even if they were the same, nothing special happens.
A few (old and deprecated) password hash functions set the key the same as the message: "HMACs that have the same key and message" , "HMAC SHA1 using the same value for key and message", etc.


Why is $H(k\mathbin\Vert x)$ not a secure MAC construction? If $H(m)$ is a secure hash function, can't we implement a MAC using $H(k\mathbin\Vert m)$?

However, it seems the more widely used MACs, such as NMAC and HMAC (both originally defined in Keying hash functions for message authentication) use a much more complicated scheme. Why is this concatenation scheme insecure?

The word "secure hash function" usually means (for a function $H$)

Preimage resistance: Given a value $h$, it is hard to find a message $x$ so that $h = H(x)$.
Second preimage resistance: Given a message $x$, it is hard to find a message $x' \neq x$ such that $H(x) = H(x')$.
Collision resistance: It is hard to find two messages $x$, $x'$ such that $H(x) = H(x')$.

For a secure MAC function $M$, we want:

Unforgability: Without knowing the key $k$, it is hard to find a message $x$ and authentication tag $m$ such that $m = M(k, x)$, even if given some other such valid message-tag pairs (which are not allowed as answers).

Unfortunately, defining $M(k,x) = H(k \mathbin\Vert x)$ for a secure hash function does not guarantee that the MAC function is unforgeable.

In fact, with the hash constructions used in practice (i.e. the Merkle-Damgård construction without a finalizing round, used in MD5, SHA-1 and the SHA-2 family), it is quite easy, given a valid pair $(x,m)$, to create an $(x', m')$ which is still valid:

To create a hash with Merkle-Damgård, the message is padded to some block size, and then each block in sequence is feeded to a compression function, which updates an internal state. The final state is then output as the hash.

So, $H(k\mathbin\Vert x)$ is the state of the hash machine after inputting $k\mathbin\Vert x\mathbin\Vert\mathit{pad}_x$. If we set our hash machine to this state, and then input arbitrary other data $y$, followed by another pad $\mathit{pad}_y$, we reach the state $m' = H(k\mathbin\Vert x\mathbin\Vert\mathit{pad}_x\mathbin\Vert y) = M(k, x\mathbin\Vert\mathit{pad}_x\mathbin\Vert y)$.
Forgery is done, with $x' = x \mathbin\Vert \mathit{pad}_x \mathbin\Vert y$.

This also works with the full-width variants of SHA-2, i.e. SHA-256 and SHA-512. For the truncated variants of SHA-2 (SHA-384, SHA-224, SHA-512/224 and SHA-512/256) this attack doesn't work, as the output is not the full hash state. (Though for a length extension attack only the truncated bits would have to be guessed, so the security is a bit less than expected from the output size.)

The HMAC construction is not suspectible to this attack, as the secret key $k$ is applied both before and after the main message, which makes the internal state non-reconstructible.

HMAC does not guarantee unforgability for general secure hash functions, either, but it has a security proof for the Merkle-Damgård construction, if the internal compression function is collision-resistant.

SHA-3 (Keccak) is based on a different model: we have a quite big state into which both key and message are mixed, and which is then further mixed to output the hash. The state itself is never output fully. Because of this, length extension needs state recovery, and the capacity (the hidden part of the state) should be big enough that this is not feasible (as well as guessing the key).

The paper On the security of the keyed sponge construction by the Keccak team analyzes the security of this construction.


Does RSA have two trapdoors? I watched some videos from Khan Academy explaining the algorithm for RSA encryption/decryption. They explained that there are two trapdoors, modular exponentiation being one and prime factorization being the other. Is this true though? As the videos went on it made it seem like prime factorization was what made the inverse of modular exponentiation difficult to solve. Did I misunderstand something, or is modular exponentiation just a naturally difficult problem to compute?

Defining RSA Problem as finding $m$, having $N,e,c$ where $c=m^e \mod N$ and $N=pq$, two unknown same-size prime numbers.

So far the best generic method we know to solve this is to factor $N$.

But there might be other methods, so far unknown, to compute the $e$-th root of $c$ and recovering $m$.

This is different from the discrete logarithm problem, where the exponent is secret. This is just computing an $e$-th root. We know how to compute roots modulo a prime, we don't know how to compute roots modulo a composite number of unknown factorization.

Note: for bad choices of m (i.e. without the use of padding) or $e$ or $d$ (the private exponent) there are practical attacks that recovers $m$ without factoring. For example the Weiner's or Coppersmith's attack. In particular the method of Coppersmith does compute $e$-th roots if $e$ and $m$ are small enough therefore it is not a generic method.

The RSA Problem is at least as easy as factoring. But there might be other, so far unknown, easier way to compute $e$-th roots without factoring.


Service to expose all encrypted messages its users sent. How protected would this data be? I have recently started a new side project for an open-source messaging system with end-to-end encryption.

My key idea with this project is that everything should be as transparent as possible, with the server only being an intermediary - a repository for encrypted messages that can be accessed by anyone but can only be decrypted by their intended recipients, who will keep their private keys safe locally.

My choice for encryption is PGP as my knowledge is that there are no known attacks that can crack it; that it is protected against attacks where both the plaintext and its encrypted version are known and that using initialization vectors you can make sure two instances of the same content don't produce the same encrypted output.

However, allowing everyone to access all encrypted messages seems risky because:

There are no known attacks for the time being but that can change in the future
Brute-forcing would take ages with current hardware but hardware is only going to improve
Quantum computers will probably become a thing in the future

I really don't want the server to handle authentication and sessions as I want to treat it as something the user can't really trust (with recent history showing it's often just a matter of time and interest whether a server will get compromised). I also want to provide users with more anonymity and privacy - if the server can't know who a user really is (because it won't know if they could decrypt the messages they accessed), an attacker who has gained control over it and is monitoring its connections can't either, at least not for sure.

My question is, is it reasonable to allow everyone to access all messages? Are the points I mentioned about possible attacks in time reasonable? Is this improved "privacy and anonymity" really not a good trade-off for the possibility messages would eventually be cracked?

To answer your primary question: Making encrypted messages accessible to everyone can be a security risk. A messaging system is typically asynchronous (meaning that you can send a message to someone that is currently offline), which makes it very difficult to provide perfect forward secrecy (great article how TextSecure solves this issue here). So an attacker with great storage capabilities (for example with a huge datacenter in Utah) could simply collect all messages that flow through your server and store them. Whenever the PGP private key of a user gets compromised, the attacker can simply go back to the recorded messages and decrypt all the messages that user received.
However, you also mention that you are assuming an adversary that can compromise the server itself. In that scenario, it doesn't matter whether or not every user can access all messages. I think it is important to first understand the goals of your messaging system as well as the different security building blocks you want to use.
Security Goals

Receiver Anonymity: By making the server a public repository for encrypted messages, you are basically creating a broadcast channel where everyone can potentially receive the message but only the intended receiver(s) can decrypt it. There exists a great body of research around receiver anonymity (e.g., this), but I am not sure whether this is actually the right approach to building your system. The problem that any kind of broadcast channel solution has is that each party has to attempt the decryption of each message, which does not scale very well (ironically, the receiver anonymity  increases with the amount of participants in the system). So regardless of whether or not the exposure of the encrypted messages to all participants poses a security risk from a cryptographic standpoint, I would not recommend this approach for a messaging system due to performance reasons.

Privacy: Using PGP will indeed provide confidentiality for your messages. However, it also requires the participants of your messaging system to have an authentic channel to retrieve each other's public keys. This cannot be the server itself, since you are assuming a potentially malicious/ compromised server setting. Threema thought of a good workaround for this problem where the server distributes the public keys but the user can verify the key's fingerprint via an out-of-band method (phone call, scanning the QR code, ...). Even if a malicious server would replace the public key of the receiver with its own, the sender could spot this by verifying the fingerprint.

Existing Building Blocks

Mixes: You can read about mix networks here. You basically achieve that a passive attacker can learn the identity of all sender and receiver but cannot link them together. This is the same level of anonymity as in your setting, as the malicious server knows who is connecting but does not learn which messages can be read by whom.

Implementation Recommendations
Have a look at XMPP/ Jabber. There exist great extensions for the protocol to offer end-to-end encryption and even OTR messaging.


Strength of RSA with OAEP In our current system we use an encryption solution based on RSA with OAEP padding. Key size is optional but default 2048. What is the general strength of RSA with OAEP? Are there know attacks that can break it, their complexity? Are people using it and relying on it as secure enough?

Thanks

OAEP is likely to be secure as long as the underlying primitives - RSA using modular exponentiation and the hash function to generate the padding - are considered secure. So the OAEP padding in itself should not pose any problems.

That said, we don't know if your protocol is secure, nor if the RSA / OAEP implementation is secure. It could for instance be vulnerable to timing or other side channel attacks.

Currently it seems that OAEP is your best bet for performing RSA encryption. Yes, OAEP is standardized and well used. RSA encryption with PKCS#1 v1.5 padding is still used, arguably too much.

As the RFC encapsulating the PKCS#1 standard specifies:

  In addition, the running time for Inv is approximately t^2, where t
     is the running time of the adversary.  The consequence is that we
     cannot exclude the possibility that attacking RSAES-OAEP is
     considerably easier than inverting RSA for concrete parameters.
     Still, the existence of a security proof provides some assurance that
     the RSAES-OAEP construction is sounder than ad hoc constructions such
     as RSAES-PKCS1-v1_5.

  Hybrid encryption schemes based on the RSA-KEM key encapsulation
     paradigm offer tight proofs of security directly applicable to
     concrete parameters; see [30] for discussion.  Future versions of
     PKCS #1 may specify schemes based on this paradigm.

This was based on the following:

  E. Fujisaki, T. Okamoto, D. Pointcheval and J. Stern.  RSA-OAEP
           is Secure under the RSA Assumption.  In J. Kilian, editor,
           Advances in Cryptology - Crypto 2001, volume 2139 of Lecture
           Notes in Computer Science, pp. 260 - 274.  Springer Verlag,
           2001.

As specified in the RFC, RSA-KEM could also be an option. RSA-KEM couples RSA encryption with a (Key Based) Key Derivation Function and symmetric encryption. RSA-KEM may be easier to implement securely. Not many libraries offer direct support for RSA-KEM though (or KDF's for that matter) and it will require some overhead.


Statistical tests for pseudorandom permutations I'm implementing a format-preserving encryption scheme similar to those described in the literature. I want to sanity test my PRP using some statistical tests like TestU01. However, I'm not sure how applicable these kinds of tests are to PRPs since they are designed to test PRNGs. Are there statistical tests that are PRP-specific? If not, would the results of a PRNG test against a collection of PRP ciphertexts be a meaningful test of its statistical pseudorandomness?

Typically, the output of format-preserving encryption is easily distinguishable from a random bitstream, precisely because the ciphertexts conform to some non-random format.  Thus, you cannot use standard statistical tests on them, at least not directly.

If the format of your FPE scheme is flexible enough, you may be able to test some aspects of it by configuring your scheme to use, say, "a block of $n$ bits" as the format.  More generally, any format that has exactly $2^n$ possible ciphertexts can be bijectively mapped to $n$-bit blocks and tested that way.  However, this will not let you test how your PRP behaves on domains whose size is not a power of two, which is probably what you're most interested in.

(Generally, statistical tests intended for random bitstreams can also be applied to the output of $n$-bit PRPs, e.g. with a simple counter as the input, provided that the number of $n$-bit blocks in the output to be tested is significantly below $2^{n/2}$.  Above that "birthday limit", the probability of observing a repeated $n$-bit block in a truly random bitstream becomes significant, allowing a PRP to be distinguished from a random bitstream.)

In principle, you could also write your own statistical tests that can handle arbitrary ciphertext formats, e.g. by looking at existing test suites and adapting them.  (Alas, while the math is not necessarily all that difficult, many standard test suites tend to be written and documented in a rather abstruse style.)

However, neither of these approaches solves that fundamental issue that, in general, statistical testing is a very poor way to test the security of a cryptographic primitive.  Sure, if your "PRP" output fails a statistical test (for some reason other than its format or the birthday bound), it's a clear sign that it's not secure, but alas, the converse does not hold — it is quite possible for a totally insecure primitive to pass all standard statistical tests not specifically designed to detect the hidden weakness in that particular primitive.

Thus, to convincingly demonstrate the security of your PRP, you need to either:

construct it so that its security can be provably reduced to that of some other cryptographic construction which is already widely believed to be secure, or
publish it and invite other cryptographers to try to break it.

The difficult part with the second option is getting enough attention — good cryptanalysts are few and far between, and often busy, whereas new ciphers are dime a dozen.  Thus, unless you're already a big name in the field, it can be difficult to get anyone to even look at your system.  There are various ways to try to get around that, such as getting someone already well known in the field to publish an analysis of your scheme, submitting it to an international crypto standards competition, or offering a large cash prize for breaking it, but none of them are easy.  Thus, where possible, a provable reduction to an existing scheme is generally preferred.


Do I need two keys for AES CBC and HMAC or can I use the same key for both operations? I am setting up a Python program to encipher messages on the following basis:

-from my password, generate 32-byte key from SHA256(password)

-generate a 16-byte IV from a PRNG

-measure the length of the plaintext and express as 2 bytes (my plaintext will be shorter than 2^16 characters)

-pad the plaintext to be a multiple of 16 bytes

-make an instance of the encryptor = AES.new(key, CBC, IV)

-generate ciphertext = encryptor.encrypt(plaintext)

-make string of concatenated  length pt before padding||IV||ciphertext and send to recipient

-also send to recipient the tag from    HMAC(key,concatenated string)

My question is whether for security I should use a different key for the AES encryption and for the HMAC tagging?

This seems to me unnecessary, in the sense that with a strong password the chance of finding the key by reverse engineering either the ciphertext or the tag is negligible. Or is it?

I'd advise you to use a library with a higher level API, such as Keyczar.

That being said:

Don't generate the key using SHA-256. Use a password hash function such as bcrypt or scrypt.
Yes, you must use different keys. For example, you can use the password hash function to generate 64 bytes of key material, and use the first 32-byte half for encryption and the second half for authentication.
Make sure the IV comes from a good randomness source (e.g. /dev/urandom)
Make sure your padding is correct. Or simply use CTR which does not require padding.


Is there any good reason to chain HMACs in this manner? I am looking at some decompiled Java code from an Android app. As a security measure, a signature is passed as a parameter to a number of JSON requests.

The method that generates the signature is as so:

private String getSignature(String s, String s1)
{
    try
    {
        Charset charset = Charset.forName("US-ASCII");
        Mac mac = Mac.getInstance("HmacSHA256");
        mac.init(new SecretKeySpec(master_key, "HmacSHA256"));
        mac.init(new SecretKeySpec(mac.doFinal(charset.encode(s).array()), "HmacSHA256"));
        mac.init(new SecretKeySpec(mac.doFinal(charset.encode(s1).array()), "HmacSHA256"));
        s = Hex.toHexString(mac.doFinal(charset.encode(serialNumber).array()));
    }
    // Misplaced declaration of an exception variable
    catch (String s)
    {
        s.printStackTrace();
        return null;
    }
    return s;
}

As you can see, the key of the HMAC is set to the master_key (a preset byte array). A piece of data is then passed through the hash and used as the key for the HMAC on the next step.

The function is called like so:

s2 = getDateString();
s3 = getSignature(s2, "/xquery/1.0/relay.json");

Is there any reason to chain together the HMAC like this? Is it anymore secure than simply performing HMAC(master_key,s|s1|serialNumber)?

If you are asking if $M(M(M(k, C_1) C_2), s)$ has the same or better security as $M(k, C_1 | C_2 | s)$ then the answer is yes. You can see this as a double key derivation to calculate a new key from $k$ using the constants $C_1$ and $C_2$ as derivation data. Then the resulting key is used to MAC the final serialNumber. $M$ is of course HMAC, $C_1$ and $C_2$ are s and s1 and $s$ represents the serialNumber.

If you look at the HMAC construction you will see that the key elements are repeated in the hashing and there are multiple passes of the underlying hash, but the elements remain the same. If you only perform concatenation then you must make sure that there are no collisions for the concatenated elements (xy|z would be identical to x|yz).

Note that the code uses lossy character encoding (ASCII only represents a small part of the Unicode code set). It should be replaced with UTF-8. Currently the input must be validated beforehand to only contain ASCII, but using UTF-8 in the code would add a layer of defense.

So in the end the protocol is fine. It should however be clearly documented.


ECDH and ECDSA in PGP with known public key How are used ECDH and ECDSA in combination with public key ? Usually these methods are used for establish a secret themselves, so why (and how) are used combined with public and private key couple in OpenPGP?

The proposed internet standard RFC-6637: Elliptic Curve Cryptography (ECC) in OpenPGP says in section 8:

  The method is a combination of an ECC Diffie-Hellman method to establish a shared secret, a key derivation method to process the shared secret into a derived key, and a key wrapping method that uses the derived key to protect a session key used to encrypt a message.   The One-Pass Diffie-Hellman method C(1, 1, ECC CDH) [NIST-SP800-56A] MUST be implemented with the following restrictions: the ECC CDH primitive employed by this method is modified to always assume the cofactor as 1, the KDF specified in Section 7 is used, and the KDF parameters specified below are used.

…but there is no word about public key receiver's use, it might be used to protect confidentiality.

Sounds like a description of ECIES to me. ECIES is a hybrid cryptosystem that builds upon ECDH.

Basically: the static public key of the receiver is used together with an ephemeral key pair generated at the sender. The public key of the receiver and ephemeral private key of the sender are used to generate a "shared secret" using ECDH. This shared secret is used with a KDF to generate a session key. This session key is used to encrypt the message. Then the ephemeral public key is attached to the ciphertext. The private key can be safely destroyed.

To decrypt the same secret is calculated at the receiver using the static private key and the public key attached to the ciphertext. The KDF is applied again to generate the session key. Then the resulting key is used to decrypt the ciphertext.

As you can see, after encryption the sender isn't needed anymore. So this scheme can be used to encrypt static data such as files. The only thing the sender needs is a trusted public key to the receiver. This public key is for instance embedded in the PGP certificate of the receiver.


Are "non-mathematical" encryption algorithms comparably secure against brute force key recovery? I recently learned about a desktop encryption application called ALKEMI, which does not use mathematical encryption according to the website, which I understand to be a misnomer, at best:

The encryption Alkemi uses was written by me starting in 2005. It is
NOT MATHEMATICAL in nature.

From what I found, it appears to be similar to, related to, or directly using libraries from Yull Encryption. The algorithm is described as using combinations of different routines:

The data submitted to the encryption class goes through a series of
routines. There are 64 unique routines (procedures). The order of the
routines is determined by a hash of the key. Furthermore, often
certain subsets of the data is run through the routines. Routines
(procedures) can and of course are reused. Typically, routines are
invoked several hundred thousand to millions of times. And some
routines call others which call others. The number of combinations is
meaninglessly huge.

The author goes on to address how difficult it would be to recover the plaintext without knowing the key:

In order to force decrypt Alkemized data, you would have to try all the decryption routines (64 of them), in the precise reverse order.
But as you can see, the amount of routine combinations is gigantic.
There isn't enough time left in Earth's existence to try them all.
..., if you have the encrypted text and the program or even the source
code but not the key, your choices are pretty limited, in my view. You
have two choices: Try all the key combinations. There are a range of
217 letters and symbols, including foreign languages, and a possible
32765 of them in various combinations.

The screenshot of Wolfram Alpha shows this totalling ~10^76554.
First off, these projects raise red flags in my head for any serious use, as I fully believe in the mantra of "don't roll your own crypto". The author admits that it is a home grown algorithm, but still puts it out there recommend for public use.
More importantly to the question, I am struggling to wrap my head around how "safety in numbers" is really sufficient against a brute force key attack. My understanding is that part of the reason it is  difficult to brute force a conventional symmetric encryption key (e.g. for AES) from ciphertext is that the encryption algorithm is computationally expensive, making it difficult to feasibly brute force a reasonably strong key. I didn't find a description of the 64 functions that ALKEMI/Yule uses, so I do not know how they compare in terms of compute cost, although the author says it took 27 seconds to encrypt 12000 characters.
I believe the author also claims it is secure because you can create very long keys in any charset, but regardless it is ultimately limited to the 64 bytes it is hashed to with SHA512, which I guess I can't complain too much about. But I believe this means the key space should be 2^64 rather than 10^76554.
My question is, do these (and any other?) "non-mathematical" [sic] encryption algorithms have theoretical or actual resilience to brute force of the key comparable to a modern standard like AES?

The premise of this question is flawed: There is no such thing as a "non-mathematical" cipher.
Every algorithmic procedure admits a mathematical description, hence is inherently mathematical in nature.

Besides that:

It is not hard to make primitives with massive key spaces, but that doesn't really achieve anything.
One can easily construct ciphers with $2^\text{gazillion}$ keys that are totally insecure.
This fallacy feels like a "freshman's converse" to Shannon's theorem: Perfect secrecy does imply big keys, but not the other way round!

The hard part of designing a good cipher is to make it small and fast while still achieving the desired security level.
The performance figures from the linked website are ridiculously slow according to modern standards.
Thus, even if that cipher is not broken — which I strongly doubt anyone has seriously studied — there is absolutely no reason to to prefer it over AES‑256.


Is it possible to prove the age of a document? Suppose that I have a document and I want to build a proof, for the year of 2020, that this document existed in 2017. I could, for one, use a public blockchain - that is the only method I know for accomplishing this. Is there, though, a more compact and self contained method to achieve the same?

Solution sketch

I pick an inherently sequential hashing algorithm and build an ASIC for it that operates at provably near the thermodynamics limits. I keep "hashing" that document continuously, non-stop, until 2020. Then, at 2020, I publish the resulting HASH^N(document) value. Someone with an equally powerful ASIC will be able to verify my document indeed existed in 2017. The only issue is that it will take him another 3 years to do so. Moreover, if I want to prove that in 2030, a verifier would need 13 years and so on.

This exact issue was handled in great details in this article that you might want to check. In particular, this article explains in detail how their construction can be applied to timestamp documents. Basically, it shows how the methodology you describe can be made efficient for the verifier. The intuition is that rather to hash a chain, the prover will hash the nodes of a graph with some particular structure (a depth-robust graph, to name it). Because of this structure, the following efficient verification procedure can be used:

The prover hashes the entire graph
The prover computes and sends a Merkle commitment of the entire hash graph (this allows to commit to an arbitrary bit string and open the bits at a given position succinctly, i.e. in time logarithmic in the size of the string)
The verifier queries random nodes of the graph; the prover open these nodes and their parents
The verifier checks that the openings are correct and that each opened node was correctly hashed from its parents.

Because of the structure of the graph, repeating the last two steps a polylogarithmic number of times is sufficient to ensure that the prover correctly hashed a long chain in the graph; if the hash function is inherently sequential, this proves that he invested some long computation time.

Several alternatives to the above method are possible. To list a few:

Proceed exactly as you explained, and add a succinct zero knowledge argument that proves that you did the correct computations. Such a succinct argument can be constructed e.g. using probabilistically checkable proofs in the random oracle model, or from various kinds of knowledge-of-xponent assumption.
Use the following nice idea from this article: some designated verifier generates the secret key for an RSA scheme, and sends the public modulus $n$. "Hashing" is simply done by squaring mod $n$ - i.e., the $t$-time function is $f:x \mapsto x^{2^t} \bmod n$. This is expected to be impossible to speed up without the secret key. However, with the secret key, verification is very fast: the verifier simply computes $t' = 2^t \bmod \phi(n)$ and then $x^{t'} \bmod n$, in total time logarithmic in $n$, and checks that he got the same result.


Hash function in PBKDF2 From this excellent answer I learned (correct me if I am wrong) that when writing a block cipher with say key size 128 bit, one has to pad the password given (variable size) so that it becomes exactly the 128 bit that is needed. I had thought that one would just add zeros or repeat the password until the length becomes 128 bit. However, after implementing these options, I can see that the key doesn't look quite random.

I understand that one might use PBKDF2. From what I understand, one has to choose a hash function and that the SHA might be a good choice.

I would like to write my own block cipher from scratch, and having to write all the code for SHA seems a bit much for me right now.

(1) Is there a nicer simpler hash function that could semi-securely be used in PBKDF2? Or alternatively a simpler, but still nice way of padding a password that would be "easy" to do "by hand"? At least, I would like something simple so that I can finish an implementation of TEA.

[(2) Bonus question: I noticed that the hash functions SHA, MD5,... seem to produce a string that is made up of characters with ASCII codes in printable range. Is that a problem when hashing passwords that are used to encrypt plaintext?]

EDIT: I realized that I was wrong about what I had "noticed" in questions 2.

The OP wants a Key Derivation Function suitable for producing a key for the block cipher TEA, from Password and Salt. He is considering the use of PBKDF2, a common method designed for that purpose, which has a parameter controlling how slow the computation is, and thus the difficulty of password cracking.

PBKDF2 is a giant progress compared to practices such as MD5(Password||Salt) → Key (where || stands for concatenation), but it is significantly inferior to what state-of-the-art allows. See the following table from the paper Stronger Key Derivation via Sequential Memory-Hard Functions defining the Scrypt Password-Based Key Derivation Function.

In the following I discuss the PBKDF2 avenue envisioned by the OP; I might propose a simpler one, illustrating the concept of Sequential Memory-Hard Key Derivation Function, in a later post under preparation.

PBKDF2 requires a Pseudo-Random Function PRF(Key,Message) → Output with variable-length key and message inputs, and fixed-size output. The PRF commonly used is HMAC. HMAC in turn requires a hash function. In order for HMAC's original design rationale to hold, that hash must use the Merkle–Damgård construction, with a round function that is a One-Way Compression Function OWCF(Block,State) → NewState with fixed-size block input and state input/outputs. The simplest construction for an OWCF from a block cipher is the Davies-Meyer construction. In that context, one uses a block cipher with block size the hash's output size, and usually key input at least twice that. In the usual PBKDF2 with HMAC-SHA-1, the OWCF is build from a block cipher with 160-bit block size (the state in the OWCF) and 512-bit key (the block in the OWCF). TEA, with its 64-bit block and 128-bit key, is not a good direct fit for that block cipher.

Further, in that use, the block cipher should be resistant to related-key attacks, and in particular must not have equivalent keys, which trivially turn into collisions; these get up the chain into hash collisions, HMAC key and message collisions, PBKDF2 equivalent passwords and equivalent salts. TEA has equivalent keys (and lesser related-key vulnerabilities). In the context, using TEA as a block cipher in the Davies-Meyer construction, it would be easy to exhibit a class of equivalent passwords and equivalent salt (by toggling bit 7 of some bytes so as to reach equivalent keys in TEA), which shows that a sizable portion of the entropy in the input is lost (1/64 for random input). This would not be a total disaster in practice, but for a recommendable scheme along the above lines, we want to strengthen the cipher w.r.t. related-key attacks, and (as lesser need) double its block and key size.

One sound scheme to construct that 128-bit block, 256-bit key cipher DTEA is a 4-rounds symmetric Feistel cipher with TEA as the round function, using at each round a 128-bit sub-key, derived as two 64-bit halves, each obtained by a CBC-MAC of DTEA's 256-bit key, using CBC-MAC with TEA keyed by an arbitrary 128-bit constant. We need 8 such constants (2 per round), and a total of 36 TEA per DTEA. This is slow, but in the context slowness that can't be optimized out is no issue. The paranoid could even use D2TEA derived from DTEA the way DTEA is derived from TEA; that would raise the difficulty of exhibiting even two equivalent passwords or salts from about $2^{64}$ DTEA (hard but feasible) to $2^{128}$ D2TEA (infeasible in the predictable future).

Thus my answer to the question is: If you want to use PBKDF2 with TEA as the core function then

use TEA to construct a wider cipher DTEA better protected from related-key attacks, using the Feistel construction with sub-keys derived by CBC-MAC, as above;
use DTEA in the Davies-Meyer construction to build an OWCF;
use that OWCF in a Merkle–Damgård construction to build a hash function;
use HMAC to turn that hash into a PRF;
use that PRF in PBKDF2;
build salt as the the concatenation of context information (user or file name..) and if feasible 256 bits of true random (else use date and time to the best accuracy available);
generate the desired key as PBKDF2(Password, Salt, c, dkLen=16), with iteration count c set as high as practical.


Are there any security issues when replacing the SHA-256 initialisation values? As RFC 4634 describes in section 6.1, SHA-256 is initialized using eight 32-bit words.

These were obtained by taking the first 32 bits of the fractional parts of the square roots of the first eight prime numbers:

H(0)0 = 6a09e667
H(0)1 = bb67ae8
H(0)2 = 3c6ef372
H(0)3 = a54ff53a
H(0)4 = 510e527f
H(0)5 = 9b05688c
H(0)6 = 1f83d9ab
H(0)7 = 5be0cd19

These are obviously meant to be "nothing up my sleeves" numbers.

Assuming interoperability — read: compatibility between users — isn't an issue, I've got the following questions:

Are there any security issues related to replacing those SHA-256 initialisation values?

The plan is the one-time use of a CSPRNG to get alternative values for a specific (in-house) implementation; which I presume to be a safe way to get good alternative values. Please correct me when this assumption is wrong.
Are some initialisation values worse than others?

In other words: is the Merkle–Damgård construction, and/or the SHA-2 algorithm design as a whole, susceptible to weak initialisation values along the lines of 0-key problems as applicable to cipher analysis? Or could we set them all to zero without any impact on cryptographic security?

NB: pointers to related research paper(s) welcome, but not a "must".

Random IVs are fairly clearly ok. NIST secure hash standard defines SHA-512/t with arbitrary t and different IV values that are themselves outputs of SHA2, and Merkle-Damgård hashes basically do the same internally when you have a multi block massage. There should be no reason you could not do the same with SHA-256 or with another PRNG generating the IV values.

Nonrandom IVs are theoretically a different matter. Current (partial) attacks on SHA2 work on the compression function and find collisions for any predetermined IV/chaining value. However, at least in principle some values could be easier to attack. That would not break the whole hash as long as the number of weak IVs is negligible.
(As in the case of the Malicious SHA1 linked in the comment by CodesInChaos, but with round constants instead of IV.)


RSA Blind attack help I am trying the Blind signature attack against an RSA crypto system (we have the value of N and e).

The system is defined as:

class RSA:
    def __init__(self, e, d, n):
        self.e = e
        self.d = d
        self.n = n

    def sign(self, msg):
        msg = int(msg.encode('hex'), 16)
        return pow(msg, self.d, self.n)

    def verify(self, msg, sig):
        msg = int(msg.encode('hex'), 16)
        verify = pow(sig, self.e, self.n)
        return msg == verify

This system allows me to do the following:

Sign a message (other than the desired message)
Verify the message

To sign the message, the code interprets my input message as shown below:

m = base64.b64decode(m)
m = int(m.encode("hex"), 16)

The desired message which I want to sign is: "check this"

So, I decided to use the Blind Attack as shown below:

Chose a random value of 'r' such that 'r' is relatively prime to 'n' (gcd(r, n) = 1)
Calculated the blinded message as shown below:

M = "check this"

M = int(M.encode("hex"), 16)

M = 469440048988568330725747

r = 3

So, M' = M * r^e mod N

I got M' = 23197755639757063616251098896030929296620390502715479513148568685304900389950103581065892241031729644711286485127332671201824316337367085311388408882287463092871368604873199283728291840921486779532441684227161682803605783877395206374452279642370838342344078339859990917350469230030211065087702649725450845840496395823640212936132815100326836805829209891510238692029283719097643211255749411742768146971730579472485865485182974850559517457334368981656730791912298827394135772525085384096283147715147158921374800971030021813145161866835151076051818566789845851064713174040021840255625914702552338381580735541362965413692

Then, I sent the above message base64 encoded to the crypto system so that it signs it for me:

base64.b64encode(M') = "MjMxOTc3NTU2Mzk3NTcwNjM2MTYyNTEwOTg4OTYwMzA5MjkyOTY2MjAzOTA1MDI3MTU0Nzk1MTMxNDg1Njg2ODUzMDQ5MDAzODk5NTAxMDM1ODEwNjU4OTIyNDEwMzE3Mjk2NDQ3MTEyODY0ODUxMjczMzI2NzEyMDE4MjQzMTYzMzczNjcwODUzMTEzODg0MDg4ODIyODc0NjMwOTI4NzEzNjg2MDQ4NzMxOTkyODM3MjgyOTE4NDA5MjE0ODY3Nzk1MzI0NDE2ODQyMjcxNjE2ODI4MDM2MDU3ODM4NzczOTUyMDYzNzQ0NTIyNzk2NDIzNzA4MzgzNDIzNDQwNzgzMzk4NTk5OTA5MTczNTA0NjkyMzAwMzAyMTEwNjUwODc3MDI2NDk3MjU0NTA4NDU4NDA0OTYzOTU4MjM2NDAyMTI5MzYxMzI4MTUxMDAzMjY4MzY4MDU4MjkyMDk4OTE1MTAyMzg2OTIwMjkyODM3MTkwOTc2NDMyMTEyNTU3NDk0MTE3NDI3NjgxNDY5NzE3MzA1Nzk0NzI0ODU4NjU0ODUxODI5NzQ4NTA1NTk1MTc0NTczMzQzNjg5ODE2NTY3MzA3OTE5MTIyOTg4MjczOTQxMzU3NzI1MjUwODUzODQwOTYyODMxNDc3MTUxNDcxNTg5MjEzNzQ4MDA5NzEwMzAwMjE4MTMxNDUxNjE4NjY4MzUxNTEwNzYwNTE4MTg1NjY3ODk4NDU4NTEwNjQ3MTMxNzQwNDAwMjE4NDAyNTU2MjU5MTQ3MDI1NTIzMzgzODE1ODA3MzU1NDEzNjI5NjU0MTM2OTI="

Then the system returns me the blinded signature, S'

so, S = (S' / r) % N

24818914914910373440924495286483732355034193918009758466268010322182571967031502513659086048658916042028823976943003185617946970036963881199841837196441552911705581109341260054593328566162456841895142950218979750677266736949402372670566292112370217099902986474876478008060410181643482927728261550661880472137789429832725542464999274462836317230085457545621451042531445414310707428331233889365772556917427615047373474133265125316113512167796060915505971722864776035325707620199263636430413757299372893302287102120461140519757246629337547966487338931336250142558314387457650036181961012203870138191022307166022035263943

So, I have the signature, S corresponding to M.

Now, I can send the message, M to the system along with its signature, S.

However, this is not working and I suspect that this might be due to the fact that M = integer representation of the message. When I send the integer representation of the message, the crypto system again applies (int(message.encode("hex"), 16) on it.

In which format must I send my message for signing?

Note: The attack I am using is similar to the one described here: http://the2702.com/2015/09/07/RSA-Blinding-Attack.html

Thanks.

Here is what should be done:

After getting the blinded message M' You should convert it back to string format. (First to hex, then string)
You should convert this m' to base64 like you did.
Send this base64 encoded message to client like you did.

The rest of the solution looks okay.

P.S: There is still a defect in that solution that i can not find.