Brute-force attack given multiple hash prefixes (Context: I'm auditing some code which I suspect to be insecure, but I'd
like to be able to quantify this.)

Suppose you have a 56-bit secret key ($secret), and suppose you have revealed the following information to untrusted parties:

$salt – An easily discovered string
$prefix – The first 32-bits from sha1($secret + $salt)

Based on a previous
question, an attacker could perform an offline attack using ($salt,$prefix) as a sieve to narrow the list of possible $candidates.  This sieve would reduce the number of candidates from $2^{56}$ to $2^{(56-32)}=2^{24}$.

Now suppose you reveal multiple variations of ($salt,$prefix) (all based on the same $secret).  The attacker now has multiple sieves; if applied iteratively, each sieve would further narrow the list of possible $candidates.

I'd like to understand how quickly $candidates will filter down to the true $secret.  For example, if you have two prefixes, how many
$candidates should be left?  If you have three prefixes, how many
should be left?

If you have two prefixes, say $p_1$ and $p_2$ assuming a well designed hash function, this will give you two lists of possible candidates $L_1,L_2$ each of size roughly $2^{24}.$ The correct value is in both of these lists. It is unlikely to also have spurious candidates since assuming uniformity o relevant variables and fixing, say the list $L_1$, the probability that a random quantity from $\{0,1\}^{56}$ is not in $L_1$ is
$$
\left(1-\frac{2^{24}}{2^{56}}\right)=\left(1-\frac{1}{2^{32}}\right),
$$
since $\lim_{n\rightarrow \infty}\left(1+\frac{x}{n}\right)^n=\exp(x).$ Thus
the probability that the $2^{24}$ elements in $L_2$ all fall outside $L_1$ is
$$
\left(1-\frac{1}{2^{32}}\right)^{2^{24}}=\left[\left(1-\frac{1}{2^{32}}\right)^{2^{32}}\right]^{2^{-8}}\approx \exp(-2^{-8}) \approx 0.9961
$$
so only in one of about 250 trials would there be a spurious candidate in addition to the correct candidate.

Edit: It is widely believed and supported by experimentation that SHA-1 is such a function. Ignore my earlier reference to universal hash functions.


Would it be easier to bruteforce the original data if given two hashes (from different hash functions)? I have a chat server which uses public keys to identify their clients. But if the public key is known, then everyone can send a direct message (DM) to each other, which is annoying. The clients should choose who should DM them.

So I decided to get two hashes of the public key, one for user authentication and one for identifying the public key used to encrypt the direct messaging.

My question is: does having two hashes affect the probability of successfully guessing the original data?

IMO it depends on what you mean by the probability of successfully guessing the original data. Since hashing functions turn input of any size to a fixed-size output, there are (infinitely) many collisions. That may pose a problem with passwords, where any collision results in successful authentication. However, you only care about the correct preimage, as any other input, that produces the same output, (most likely) does not reveal Bob's valid public keys.

Suppose there is an attacker who knows your public keys format and is able to brute-force all possible keys. Then it is likely that more than one candidate will appear (depending on the length of your hash and public keys). The attacker then gets more information from the second hash as to distinguish which candidate is the correct one.

In that sense, you increase the probability of guessing the original data by providing a second hash.

But. I don't think that scenario is much to worry about - as you need the collisions of the first function to feed into the second function to gain advantage (or vice versa) and these are hard to get if the hashing function is well-chosen. Moreover, given that the number of such candidates might not be too high, the attacker might just as well try to DM using candidate keys rightaway.

If you worry about someone finding correct preimage of a given hash (or two), use properly-sized and random salt, different for each user. Ultimate booster: use different salts for each hash.


ElGamal against chosen ciphertext attacks In Hoffstein, Pipher, and Silverman's book An Introduction to Mathematical Cryptography, the authors make the following remark:

  An attack in which Eve has access to an oracle that decrypts
  arbitrary ciphertexts is known as a chosen ciphertext attack. The preceding
  proposition shows that the ElGamal system is secure against chosen ciphertext
  attacks. More precisely, it is secure if one assumes that the Diffie–Hellman
  problem is hard.

where the "preceding proposition" is a walk-through of a proof that if one can decrypt ElGamal ciphertexts, then one can solve the Diffie-Hellman problem.

However, all the sources that I can find online (including several on this site) seem to make the opposite claim, that ElGamal is not secure against chosen ciphertext attacks.  The errata for the book makes no mention of this passage.  Is my understanding of the authors' statement flawed?

As already mentioned in a previous answer and the comments, you are right regarding that ElGamal is not secure against chosen-ciphertext attacks. An immediate reason is that the scheme is multiplicatively homomorphic, and that is not compatible with CCA: the attacker could query the decryption oracle with the ciphertext that results of multiplying the challenge ciphertext and the encryption of some random message; the homomorphism ensures that $Enc(pk, m_b) \cdot Enc(pk, m') = Enc(pk, m_b \cdot m')$, and therefore, the decryption oracle cannot refuse to respond to the query since the input is different to the challenge; now the adversary only has to remove $m'$ to recover the challenge message.

Also, something worth mentioning is that the proof given in that book does not follow the traditional conventions for proofs in provable security. First, they are not defining the security goal explicitly (i.e., are they trying to prove one-wayness? indistinguishability? some other notion?). And second, usually proofs are constructed as a reduction to a hard problem; that is, these proofs aim to reach a contradiction by which, if the scheme is insecure, then you could solve the hard problem. These proofs follow this template:

Define a security goal (e.g., Indistinguishability (IND)) and an attack model (in this case, chosen ciphertext attacks). Together they form a security notion (e.g., IND-CCA).
Assume the existence of an adversary $\mathcal A$ that breaks the scheme under the security notion.
Simulate the environment of $\mathcal A$. That is, you explicitly construct the oracles required by the attack model. Usually, you need to somehow embed elements from the hard problem instance you want to solve (e.g., elements from a DH tuple $(g^a, g^b)$).
Prove that using $\mathcal A$ you could solve the hard problem.
Since the hard problem is assumed to be hard, we have reached a contradiction, so the initial assumption (i.e., the statement in step 2) is false, and the scheme is actually secure.

However, the proof given in the book is doing something different. It is first assuming that there exists a decryption oracle, and then proving that you could solve the DH problem using it. Since the DH is hard, then the initial assumption must be false. In this case, the initial assumption is that there exists a decryption oracle, but this does not prove at all that the scheme is secure under chosen-ciphertext attacks.


CCA secure vs AE scheme We already know that every authenticated encryption scheme is CCA secure, I was wondering about the converse.
I believe it is not true, and I am finding trouble to construct a scheme which is only CCA secure but is not an authenticated encryption.
How to show the existence of an encryption scheme which is only CCA secure but is not an authenticated encryption?

Let $(\mathsf{Enc},\mathsf{Dec})$ be an authenticated encryption scheme, i.e. it is both IND-CPA secure and INT-CTXT secure (and thus by extension IND-CCA secure). Let $\mathcal{M}$ be the message space of this encrytion scheme and let $\hat m\in\mathcal{M}$ be an arbitrary fixed message.
Now construct the symmetric encryption scheme $(\mathsf{Enc}',\mathsf{Dec}')$ with $\mathsf{Enc}'=\mathsf{Enc}$ and $\mathsf{Dec}'$ defined as
\begin{align*}
&\underline{\mathsf{Dec}'(k,c)}\\
&m := \mathsf{Dec}(k,c)\\
&\textrm{if } m = \bot\\
&\quad \textrm{return } \hat m\\
&\textrm{else}\\
&\quad \textrm{return } m
\end{align*}
It is easy to show that this scheme remains IND-CCA secure. The reduction to the IND-CCA security of $(\mathsf{Enc},\mathsf{Dec})$ merely needs to replace all $\bot$-responses of the decryption oracle with $\hat m$.
At the same time, it is trivial to break INT-CTXT security of $(\mathsf{Enc}',\mathsf{Dec}')$ by simply presenting literally anything as a ciphertext.
This means that if secure authenticated encryption exists, there also exists IND-CCA secure encryption that is not INT-CTXT secure.


Questions about the argon2 options So because I am currently working on a Project in which I will use Argon2 I need some answers to questions about the options of Argon2.

I didn't find anything about them.

What exactly does the parallelism option do?
What exactly does the memory option do?
What exactly does the Iterations option do? How does it work? Is it just re-Hashing?

The entire point of a key-derivation function like Argon2 is to increase the time (difficulty) it takes to create a key, and as a side effect, increase the resources required to attack the key.

The problem with other key functions like PBKDF2 is that you can only set the total iterations required, while this is fine for many applications, it isn't ideal for password hashing. PBKDF2 can be easily hashed quicker by using specific equipment. A graphics card is designed to be able to perform repetitive actions relatively fast. This makes hashing an easy task to allow a GPU to quickly power through. However, while GPUs have access to many logical processors, they are quite limited on access to fast memory.

Argon2 is designed with this in mind, allowing three different parameters for it to be enabled best with your hardware. As such it comes with three different adjustable factors (called cost):

Iterations: A total time cost, requiring Argon2 to run a certain amount of time before the output is received, allowing you to adjust how long it takes for an output to generate.
Memory: A system resource cost. Memory is specified as a set amount required for each running instance of the hash function. Unlike iterations, memory is not something that can be optimised for, it's a physical limit that needs a certain sum of physical memory (often RAM) available, and free for hashing. Unless a high-speed storage density revolution occurs in the future, this is going to be one of your hardest hitting costs
Parallelism: The total sum of threads which will run at once in order to generate an output. If you have a large quantity of logical processors available, increasing this cost requires an attacker to either process less congruent attacks at a time, or purchase more expensive equipment.

(It is also important to note that there are several different inputs other than those listed, but those are mostly for low-level API usage of the Argon2lib and can be found here)

A quick guide for configuring Argon2 costs:

Set your Memory cost as high as you can comfortably support. If you at most expect to have 10 users log in at the same time on a dedicated server and have a total of 20 GBs of memory available, issue a total of 1.5 GBs per function run. Also, always remember to be scaling friendly: if you have 20Gbs of memory, and only 10 users login at any given time currently, but you expect to have over a hundred at a time in the future, set your parameters to support such an event.
Set your parallelism in accordance to what your hardware can support. I have a 4 core computer, as such, I set KeePass's parallelism to 4 threads, your needs will vary depending on total logins per second and what your hardware can do.
Set your iterations to a reasonable time, depending on your application. Start with a low value like 10, run your function, and see how long it takes to receive your output, if it feels too fast, increase your iterations. Continue to repeat this process until well-tuned. You will want to set your iterations dependent on your application's needs. If you are performing password hashes for clients on your web service, you may want to aim for around 0.2 seconds per hash. However, if you are doing client-side hashing for local storage encryption, you may want to aim for a couple of seconds as you will likely only ever expect to run one function at a time and run it very few times a day.

Hope this helps and I explained things well for you!


How different is SHA-512/224 when compared to SHA-512? I understood from the NIST SHS specifications (FIPS 140-4) that the difference between SHA-512 and SHA-512/224 the two differences are the initial hash value and the final result truncation
I changed the initial hash value of SHA-512 to that one of SHA-512/224 as specified in the SHS specifications and then built the CAVS tests. Then I started testing against the copied CAVP test vector.
Lets consider the first case:
Len = 0
Msg = 00
MD = d14a028c2a3a2bc9476102bb288234c415a2b01f828ea62ac5b3e42f

But the result I am obtaining for the above input is:
SHA512/224 digest
     6ed0dd02806fa89e25de060c19d3ac86cabb87d6a0ddd05c333b84f4

Lets consider the second case:
Len = 8
Msg = 84
MD = 3cd36921df5d6963e73739cf4d20211e2d8877c19cff087ade9d0e3a

But the result I am obtaining for the above input is:
SHA512/224 digest
     8f8fdcb3f617a2d809b3132860b02fee00bdd927d541d42073dd12e7

What am I doing wrong?

As stated by FIPS 186-4 (6.6) The only two differences between SHA-512 and SHA-512/224 are the eight 64-bit words used for initialization, given by FIPS 186-4 (5.3.6.1); and result truncation to the first 224 bits of the 512-bit result: $H_0^{(N)}$, $H_1^{(N)}$, $H_2^{(N)}$ each 64-bit, and the high-order 32 bits of $H_3^{(N)}$.

I suggest to start by checking the SHA-512 implementation pass test vectors; then implement the truncation, and test; then change the initialization value, and test.

[epilogue: that was the test vectors, see this]


AES key/ciphertext space sizes This is giving me a brain ache now... If I have AES-128, block is 128 bit, then every plaintext (128-bit) can be encrypted to some ciphertext that is also 128-bit. This is the block size. But: 128-bit block can have 2^128 different values. So if I have 128-bit key - then it seems to be natural to have every different key produce different ciphertext for a given plaintext - $P_1$. So let's take another plaintext - $P_2$, which also can be encrypted to $2^{128}$ different output blocks - but still the same values - we have the same binary 128-bit block - again $2^{128}$ values - the same values that $P_1$ used. How AES differentiate between the two?

The second question: what about AES-256? Here I have $2^{256}$ keys, but again for given plaintext - $P_1$ I can get no more than $2^{128}$ output blocks, is it that I only have $2^{128}$ unique keys even for AES-256? What about the previous situation - I can have only $2^{128}$ different output blocks- so what's the use of having $2^{256}$ key space? Shouldn't the block size be also increased for AES-256? Or am I making some terrible mistake here?

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

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

In any case...

  How AES differentiate between the two?

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

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

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

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


What are requirements of the audio input to be encrypted using AES? I want to inquire that what are requirements of the audio input to be encrypted using AES. Is encrypting a mp3 file different from encrypting an aac file?

Thanks!

As LightBit notes in the comments, modern ciphers like AES work on arbitrary binary data, and don't care about what those bits represent.  Thus, you can use AES to encrypt any kind of (audio or other) files or streams.

That said, there is one detail to keep in mind: basically all practical encryption schemes (including AES in any of the commonly used modes) leak the length of the data being encrypted.  (Some schemes may round the length up to say, the next multiple of 16 bytes, but that still leaks the approximate length.)

When encrypting compressed data (like MP3 / AAC audio), this can in turn leak information about the content: for example, 1 second of silence compresses a lot better than 1 second of speech (which, in turn, compresses a lot better than 1 second of random noise).  Thus, just by observing the length of the encrypted messages or packets, an attacker may be able to learn information about the sounds encoded in the encrypted data.

This is not just an academic concern: precisely this kind of an attack has been used to break VoIP audio encryption by researchers a few years ago.  The CRIME and BREACH attacks on HTTPS also rely on compression leaking data about the plaintext via the message length, although those are not specific to audio.

The only general solution to message-length leaks is to ensure that all messages (or packets, for something like a real-time telephony protocol) have the same length (or, at least, that the message length only depends on things you're reasonably sure it's safe to leak, like the duration of the conversation).  For audio encryption, this might be achieved e.g. by first using an audio compression algorithm with a fixed maximum bitrate, and then padding any compressed packets to a fixed length before encryption.


Calculating the amount of zero bits to be appended to the message From FIPS 180-3

  Suppose that the length of the message, $M$, is $l$ bits. Append the bit $1$ to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation $l + 1 + k \equiv 448 \mod 512$ . [...] For  example,  the  (8-bit  ASCII)  message  “abc”  has  length $8 \times 3 = 24$, so the message is padded with a one bit, then $448 − (24 + 1) = 423$ zero bits [...].

The example only works for $0 \leq M < 448$, so I've come up with this formula for calculating $k$.

$$k = 448 - (l + 1) + 512 \cdot \left\lfloor \frac{l + 64}{512} \right\rfloor $$

or shorter

$$k = 447 - l + 512 \cdot \left\lfloor \frac{l + 64}{512} \right\rfloor $$

Is this the shortest/most performant way to calculate $k$?

If you have an implementation of an integer modulo operator, then

$$k = (447 - l) \bmod 512$$

should be the right solution. If your modulo operator can return negative results, do this:

$$k = ((447 - l) \bmod 512 + 512) \bmod 512$$

This seems simpler than using your division and flooring.

That said, you actually don't really need the number of zero bits for the padding, but you need to know how many 512-bit (e.g. 64 byte) blocks to hash. These then will be filled by:

the data
one 1 bit
a number of 0 bits (between 0 and 511, to fill the block)
the length, encoded as a 64-bit number.

We need just enough ($b$) blocks to have space for the data and the length (and the one 1-bit):

$$ b = \left\lceil \frac{l + 1 + 64}{512} \right\rceil $$

If you hash only data in whole bytes (as usual), the formula becomes

$$ b = \left\lceil \frac{l_8 + 1 + 8}{64} \right\rceil, $$

with $l_8 = \frac l8$ the length of the data in bytes.


Does signing multiple messages with the same RSA key weaken the encryption? Here is the scenario,

I am signing roughly 1000 messages, which consist of 16 byte hashes, with 1024 bit RSA.
The private key is only used to sign the hashes, and there is no padding scheme.

The attacker has access to all 1000 messages and the public key. That is all they have to work with (no chosen plaintext ability, etc).

Does access to a large number of signed messages make it easier for the attacker to create a valid signature for a hash of their choosing?

If so, how? And would a padding scheme protect against it?

I'll ignore the term "encryption" in the title, since it is improper: signature is not encryption. Instead I'll try to answer the question:

  Does direct textbook RSA signing of hashes of 1000 messages $M_j$ per the textbook RSA signaing function $\mathcal S$, as $S_j=\mathcal S(H(M_j))=H(M_j)^d\bmod N$, weaken the resistance against signature forgery for other messages under the same scheme, given $(N,e)$ a public key with 1024-bit RSA modulus.

Yes, for too narrow a hash $H$. One attack strategy could be that of Yvo Desmedt and Andrew M. Odlyzko: A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, in proceedings of Crypto 1985.

The basic attack

Factors the $H(M_j)$ and keeps those that are $B$-smooth, forming a (sparse) matrix $A$ with one column per such $j$, one line for each prime $p_i$ that appears in such factorizations, collectively forming the factor base. The multiplicity of prime $p_i$ in $H(M_j)$ is at line $i$ column $j$ of $A$.
Factors many $H(M'_k)$, and for those which factors all are among the factor base, form the vector $V$ of the multiplicities of that $H(M'_k)$, and try to solve for $X$ the system $V=A\cdot X$ where $X$ is a vector with one entry per column in $A$, and operations are in $\Bbb Z_e$.
Once such $M'_k$ is found, computes the signature of $M'_k$ using

the multiplicative property: $\mathcal S(H\cdot H'\bmod N)=\mathcal S(H)\cdot\mathcal S(H')\bmod N$,
the known signatures $S_j$,
the coefficients in $X$, corresponding to powers of the $S_j$,
the fact that forall $p_i$, it holds $\mathcal S({p_i}^e\bmod N)=p_i\bmod N$.

It can work, or not, depending on:

The width of the hash. The narrower, the more smooths, the easier the attack.
The value of $e$. Lower $e$ (e.g. $e=3$) make the attack easier.
If the adversaries are able to choose some of the $M_i$; this allows the adversaries to try much more than 1000 messages in step 1, somewhat offsetting the effect of a wider hash.

In an improvement extending the applicability to less signed messages or wider hashes, pairs of $H(M_j)$ having a single prime factor larger than $B$ are kept separately if another $H(M_{j'})$ is in this case and shares the same larger prime factor, with the difference modulo $e$ in the respective multiplicities of the primes in the factor base for $H(M_j)$ and $H(M_{j'})$ used for an additional column in $A$. A further improvement uses two large primes.

It can be predicted about how many messages are required for a given hash width and $e$, and the work necessary. I wish I knew exactly how! There is an analysis in appendix C of the full version of Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann's Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures, in proceedings of Crypto 2009, but it does not account for $e$, nor of the large prime(s) improvement, nor of working under the constraint of relatively few non-chosen signed messages.

  would a padding scheme protect against it?

Yes, by making the input of the textbook RSA signature function $\mathcal S$ too large to allow the attack.


Quantum-secure obfuscation My question is a follow-up to a recent question regarding quantum-secure time-lock puzzles (TLPs). TLPs can be built (in principle) from indistinguishability obfuscation (iO) [BGJ+,BGL+] as noted in this thread. As a corollary, quantum-secure iO would lead to quantum-secure TLPs (provided that there are inherently-sequential languages in the quantum world, which seems plausible).

So it boils down to whether any of the candidate constructions of iO are quantum-secure. It seems that some of the candidates are broken given a quantum computer [PM]. The question is whether any remaining candidate construction of iO is believed/conjectured to be quantum-secure?

[BGJ+]: Bitansky et al., Time-Lock Puzzles from Randomized Encodings, ITCS'16

[BGL+]: Bitansky et al., Succinct Randomized Encodings and their Applications, STOC'15

[PM]: Pellet-Mary, Quantum Attacks against Indistinguishablility Obfuscators Proved Secure in the Weak Multilinear Map Model, Crypto'18

Turns out that this was an open question. Brakerski et al. [BDGM] posted a paper today on the ePrint claiming the first (provable) post-quantum construction of iO. Their underlying security assumption is the "circular security" of an encryption scheme based on LWE.
[BDGM], Brakerski, Döttling, Garg and Malavolta, Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices, ePrint Archive


Prove in Zero Knowledge the execution of a function Given a function:

$$Y = a * b$$

Is there a way to prove in zero knowledge that a value $Y$ was gotten, without revealing $a$ and $b$?  Alternatively, that we have knowledge of $a$ and $b$ such that their product equals $Y$.

public : $Y$

private: $a$,$b$

Yes, what you describe is an example of a zero-knowledge proof.

ZKP systems such as libSNARK, libSTARK, pepper-project, etc. can help the prover generate a proof that he/she knows private $a$ and $b$ such that $Y = a * b$ and then a verifier can check that the computation was done correctly without ever knowing $a$ and $b$.

What you describe is the knowledge-of-factorization example and I recently implemented that in the pepper-project here.


How can I encrypt more than 64 bit with the Data Encryption Standard? The Data Encryption Algorithm is designed to encipher and decipher blocks of data consisting of 64 bits under control of a 56-bit key.

If my data is more than 64 bits, (suppose 66 or 67 bits), will it take remaining bits as 0s (zeros)?

How would it encrypt?

Well, the methods we use to take a block cipher (such as DES), and turn it into an actually useful function (say, to encrypt a large message) is called a mode of operation.

Such a mode of operation takes the message (generally of arbitrary length), and processes it (usually block by block), using the block cipher as a primitive.

There are a number of such modes of operation, the most popular of which are CBC mode and counter mode.  BTW: the mode where you just send the message in pieces to the block cipher in 64 bit chunks (and the encrypted message is just the output of the block cipher) is referred to as ECB mode – that is rarely appropriate (and certainly never unless you know what you're doing).

As for which mode would be appropriate for you, well, I can't answer that without knowing more about your application (and the security properties you need).

In addition, you say that you are intending to use DES.  DES is generally frowned upon nowadays (machines to break it are known to exist); the block cipher AES is usually a better choice (it is about as efficient in software, and it is currently believed to be secure).


How is multiplication inverted in IDEA's decryption round? As we can see in the picture we have a multiplication in this algorithm,
we know that two 16 bit inputs should have a 32 bit output, but here we just use 16 bits of the 32 bit output.

For decryption we can reverse the algorithm from bottom of the algorithm to top, but how can we invert the multiplication that produced value of $a$ to recover $I$?

The multiplication operation is indeed not uniquely reversible given just the output. But we also have one of the inputs, namely, the subkey. We can use that to reverse the multiplication.

Decryption for IDEA requires changing the subkeys in the key schedule. I didn't find a good description of IDEA online, so I went back to Applied Cryptography, 2nd Edition, which had a good description (as well as the provided diagram):

  Decryption is exactly the same, except that the subkeys are reversed and slightly different. The decryption subkeys are either the additive or multiplicative inverses of the encryption subkeys. (For the purposes of IDEA, the all-zero sub-block is considered to represent $2^{16} = –1$ for multiplication modulo $2^{16} + 1$; thus the multiplicative inverse of 0 is 0.)

For decryption you would take the result of the original multiplication operation and multiply that by the multiplicative inverse of the subkey that was used. (The subkey was derived from the original key, and the multiplicative inverse of a subkey can be calculated from the subkey.) This yields the original input value.

This works mathematically because the multiplication operation is performed modulo $2^{16}+1$ which (combined with with the provided special case treatment of 0) forms a mathematical group structure. Within a group, every multiplication operation is guaranteed to have an inverse value that can be used to reverse the operation.

It forms a group because, in general, the numbers $1, 2, ..., p-1$ form a multiplicative group modulo a prime $p$ (this group can denoted by $\mathbb{Z}^*_p$), and in our case $2^{16}+1$ is prime. The special case for 0 is necessary because of a minor implementation complication: A variable value of $0$ isn't in the group and $2^{16}$ can't be stored in a 16-bit variable. This was easy to resolve: Define the unused $0$ to represent $2^{16}$.


How secure is this use of Ziv-Lempel encoding? I'm reading patent application US 20120278897 A1 — “System and method of sort-order preserving tokenization”. Near the bottom they describe their token generation algorithm, which basically involves using the first few characters of a string as input to a modified order preserving Ziv-Lempel compression function described in this patent. They then prepend the output to the token and treat it as a kind of 'sort prefix' which can enable sorting.

I would like to know what (if any) security can be guaranteed for the characters of the plaintext used to generate the 'sort prefix'. More generally, how difficult is it for an adversary to distinguish two strings which have been Ziv-Lempel encoded but not encrypted?

The patent application makes this statement:

  An attacker may still be able to determine the first character with some level of certainty, but since they would no longer have all of the characters encoded within the Ziv-Lempel tree, the token is no longer susceptible to a dictionary attack

Given enough samples of this compression function is it possible for an attacker to partially reconstruct the tree and guess the input for an arbitrary output value?

Ziv-Lempel is a data compression algorithm, so in general it doesn't protect your data. As for your question:

  More generally, how difficult is it for an adversary to distinguish two strings which have been Ziv-Lempel encoded but not encrypted?

An adversary just can decode two strings and compare them. Due to the fact that Ziv-Lempel is an encoding algorithm, if you send your data to somebody then you have to send the other information needed to decode your data by the receiver. So, in this case an attacker can easily get access to the transmitted data.


Are there post-quantum cryptosystems with a gap between classical and quantum security? Is there a gap between classical attacks and quantum attacks against some post-quantum security assumptions? (I'm particularly interested in asymmetric cryptography.)

I understand that there is no polynomial-time algorithm against these problems (otherwise it will no longer be considered as a PQ security assumption). But is it sometimes the case that we know more efficient quantum attacks than classical attacks (even if it's still exponential)?

Here's an example where the best known quantum attack is, in a sense, just "halfway" between the best known classical attack on one side, and a complete break on the other:
Inverting a cryptographic group action such as CSIDH.

Let $G$ be a (finite) commutative group $G$ acting on a set $X$, i.e., we consider a map
$$ \ast\colon\; G\times X\to X$$
that is compatible with the group structure of $G$ in the sense that $1\ast x=x$ and $(g\cdot h)\ast x=g\ast(h\ast x)$.

The problem to be solved is analogous to the discrete-logarithm problem:

  Given two elements $x,y\in X$, find $g\in G$ with $g\ast x=y$, assuming it exists.

Classically, the best known attack is a meet-in-the-middle approach à la baby-step giant-step, where the group $G$ is split into two subsets $U,V\subseteq G$ such that $G=U\cdot V$, and one looks for a collision between the two sets $U\ast x$ and $V^{-1}\ast y$. Indeed, when $u\ast x=v^{-1}\ast y$, then $(u\cdot v)\ast x=y$. This takes time and space $O(\!\sqrt{\lvert G\rvert})$, which is exponential in $\log{\lvert G\rvert}$.
(In reality, there are better time-space tradeoffs than this simplistic approach.)

Quantumly however, this problem can be attacked using Kuperberg's algorithm [1,2] for the abelian hidden shift problem, and this takes subexponential (but superpolynomial) time in the group size. More concretely, the asymptotic cost is
$$ {\exp}\Big(\!\sqrt{\log{\lvert G\rvert}}+o(1)\Big) \text, $$
which can be roughly summarized as "taking a square root in the exponent".
(For comparison, the number field sieve for integer factorization is also subexponential, but with a cube root.)


Why this malicious behavior of corrupted sender isn't considered in malicious-secure OT? I have read some oblivious transfer protocols, and I am confused about why they do not mention the malicious behavior that the corrupted sender may encrypt the wrong message $x_0'$ and $x_1'$ so that the honest receiver will receive the wrong result $x_\sigma'$. I think this totally breaks the correctness of OT and I don't know why the malicious secure OT protocol did not mention it. I know that the committed OT can prevent this behavior, but is this not a malicious behavior that one malicous-secure OT should consider?

In MPC we judge security by comparing to the "ideal world" where a trusted third party does the entire computation. In the ideal world, an adversary can send anything it wants as input to the trusted third party. In the ideal world, when it comes to malicious adversaries, there really is no valid sense of a "correct/incorrect input" for the adversary. (For semi-honest adversaries, their input is supplied by the external environment and they are bound to use it in the ideal world.) Since "using whatever input you like" is possible on the ideal world, it is not considered an attack against the protocol.


Does secure multiplication makes sense in the case of 2 inputs? I am looking at a protocol to securely multiply numbers, so as to preserve privacy of inputs.

In particular, suppose there are three parties $P_1$, $P_2$ and $P_3$ and 2 numbers to multiply, $a \in \mathbb{F}$ and $b \in \mathbb{F}$ such that $\mathbb{F}$ is a finite field of prime order $p$. More precisely, $a$ is the $P_1$'s input, $b$ is $P_2$'s input and $P_3$ has no input. $P_1$ and $P_2$ shares their input among the parties using 2-out-of-3 secret sharing and, in this way, each party can compute a share of the product. Then, shares of the product are securely summed and all the parties can compute the result.

In this aim, I am wondering whether does it make sense when we have only two parties?

If $p$ is big enough (such that $a \cdot b < p$) , once $P_1$ knows $a \cdot b \mod p$, by knowing $a$, it could easily compute the secret value $b$.

For this reason, I do not see the point of using secure multiplication in this case. Could somebody help me understand this?

There is no way to avoid that a party infers knowledge about another party input by looking at the result and his or her input. This is not considered a security issue of the protocol.


Many consecutive hashes to slow down brute force attack? I've heard that hash algorithms like bcrypt are more secure because they take longer to complete, and therefore take much longer to brute force, without a noticeable delay for legitimate users. Would using a faster algorithm, such as SHA-256, multiple times, be secure? For example:

hash = "password"
for x in range(5000):
    hash = hashlib.sha256(hash).hexdigest

As it has to hash the data, then hash the hash, and so on, taking much longer than a single SHA-256 hash, wouldn't this accomplish the same thing?

Instead of that home-grown scheme, I would use PBKDF2 instead if you simply are sold on the idea of iterated hash schemes. It uses an such a scheme, although not exactly the one you have described, and is well-studied and considered secure.

However, PBKDF2 doesn't offer many advantages over bcrypt, as PBKDF2 is still vulnerable to GPU and FPGA/ASIC brute-force attacks. bcrypt resists GPU brute-forcing because of the 4K table used in the algorithm, which forces contention for the global memory bus in GPUs. But bcrypt is still potentially vulnerable to FPGA/ASIC attacks, although most people don't have to worry about that.

A newer KDF, scrypt, is also tunable for the amount of memory it uses, so it is more resistant (when properly tuned) to FPGA/ASIC attacks than bcrypt. However, scrypt is relatively new (2009) when compared to bcrypt (1999), so that may make you somewhat nervous.

Essentially, to store passwords, you should be probably using bcrypt, since it seems to hit a sweet spot of being GPU resistant as well as being sufficiently mature. But PBKDF2 and scrypt are still good; using any one of the three is really fine.

For more information, I would recommend looking at the following question which has an (excellent) top answer by Thomas Pornin: Do any security experts recommend bcrypt for password storage? He is infinitely more credentialed than I am, so if you don't believe me, hopefully his testimony will be compelling.


Mitigating Side Channel Attack (SCA) The SCA power attack described in 2016 article called "Power Side Channels in Security ICs: Hardware Countermeasures", depends on the measurement of power consumption fluctuations during AES-128 execution, for either known plain text, or known cipher text. In addition, the attacker has the ability to change the cipher text (CPA attack). Nevertheless only one of them, either the plain text or the cipher text need to be known to the attacker.

Suppose one avoids exposing both of them, for instance by using secret internal key AND secret internal counter for counter (CTR) mode encryption. In that case the AES-128 block cipher encrypts a counter that is not known with a key that is not known.

Additionally the cipher text is located in an external Flash. And finally, the attacker cannot change the cipher text, as described in the article.

Is such a scheme still exposed to side channel attacks?

As you are always decrypting the same flash content with the same key, statistical attacks like DPA do not work, as they try to find dependencies between two random variables (one being an intermediate value predicted using parts of the key and the other one being the measured current consumption(s)), where in your case one of them is constant.

The only uses an attacker can get from several measurements (instead of using just one) is to take the average to reduce the noise or to apply an attack that exploits the noise. Otherwise the attacker basically has to use an attack that works with a single power trace.

If an attacker is able to run the identical software on an identical device where (s)he can choose the key and the cipher text, (s)he can use it to run the profiling phase for a template attack, and hope that both devices have very similar power characteristics.

As template attacks calculate likelihoods depending on the observed noise, you can combine the results of several measurements to improve your chances to recover key and data.

From my experience the success probability for a very skilled attacker (using an optimal template attack implementation combined with key enumeration techniques) are relatively low if the AES is implemented in hardware, but pretty good for a software implementation on a leaky device.


How is the session key more secure than the public key? From the website of GNU Privacy Guard (GnuPG):

If an attacker could decrypt a session key it would only be useful for reading the one message encrypted with that session key. The attacker would have to start over and decrypt another session key in order to read any other message.

From my understanding, if an attacker is able to decrypt a session key which was encrypted through a public key, then the attacker practically has the corresponding private key pair.
Hence, it is not difficult to decrypt any further session keys encrypted by the public key.
How does a session key make this any more secure? I can only see this as redundant security.

From my understanding, if an attacker is able to decrypt a session key which was encrypted through a public key, then the attacker practically has the corresponding private key pair.

Effectively yes, however only for that single message. Note that session keys are chosen independently and so leaking one doesn't allow you to guess any others. The public key encryption is also independently randomized preventing efficient recovery from the known plaintext. Then, as soon as you consider more than one message, leaking a strict subset of session keys is not as powerful as leaking the private key once.

If you're looking for a scenario where recovery of the session key is sometimes possible but recovery of the private key is not consider the following:
Suppose you run on an old copy of Debian with a weak RNG. Further suppose that you want to send a message to somebody else running a modern copy of Debian who also generated their private key on that modern copy. Now because of the RNG bug, you accidentally pick a weak session key and encrypt it. You then send a message which gets observed by an adversary knowing you run old Debian and brute-forces the session key exploiting the bad RNG output. Now your message has leaked, but no messages from other parties using good RNGs leaked.
If this is "too far-fetched" replace the Debian RNG bug in the above explanation with say a Spectre side-channel leaking the session key.


Can I pre-define the points in Shamir's Secret Sharing algorithm With Shamir's secret sharing is it possible to pre-define the points returned by the algorithm?

For simplicity if I have (k, n) where k=2, and n=4, and I have the points X,Y,Z, and Q. Can I create the coefficients so that X,Y,Z, and Q are the points returned from the algorithm.

If yes will it still be secure (or secure enough)?

Edit:

Change my example to k=2 instead of k=1 to keep the comments from degenerating into a discussion on the merits of only needing a single piece of knowledge to access the secret.

With Shamir's secret sharing for the case of $k$ out of $n$, you construct a random polynomial of degree $k-1$, because $l$ points uniquely identify a polynomial of degree $k-1$.

The usual way to construct said polynomial is to uniformly choose coefficients $a_1$ through $a_{k-1}$ and setting $a_0=s$.

There is an alternative to that, where you choose $k-1$ points uniformly at random. The $k$th point is then $(0,s)$, you can compute the polynomial defined by those points and then compute the remaining $n-(k-1)$ points.
There is absolutely no difference between the two approaches.

So in summary: No that is not possible. You can freely choose at most $k-1$ shares. And also for the security to hold, those must be chosen uniformly at random.


How secure is a pronounceable password in terms of entropy? There are some strong studies which support the use of pronounceable passwords and multiple tools which provide generation of such passwords.

According to this question the entropy of a password depends on its method of generation but how can I be sure that my generated pronounceable password has enough entropy for my use? (for example, in case of pwgen open source software)

Below is a pseudocode for generating a pronounceable password. However, this might be the simplest possible solution and I am rather interested in existing "conventional" methods.

vowels = A, AI, AU, E, EA, EE, I, IA, IO, O, OA, OI, OO, OU, U
consonants = B, C, CH, CL, D, F, FF, G, GH, GL, J, K, L, LL, M, MN, N, P, PH, PS, R, RH, S, SC, SH, SK, ST, T, TH, V, W, X, Y, Z
theLastOneIsAVowel = True
while length(strPassword) < Minimum_Length do
if theLastOneIsAVowel then
strPassword = strPassword + randomElementOf(consonants)
else
strPassword = strPassword + randomElementOf(vowels)
endif
theLastOneIsAVowel = ~(theLastOneIsAVowel)
endwhile

Yes, the entropy depends on the generation process. The study you link to has the answer for the (fixed) process used there:

  To overcome this [flaw in the original program], we generated the full list of eight-character pronounceable passwords without duplicates (≈ 1.2 billion) and assigned each password on this list with equal probability, resulting in 30.2 bits of entropy.

That is equivalent to five base 64 characters. I.e. you lose about 2.25 bits of entropy per character by making the password pronounceable, compared to using random base 64 passwords.

However, like the implementation they used, it is possible the algorithm is flawed and does not generate all possible pronounceable passwords with equal probability. In that case you lose even more entropy. So I would check the program carefully before relying on it.


linear cryptanalysis: how are the subkey bits removed from the linear approximation? I'm currently reading the tutorial on linear/differential crypta here: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf

End of page 14/Beginning of page 15: all the bits from the subkeys are summed up to a sum(k) variable. It is then written as 0 in the equation (5) and the probability stays the same.

I don't understand this step, why is the probability not changing if sum(k) is zero, and why is it 1-p if sum(k) is 1?

So after re-reading a few times it becomes clear. The key bits are static, so they won't change the probabilities.

Now suppose that $\sum_K = 0$, then the equation in (5) will be true, with probability $\frac{15}{32}$ since it is the same equation.

Suppose now that $\sum_K = 1$, the equation in (5) is now the inverse, and it will thus happen with probability $1-(15/32).$


What is the "purpose" byte in Crypto++ PBKDF2? Does anyone know the purpose of the "purpose" byte in the PBKDF2 implementation in Crypto++?  It appears that the PBKDF2 does not use this byte, but I want to make sure I am not setting the option to some stupid default.

Here is the method signature.

If you look at line 42 of the pwdbase.h file, it seems to indicate that this parameter is ignored by PBKDF2 implementation.

This seems to only be used in the PKCS12_PBKDF<T>::DeriveKey implementation.
According to the PKCS12 specification,

  The following procedure can be used to produce pseudo-random bits for a particular “purpose” which is identified by a byte, ID. The meaning of this ID byte will be discussed later.

The spec actually declares three values this ID byte can take, depending on the actual purpose of the key derivation.

It's not used for PBKDF2, and seems to only be present in its signature to have the DeriveKey method of PasswordBasedKeyDerivationFunction be usable for all subclasses here.


Decoding AES with Base64 cyphertext and key I have a supposed AES cyphertext and key.
They are both encoded in Base64 as they have trailing = for padding.

The key decodes down into 16 characters, so I am assuming its AES128.

I have tried to use the key and cyphertext to decode the message using
the website “aesencryption.net” and OpenSSL with the following command:

openssl enc -d -aes-128-ecb -base64 -in cypherText.txt -out /dev/stdout -pass pass:key

The online decoder gives me unreadable text, and OpenSSL produces a bad magic number. I have also tried a few of the other supported AES modes in OpenSSL with no luck.

Am I missing a crucial step?

Yes, it is AES. The ciphertext decrypts to

user: part4, password: 97531
{{{

PS: after some experiments I was able to decrypt it using the OpenSSL command line:

openssl enc -d -aes-128-ecb -in cipher.txt -out plain.txt -nopad -nosalt -K 10EABCFF45E05EBB7AF9A228DD31F216 -iv 0 -base64

I converted the key from base64 to hex first.


How to obtain a one-value share in Shamir's secret sharing This is a trivial question, but I had to ask:

since each generated share in a Shamir's secret sharing scheme initially consists of a pair of values (representing the coordinates of a point on the plane), how do I reduce the two values to one, so that the share that I eventually hand out will consist of only one value?

The way this is normally done is:

Share #1: (1, 65428)
Share #2: (2, 935747)
Share #3: (3, 3524)

But this does not seem very satisfactory to me, because the share still consists of two values, as the share's number (which could be seen as a metadata) is still one of two values. This way of doing is also inconvenient in the sense that if a share is marked as Share #7, this normally implies that there are at least 7 shares, possibly more.

The solution I am looking for is a way to have shares with totally random x values, such as

(324,4634634)
(23, 945)
(8, 45634)
(944, 356345)

and no serial number on a share (e.g. Share #8), so that by intercepting one share, and adversary cannot even try to guess how many shares there are.
Of course, the share generating mechanism is exactly the same. The only difference is that the x values, instead of being 1, 2, 3, 4… are random numbers.

So, now the question is: assuming I decide to use random x numbers, how can I conflate the two values of each share into one value, also assuming that no external (metadata) markings of the share (e.g. share #3) will be used?

Well, Shamir Secret Sharing is done using a field $GF(p^k)$, for some prime $p$ and some integer $k$.  A share consists of two integers $(x, y)$, where $0 \le x, y < p^k$.

So, the obvious way to express a single share $(x, y)$ as a single value would be to use the value $x p^k + y$ (using integer arithmetic, not field operations); each potential share would map to a distinct value, and during reconstruction, each value can easily be mapped by to the $(x, y)$ format.

Yes, this is just another way of doing concatination; you might find this somewhat more elegant.


Is it possible to add error propagation to OTP? What would be the recipe to add error propagation to a one time pad?
I.e. if I change a single letter in the clear text message, I want
the encrypted message to change starting from that letter and up to the
end of the encrypted message.

What you are actually looking for, which is a way to reuse a one-time pad, is not possible. For OTP reuse to be in any way secure, you need an algorithm with enough "complexity" to be a secure cipher (where the "pad" is actually a key).

For example, in the comments you raise the idea of including a random number and using the 8-bit CBC that Richie Frame and poncho mention. That would not work, because a known plaintext attack would reveal the pad, and the encryption of each byte would only depend on the encrypted value of the previous byte (known) and the pad at that point (recovered after a known plaintext attack).

For the title question the CBC idea is a valid answer, but it does not seem very useful. There is also a complementary question: is there a way to cause changes in the ciphertext to propagate through the plaintext. There e.g. the PCBC mode would work, but again I do not how useful that is.

As for actual suggestions, if you cannot handle the unique pad requirement of OTP (which is common), you should use a conventional cipher like AES. Preferably in authenticated encryption, so that error propagation does not need to be worried about.


Signatures: RSA compared to ECDSA I'm signing very small messages using RSA, and the signature and public key are added to every message, which requires a lot of space compared to the actual content.

I'm considering switching to ECDSA, would this require less space with the same level of encryption? And is the verification performance in the same range as RSA?

I'm considering switching to ECDSA, would this require less space with the same level of encryption?

The answer to that question is yes, both ECDSA signatures and public keys are much smaller than RSA signatures and public keys of similar security levels.  If you compare a 192-bit ECDSA curve compared to a 1k RSA key (which are roughly the same security level; the 192-bit ECDSA curve is probably a bit stronger); then the RSA signature and public key can be expressed in 128 bytes each (assuming that you'll willing to use a space-saving format for the public key, rather than using the standard PKCS format); the ECDSA signature would be 48 bytes, and the public key would be 25 bytes.

As you increase the required security level, the advantage tilts even more radically towards ECDSA; that's because you have to increase the RSA modulus size far faster than the ECDSA curve size to increase the security level.

  And is the verification performance in the same range as RSA?

Well, no, ECDSA signature verification is slower than RSA (for reasonable security levels).  That is the one place that RSA shines; you can verify RSA signatures rather faster than you can verify an ECDSA signature.  According to this web page, on their test environment, 2k RSA signature verification took 0.16msec, while 256-bit ECDSA signature verification took 8.53msec (see the page for the details on the platform they were testing it).  Now to be fair, this isn't quite an apples-to-apples comparison (256-bit ECDSA is probably a bit stronger than 2k RSA), but even if the difference isn't quite 50x, RSA is still faster.

I do have one question, though.  You mention that you are including the RSA public key along with the signed message.  Does that mean that the verifier uses that public key to verify the message?  If so, how do you know that someone who wants to forge a message won't just provide his own public key along with the signature (signed using his private key)?  That is, how does the receiver know that the public key he sees in the message is the one that was sent?


Discrete logarithms on elliptic curves In many examples of attacks on public key cryptography, examples of the form $a ^ x = b$ are used, but I can not understand the correlation between this and the multiplication of the generator point of the elliptic curve $Q = xP$.

I have already read a lot, but still I can not understand this. In the case $a ^ x = b$, this is one number, and for an elliptic curve it is a point with coordinates $(x, y)$. Please explain the difference simply, as you would to a child.

Well, to explain that, I have to touch lightly on what a group is, and how both operations involve a group.

A group [1] is a set of values, along with an operation (which I'll denote as $\odot$); with this operation, we take two values, smash them together, and generate a third one [2].  One example of a group are the numbers, along with the operation of addition $+$; we can take the values 1 and 3, and smash them together $1+3$ to get the value 4.

Now, one thing we can ask is 'if we start with a value $a$, how many $a$s do we need to smash together before we get the value we're looking for $b$'.  That is, if we compute:

$$\underbrace{a \odot a \odot a \odot … \odot a}_{\text{x times}}$$

how large does $x$ need to be before we get the value $b$?

This is called the discrete log problem.

With some groups, this is an easy problem.  For example, in the numbers and addition group I mentioned earlier, if we start with $7$, and ask "how many 7's do we need to add together before we get to 63, it's easy to see that the answer is 9.

Now, it turns out that both problems you mentioned are like this.

For the problem $a^x = b$, the $\odot$ operation is the act of taking two values, multiplying them together, and then taking the result modulo p (typically a large prime).  Because $a^x = \underbrace{a \times a \times a \times … \times a}_{\text{x times}}$, this is precisely the same form as the generic problem (and in fact is why we call the generic problem the 'discrete log' problem)

For Elliptic Curves and the problem $xP = Q$, the $\odot$ operation is taking two values where are 'elliptic curve points' [3], and performing an 'elliptic curve addition' to generate a third point.  That is, the problem is finding $x$ where $xP = \underbrace{P + P + P + … + P}_{\text{x times}}$ is the elliptic curve point $Q$; hence it is also in that same form.

Now, if the two problems are the same at the abstract level, why do we write them differently?  Well, it just comes down to notation.  For modular multiplication, we always write the operation as if it were multiplication, and so the obvious way to write a large number of multiplications is to write it as an exponentiation:

$$\underbrace{a \times a \times a \times … \times a}_{\text{x times}} = a^x$$

For Elliptic curves, we typically write the operation as if it were addition, and the obvious way to write a large number of additions is to write it as if we were doing a multiplication:

$$\underbrace{P + P + P + … + P}_{\text{x times}} = xP$$

This difference is just in the way we generally talk about these two grous - it has no impact on what we do with them.

[1]: That's a term that mathematicians use; don't worry, I would use that much more arcane terminology

[2]: Actually, there are a bunch of other things we require of a group - I will not mention them here.

[3]: I won't go into detail here about what an elliptic curve point is.


How does a padding oracle attack work? I am unsure of how a padding oracle attack works.

What I am not getting is how changing one bit at one time allows one to exploit(get keys) ASP.NET machines.

Can anyone explain this?

Definitions / Introduction

We define (this is solely for our example):

$enc()$ and $dec()$ as the encryption and decryption function using CBC mode, with a constant key. any block cipher will do
$\oplus$ is the XOR operation.
$n$ the amount of plain text blocks.
the length of a block in bytes is $16$ (i.e. 128 bit).
$m_1$ through $m_n$ the plain text blocks.
$c_0$ through $c_n$ the cipher text blocks, whereas
$c_0$ is the Initialization Vector (i.e. we have one more block here!).
for each block, a second index points to the byte, i.e. $m_{1,0}$ is the very first byte of our plain text.
$x_1$ through $x_n$ are the intermediate decryption values, after $dec()$ and before XOR.
the single equal sign $=$ is used for assignments, the double equal sign $==$ for comparisons.

To explain what $x$ means, here's the CBC decryption formula again. For each encrypted block $c_i$, we determine $m_i$ by:

$m_i$ = $x_{i} \oplus c_{i-1}$,(and the value $dec(c_0)$ is also named $x_0$)

For the very first block, we use the IV as follows:

$m_0$ = $dec(c_0) \oplus iv$

I recommend taking a quick glance at these images for decryption and encryption (It's not gonna hurt to read the whole Wikipedia Article too).

Scenario

For this attack we need a so called padding oracle, e.g. a web application.
This padding oracle accepts arbitrary cipher texts and gives different messages about whether the plain text is invalid or the decryption has failed.

Let's imagine this padding:

For all plain texts the last block is padded to a length of 16 bytes as follows, the end.\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x08.
If the last block is 15 bytes long, the padding is simply \x01.
If the last block is 16 bytes long, that is if the length of the message is a multiple of 16, then a block of 15 arbitrary values followed by \x10 is appended.
This means, the last block is always filled with zero to fifteen \xFF bytes up to the last one, which gives the length of our padding.

After decryption, one might now read the very last byte and cut off the given amount of bytes at the end. A value equals 0 and above 16 is invalid and returns a padding error.

We define the Oracle as follows:

$$
  O(c) = \left\{
  \begin{array}{l l}
    0 & \quad \text{if $c$ has a valid padding and }\\
      & \quad \text{decryption yields a well-formed plain text} \\
    1 & \quad \text{if the padding was valid, but the plain text}\\
      & \quad \text{was not well-formed (contained \xFF)} \\
    2 & \quad \text{if $c$ has an invalid padding}\\
  \end{array} \right.
$$

The web application expects plaintext as XML (or JSON or whatever) and will report a different error, when parsing fails. For our simplified scenario, let's just say there exists an evil character the plain text (after removing the padding) must not contain, e.g. \xFF

The attack

For this attack to work you need a valid ciphertext $c$, it is not required to know the correct plaintext value $m$.

We will start decrypting block by block, byte by byte. We start with the very first block and it's last byte.

Let's take the very first two cipher text blocks
$c_0c_1$, and send them to the oracle. Since $c_0$ is just the IV, the oracle  gets the first block (16 bytes) of plain text. Now, this depends on the value but it's pretty likely that the padding will be wrong, so you'll get a padding error.

Now by XORing the value $j$ from \x00 through \xFF to the very last byte of your $c_0c_1$ block you will get a total set of 256 different results. These results, let's call them $\tilde{C}_j$, make up cipher texts with the last byte in all possible values from \x00to \xFF - randomly distributed though.
Sending all of them to the oracle will yield 16 for which $O(\tilde{C}_j) < 2$. This means, that the last byte decrypted to valid bytes like \x01 through \x10. Of these 16 values for $j$, one must correspond to the plain text byte \x10. Bitwise comparison will help you notice, that they all have the very same fifth bit (counting from the right, where the rightmost is 1), except one. The exception results to the one that corresponds to 0x10. Let's memorize this $j$-value as $s$.

Whatever value $s$ has, we can XOR it with \x11, which will then result to the plain text \x01. We now have a block with a valid \x01 padding. (Oh, btw. $s \oplus j$ is the last plain text byte for $c_1$)

Now that we have a block with a valid \x01 padding, we have 15 more bytes to find.
We know that whenever we have an invalid byte \xFF in the plain text, the web application will stop and say so.
So for now, we can go through each byte and find the plain text as following:

  let $c$ be the current block and $p$ the plain text result
  for $i$ from 1 to 8 (each byte in the block):
  $\quad$ for $j$ from 0 to 255 (all ascii values):
  $\quad$ $\quad$ $\hat{c}_{i,j} = c_0c_1...(c_i \oplus j)...c_n$
  $\quad$ $\quad$ if $O(\hat{c}_{i,j}) == 1$:
  $\quad$ $\quad$ $\quad$ $p_i = j \oplus 0xFF$

Repeat this procedure with block pairs $c_1c_2$, $c_2c_3$, ...

Disclaimer

This is a simplified example and I tried to highlight all simplifications where made. I am by no means a crypto expert and my knowledge is limited. If you find any unmentioned simplifications or plain mistakes, please comment/edit :)
I can highly recommend reading a good explanation of the XML Encryption padding oracle in this blog. The paper about the attack is a pretty good read too: Breaking XML Encryption

TODO: This post is lacking a good explanation on why the CBC scheme is malleable and I wouldn't mind if there was a good graph to include.


Given a Message and Decryption Key, is it possible to find the Cipher in RSA? This is a slight reversal from the norm but...

Suppose Alice wants to ensure that everyone knows that a message will be from her. Instead of giving out the encryption key, she broadcasts the decryption key, and encrypts her messages privately. She doesn't care that anybody can read her messages, only that someone can't imitate her.

So if I want to imitate Alice, and all I have is a decryption key and the message, is it possible to fake a message from Alice?

Edit: so to clarify, we'll assume a literate message is valid. We'll also add the constraint that the attacker wants to mimic a specific Message (M), not just any message, or previous messages will do.

TL;DR: don't go here, it's a common mistake by starting cryptographers.

This is a reinvention of a signature scheme, as fgrieu mentions. If you want to integrate (part of) the message into the signature then you are talking about signature schemes giving (partial) message recovery.

The decryption key is the private key. It contains the modulus and private exponent, plus possibly all the CRT parameters and the public exponent. Now the public exponent doesn't need to be easy to guess, but it is if all the parameters or the exponent itself is given. Besides that, usually the public key exponent is set to a small prime number, which is easy to guess. Usually it is just 65537, the fourth prime of Fermat (F4). In other words, anybody who has the private key can generate the public key as well.

You can of course flip the public and private key and give out the public key instead. Even then there are problems with the scheme, take a look at my self answered question here - and note that I wrote this Q/A because many StackOverflow errors before.

And of course, just distributing the keys is not enough; the key of Alice must be trusted to be the key from Alice. Otherwise anybody can distribute keys instead of Alice. It may be tricky to find a scheme that protects public keys instead of private keys, if that is used.


Why are recomended RSA key lengths so high? I was checking for authoritative sources to back up my recommendation of a minimum RSA key length of 1024 and was shocked to find that NIST 800-56Br1 and FIPS 186-4 both recommend at least 2048 bits with 3072 bits for TOP SECRET data.  I found that other sources have similarly high recommendations based on expected lifetime of the key.

These recommendations seem excessive in light of what I can find about attacks against RSA encryption.  As far as I can find, the most recent attempt to factor RSA numbers was the successful factoring of the 756 bit RSA number.  That was in 2009 and required, roughly, two years of effort with 100 computers and a team of mathematicians.  Those researchers noted that their methods would not scale to significantly larger RSA numbers, so other [and unknown] methods would need to be developed.

Given that each additional bit doubles the number of values, 1024 bits would have $2^{256}$ times as many possible values.  Even given very sparse utilization of that immense field, the effort required to attack a 1024 bit RSA key appears very far outside the reach of current capabilities.

Have I missed some more recent attacks?  I note that some of the recommendations I have found predate the 2009 paper.  Why would cryptanalysts believe that 1024 bit RSA keys would be insufficient when no one had even attacked the 756 bit key, which is vastly easier than 1024?

Can anyone point me to cryptanalytic work that demonstrates the risk to 1024 bit RSA?

RSA, and to a somewhat similar extent Diffie-Hellman, bases its security on the difficulty of factoring large numbers into primes. While a scheme like AES can use all 2n numbers, in order to break RSA, you need to guess prime numbers.

As there are far fewer prime numbers and the factors can be better guessed, we need far larger prime numbers than other schemes like AES. So each additional bit doesn't double the difficulty of brute forcing it. If you want to venture into the math, you can check out the Wikipedia page on RSA.

While no one (we know of) has managed to break 1024, it is always important to stay ahead of the curve. And since brute force isn't exactly 2256 times more difficult,we pick higher primes. Who knows what future improvements in mathematics could break 1024-bit keys.


Is double hashing collision resistant? Double hashing can surely provide more security than only one layer of hashing but does that necessarily mean it is more collision resistant? This question in a more mathematical form: If $H$ is a collision resistant hash function, is $H\circ H\colon\;x\mapsto H(H(x))$ still collision resistant?

Yes. Let $H$ be a collision resistant hash function and assume that one can find a collision $(x,y)$ for $H\circ H$, that is, $x$ and $y$ with $x\neq y$ and $H(H(x))=H(H(y))$.
Consider the results $H(x)$ and $H(y)$ of applying $H$ once to both inputs. Then either

$H(x)=H(y)$, hence $(x,y)$ is a collision for $H$; or
$H(x)\neq H(y)$, hence $(H(x),H(y))$ is a collision for $H$.

Therefore, obtaining a collision for $H\circ H$ allows an attacker to derive a collision for $H$, showing the claim.

What could suffer is the output distribution of $H\circ H$ as opposed to $H$, that is, even if $H$ is uniformly distributed on the set of all bit strings $\{0,1\}^\ast$, the distribution of $H\circ H$ may be arbitrarily bad. For instance, when $H$ is not bijective on its image (which is the usual case), there are always hash values that are not in $H\circ H$'s image while others may have lots of preimages. However, this doesn't break collision resistance in the cryptographic sense, as outlined above.


How can a learnable function be obfuscable? I overheard in a lecture on cryptographic obfuscation that the learnable functions are obfuscable. But to me this seems so counter-intuitive.
Let's take a linear function (as an example of learnable function), then say I am given any obfuscated version of the function, I can always find the original function by querying an oracle having access to the original function- then how did I manage to obfuscate the original learnable function to begin with?

I am not sure what definition of obfuscation you care about, but in cryptography, we usually consider the virtual black-box obfuscation (VBBO) or indistinguishability obfuscation (IO). And as far as I can say, both definitions allow to extract learnable information from the obfuscated program (here learnable means learnable by querying the oracle having access to the original function). That is, the cryptographic obfuscation essentially does not hide anything about the learnable functions.
In other words, the cryptographic obfuscations do not rule out to learn something from the oracle access to the program. Instead, the cryptographic obfuscations do rule out the possibility to learn anything except the oracle access, or input-output behavior of the program. In particular, using the VBBO or IO, it is meaningless to obfuscate the learnable function with respect to security.
Let me briefly describe the (in-)formal definition of VBBO. A compiler $C$ that takes a program $P$ and outputs another program $C(P)$ is called VBBO if the following hold:
For any efficient algorithm $A$ that learns anything about $C(P)$, there is a simulator $S$ that learns exactly the same thing only via oracle access to $P$. More formally, it holds that
$$\Pr_{C,A} [A(C(P))\rightarrow 1] \approx \Pr_S[S^P ()\rightarrow 1].
$$
I omitted security parameters, negligible difference, etc. This definition does not prevent learning by querying the oracle having access to the original program.
Perhaps you are interested in this discussion.


Data Leakage and Data Switching I have two secret values $a$ and $b$ (i.e. they are arbitrary values). I mask them as follow:

$v_1=r_1a+r_2$

$v_2=r_1(b-a)$

where $r_1$ and $r_2$ are uniformly random values. I send $v_1$ and $v_2$ to a malicious server, and ask him to compute $v_1+v_2=r_1b+r_2$

Question: Given $v_1$ and $v_2$, can the server learn anything about $a$ and $b$?

Note: We know that if the server learns $r_1$ or $r_2$ it can figure out the values $a$ and $b$ too.

Edit: I consider modular operations, so they are done mod $p$ where $p$ is a large prime number. So $r_i$ is picked uniformly at random from the field $\mathbb{F}_p$

Given $v_1$ and $v_2$, can the server learn anything about $a$ and $b$?

Yes, they can (with high probability) determine whether $a = b$; if $v_2 = 0$, then either $r_1 = 0$ or $a = b$; given that $r_1 = 0$ occurs with probability $1/p$, the attacker can conclude that $a = b$.

Now, that's the only thing the attacker can learn; for any observed $v_1, v_2$, then for any $a, b$ pair with $a \ne b$, there is a unique $r_1, r_2$ pair that makes it work.  As $r_1, r_2$ are selected randomly and uniformly, the attacker gets no information on what the actual $a, b$ pair is.


Construction of R1CS vs QAP I have been following the medium post of Vitalik, where he shows step by step how to convert program --> Circuit --> R1CS --> QAP.
I am aware of the Pinocchio protocol, where they utilize the Groth13 QAP to generate proofs. I am also aware of Groth16, which improves QAP generation.
However, besides Vitalik's post, I haven't seen anyone in those papers talk anything regarding the R1CS constraints. Is this process somehow get done inside the QAP generation?
What am I missing?

In the original Pinocchio [GGPR13], the authors didn't use R1CS at all.
As a ZKP friendly computational representation, R1CS was proposed later that year in [BCGTV13] Appendix E. The reduction from an arithmetic circuit to R1CS is quite straightforward, which I guess is the reason why there's no dedicated papers introducing such a computation model.
Soon after its introduction, the BCGTV13 authors started to implement the system into libsnarks, and people started to realise that R1CS is quite easy to be arithmetized. (normally a SNARK is based on Linear IOP or a polynomial IOP that operates on polynomials, thus the efficiency of the arithmetization of R1CS or other representation into polynomials is important).
Ben-Sasson et.al has a pretty good empirical reason on why R1CS became a popular choice in his 2018 Aurora paper (Page 4):

We choose R1CS because it strikes an attractive balance: it generalizes circuits by allowing “native” field arithmetic and having no fan-in/fan-out restrictions, but it is simple enough that one can design efficient argument systems for it. Moreover, R1CS has demonstrated strong empirical value: it underlies real-world systems [Zca] and there are compilers that reduce program executions to it (see [WB15] and references therein). This has led to efforts to standardize R1CS formats across academia and industry [Zks].


How are RSA and ElGamal compatible in PGP? I'm starting to play with PGP and I don't understand how if your key pair is RSA

you can encrypt a message for someone whose key is for example ElGamal.

How does the asymmetric key exchange work if the crypstosystems are different?

When creating a signed and encrypted PGP message, you only use your own keypair in the signing phase -- it's not used when encrypting the message (that only uses the recipient's public key). The recipient uses their own keypair only to decrypt the message, not to verify the signature. The two keypairs don't interact at all; that's why they don't have to be the same algorithm.


Nonce role on stream ciphers Modern stream ciphers usually predicts the usage of a nonce (also termed as IV) in the cryptosystem. The cost of initializing the cipher with the nonce varies from algorithm to algorithm (for instance, this cost seems very high on HC-256 and negligible on Salsa 20). I would like to know the correct usage pattern of a nonce together with the stream cipher in a cryptosystem. The only thing I know for sure is that they must never repeat...

Does it needs to be new for every transmitted message?
It must be secret? (Is it assumed to be known by an attacker)?

Yes, no.

  Does it needs to be new for every transmitted message?

Yes, always, otherwise this qualifies as IV reuse, the keystream produced by the stream cipher is the same (since keystream is independent of plaintext) and you end up with the familiar $M_0 \oplus M_1$.

I think you answered your own question here by noting that IV's must never repeat.

  It must be secret? (Is it assumed to be known by an attacker)?

No, it can be made public and is generally transmitted along with the message. It is not a key. If it had to be kept secret, there wouldn't be much point in using one, as it would be equivalent to changing the key.

I should note this is a very common question here and will probably be closed as a duplicate:

Stream Cipher : Never use stream cipher key more than once
Why can't the IV be predictable when its said it doesn't need to be a secret?
Why is the IV passed in the clear when it can be easily encrypted?
What is the main difference between a key, an IV and a nonce?


chaining multiple key derivation functions together I was looking at PBKDF2, bcrypt and scrypt as options for key derivation; and would like to try using them all together in order to get the cryptographic strength of the strongest one (which seems to be scrypt so far unless something novel is discovered).
My first thought was to apply the first kdf to the password, then apply the second kdf to the obtained key (using it as the second password), and then the third. Is there something inherently wrong with this?

I saw a different approach posted by user perseids here:

http://www.unlimitednovelty.com/2012/03/dont-use-bcrypt.html

I quote:
"Derive p_1 = HMAC(Salt1+"PBKDF2") with key sha256(p), p_2 = HMAC(Salt2+"bcrypt") with key sha1(p) and p_3 = HMAC(Salt3+ "scrypt") with key sha1(p). Derive key k1, k2 and k3 by using the key derivation function PBKDF2, bcrypt and scrypt respectively, each of them using 1/30 seconds CPU time with input p_1, p_2 and p_3 respectively. Compute the key (or database reference entry) as sha256(k1+k2+k3). Here "+" designates the concatenation of byte arrays. "

So basically the 3 kdfs are applied in parallel, and the resulting keys are concatenated and then hashed together. What do you guys think about this one? Is this obviously superior to just applying the multiple kdf "in series"?

Also, what are considered the most reliable and well scrutinized C or C++ implementations of bcrypt and scrypt (I found pbkdf2 in crypto++ and botan).
Edit: I guess if they produce the right results, then they are reliable, so one point would be that they are well tested, but also what would be important is that they are implemented reasonably efficiently, so they don't give you a false sense of security (e.g. taking long time to compute, when in fact an attacker could take much less time to compute the same with a better algorithm, even without specialized hardware).

Yes, there's an issue: you're adding needless complexity, which gives you absolutely no benefit.

The whole point of a PBKDF is to be slow; passwords are low-entropy, and the only way to mitigate brute-force is to make it take time to compute hashes. It can't take too long to log in, so you have to balance "fast for a user" and "slow for an attacker." Attackers use hashes differently than users; an attacker will be trying many, many, many combinations, possibly on specialized hardware, while a user only tries one password at a time.

The trouble with combining hashes is that you only have a certain amount of time and resources you can give your hashing process. If you take 200ms for PBKDF2, 200ms for bcrypt, and 200ms and 16 MB for scrypt, your system takes 600ms to compute a hash. Suppose that PBKDF2 hardware implementations are \$1.00 per 100 threads of PBKDF2; bcrypt ones are \$50.00 per 100 threads of bcrypt; scrypt ones are \$100 per 100 threads of scrypt (these numbers are wholly made up). Then an attacker can attack 300 hashes at once for a cost of \$151; this will check a new hash every 2ms on average. If you just used scrypt with 600ms and 16 MB required, then an attacker would need 300 scrypt threads to get that throughput; this is \$300.

Basically, the issue with combining them is that you're shifting hash time from a stronger algorithm (where it's expensive for the attacker to do things faster than you) into a weaker algorithm (where it's cheap for the attacker to do things faster you).


Does there exist a proof-of-retrievability scheme that is publicly-verifiable, limited-use, and does not use homomorphic encryption? I find myself wanting to test out a practical implementation of a proof-of-retrievability scheme, simply out of curiosity. These schemes seem to be divided into two variations, publicly-verified and privately-verified. Here's a brief explanation of the problem:

Private:

  Alice sends a very large file to Bob.

  Bob agrees to store the file for Alice in exchange for $5 per month.

  Alice is suspicious of Bob's intentions, and suspects that Bob could delete all or part of the file and fool her into paying $5 per month, without Bob holding up his end of the agreement. Therefore, Alice wants to conduct periodic random audits to verify that Bob is in fact storing all of the file, as agreed upon.

  Alice could download the entire file from Bob, and then verify the hash of the file against one that was recorded earlier. However this would waste a lot of bandwidth, and also take a lot of time, since the file is very large.

  Instead, Alice would like a more efficient interactive audit protocol, in which she chooses a random subset of the contents of the file, and Bob must be able to correctly respond with an answer that is based off of those parts of the file. Since Bob doesn't know which parts of the file will be needed in the future to pass the audit, Bob is forced to store the entire file, or he will fail the next audit. Since Bob is storing the entire file, it is reasonable to say that Bob is holding up his end of the agreement.

Public:

  Same as the above, except we have a third party, Carol, who also wants to audit Bob to verify that he is storing Alice's file. Carol might have more limited information about the file, for example, Carol might never have actually seen Alice's file. However Carol still needs to be able to perform the audit.

I have looked at two papers on this subject (see below) and it seems like a simple but inefficient privately-verifiable scheme is possible using MACs. More efficient schemes seem to use complicated "homomorphic linear authenticators" and fountain codes. It also seems like these more advanced schemes allow an unlimited number of challenge-response verifications to be performed in the future.

Unfortunately my understanding of this subject is limited, so my goal is to piece together a working implementation of a simple scheme that does not require advanced knowledge of cryptography. That said, I am most interested in the public verification aspect of proof-of-retrievability schemes, and it seems like the simple scheme using MACs is only privately verifiable. It also seems like there is a trade-off between the algorithm's efficiency and complexity.

So my question is, if we relax the requirement of being able to perform an unbounded number of verifications, and we also relax the requirement of using resources efficiently, is it still possible to produce a proof-of-retrievability scheme which is both publicly-verifiable and simple in construction?

Any additional information about this would also be appreciated.

"Proofs of Storage from Homomorphic Identication Protocols" (Ateniese et al)
"Compact Proofs of Retrievability" (Shacham and Waters)

I do not know of any approaches in context of proofs or retrievability (PoRs)/provable data possession (PDP) that use homomorphic encryption. However, many of those schemes employ homomorphic (linear) authenticators/tags for the metadata such that the proofs delivered by the server can be of constant size, i.e., by aggregating single tags.

Now to some misunderstanding regarding the type of verifiability:

Public verifiability in this context means that the data owner who initially outsources the file is the only entity that can modify the data, but a third party, which is given some public information, can only verify a proof from the server that the data is available, i.e., check that the data is still available/retrievable.

Consequently, public verifiability always involves some secret that is only known to the data holder (who creates the file and metadata and may modify the stored data and the corresponding tags) and some public information (corresponding to that secret) that can be given to some third party such that it can trigger proofs for availability of the data (but cannot modify/replace the data). Thus, the party in possession of the public information can only check if data is available, but can not modify already stored data in such a way that a proof after modification of the data will still succeed.

As a consequence, MAC based PoRs/PDP schemes, which are essentially the same but have different security models, can never achieve public verifiability as it is defined in this setting, as it would require to share the respective secret (and this allow modifications). The same holds for any secret key only scheme.

Clearly, the use of a privately or publicly verifiable scheme to allow another third entity (distinct form the data holder) to request and verify proofs from the server depend on your trust model. Public verifiability assumes that the third entity is semi trusted, i.e., only trusted to conduct the proofs honestly, but you do not trust the third party that it wont modify the stored data. If you fully trust the third party, i.e., you are sure that it will not modify your data unauthorized, you can also use a privately verifiable scheme and simply give away your secret to the third party. However, this is a quite strong assumption.

Typically, such PoR/PDP schemes are either private verifiable or public verifiable. But there are also protocols which achieve unbounded private and public verifiability at a quite low cost simultaneously (based on the same metadata/tags). You may look here for such a scheme. However, it is based on pairing friendly elliptic curves and may not be that straightforward to understand as you say your knowledge is quite limited.

A very simple and easy to understand privately verifiable but bounded use scheme is presented here, but it does not support public verifiability as discussed above. Nevertheless, it is easy to implement and may be sufficient for your purpose.


Is there any restriction in using lossless compression algorithms for huge key sizes? I'm studying McEliece and Multivariate Public Key cryptographic systems. The main problem here is the huge key size.

Is there any restriction in using lossless compression algorithms to fix this problem?

The problem is that the key is essentially random data and thus cannot be meaningfully compressed. Several variations of the McEliece cryptosystem have tried modifying it to produce public keys with special structure which are compressable. However, all such systems have been broken (as far as I know), and it seems that in most cases, adding special structure like that makes it more vulnerable to attack.


Is it possible to fake any file's SHA256 checksum with Length extension attack? Is SHA256 completely insecure when file size is not also checked? Can fake SHA256 checksum be created trivially for any file by attacker after padding some data after original file i.e. using length extension attack?
E.g:

Alice creates fake linux installation ISO file using length extension attack by padding extra data after ISO and calculates fake
SHA256 checksum of the ISO

Bob downloads Alice's fake ISO file and calculates the SHA256 of the ISO

Bob compares the SHA256 checksum that he generated from fake ISO file to the checksum found on official linux distribution's home page. Because Bob's fake ISO checksum matches the official ISO checksum, Bob
doesn't notice that he has downloaded fake ISO

If Bob had compared the fake ISO file size to the original ISO file size found on official linux distribution's home page in addition to calculating the checksum, he
would have noticed that he has fake ISO not the original

Is this trivial to do?
In other words, is SHA256 completely insecure when a file's file size is not manually checked by computer user?
Does the file size always need to be checked when using SHA256?

Bob compares the SHA256 checksum that he generated from fake ISO file to the checksum found on official linux distribution's home page. Because Bob's fake ISO checksum matches the official ISO checksum, Bob doesn't notice that he has downloaded fake ISO

I highlighted the incorrect assumption: the checksums wouldn't match.
What the length extension attack allows someone to do is, given the hash of an unknown message $M$, compute the hash of a message $M | pad | X$ (for a specific string $pad$ which depends on the length of $M$, and an arbitrary string $X$).
However, the hash of $M | pad | X$ will not (in general, that is, barring an extremely improbable coincidence) be the same as the hash of $M$.
If it were, that would count as a hash collision, hence disproving the collision resistance of SHA256.

Is this trivial to do?

It is believed to be infeasible  to make the hashes match.  Yes, the adversary could compute the hash of $Y = M | pad | X$, however because he knows what his image $Y$ is, he could compute its hash without any special properties of the hash function.


Is super encryption (aka “multiple encryption”) always good? I'm trying to use super encryption (also known as “multiple encryption”) with AES in CFB mode with IV and password salting and AES in CTR mode both without padding. I first use AES CFB and then AES in CTR mode. Will my approach compromise security in any way, or is it efficient (in terms of resource consumption, security, and speed) compared to using either one of the modes?

Since you are deriving the key from a password, there is generally not a security advantage to using multiple encryption in the way you described. The entropy of key material generated is less than the maximum security provided by AES, which means an attack on the password will be more effective than a generic key recovery attack on the cipher.

A devastating attack on AES will break the entire system since you are only using a single cipher. The general reasoning for using multiple encryption is that if a single cipher algorithm falls, the system does not. This means you need to use different ciphers, such as AES and Twofish.

In terms of efficiency, any multiple encryption system will be less efficient than a single cipher mode. In your case, you loose the ability to have one of your AES instances available as an in-register cipher with hardware acceleration on a single core, since there is not enough register space to hold the round keys from both instances. If you have multiple cores available this is not a problem, since the CTR stream can be generated in advance of the plaintext, but with CFB it cannot. Spreading across 2 cores using different modes will probably slow it down to less than 50% because of memory access latencies involved when combining the instances. You could keep everything on one core and hop between instances; generate chunk of CTR stream and store, then switch to CFB and use CTR stream while processing plaintext, then repeat as needed. Performing a single mode at a time on the entire plaintext will use the least processor resources, but the most memory, unless you are first writing all intermediate ciphertext to disk.

Depending on implementation, this system may be more vulnerable to a multitude of attacks. Dual AES instances use double the round subkeys, which may need to be stored in RAM rather than CPU register space. This may leave them vulnerable to skimming or cold boot recovery.

There is also more than 1 way to do this. You can perform CFB on all plaintext, then add the CTR stream. Or you can add the CTR stream to the CFB ciphertext block before it is fed back. In the 2nd way, this is equivalent to adding the CTR stream to the plaintext before CFB mode, since both use XOR. You also did not describe any type of authentication scheme, which is extremely important since neither mode is authenticated, especially in the case of stream type ciphers which are vulnerable to bit-flipping.


Is there a standard format for compact 56-bit DES keys? DES keys are traditionally stored as 8-byte blobs, with only the high 7 bits of each byte being meaningful to the algorithm; the low bit of each byte is set so that the population count of the byte is odd.  This makes DES have a key size of 56 bits, rather than 64 bits.

Is there a standard format for storing a 56-bit representation of a DES key?  I was going to store them that way because it means random keys have all their bits used.

For now, I'm just concatenating the 7 bit chunks together, left to right (big-endian sense).

This is for interfacing with a legacy system that uses 3DES; thus, the parity-less format would have 168 bits = 21 bytes.

The one time I've seen a system compress a DES key into 7 bytes, it did it by logically placing the 8 bytes of the standard DES key into an 8x8 table, and then flipping the table along the diagonal axis, so that bit x of byte y of the standard DES key was mapped to bit 7-y of byte 7-x of the compressed key. For example, the first byte of the compressed key consisted of the msbits of all 8 bytes, and the second byte of the compressed key consisted of bit 6 of all 8 bytes, etc.  This moved all the lsbits of each byte into the last byte, which was discarded.

However, I don't believe this was, in any way, standard; it just happened to be what the system I saw did.  This particular transform does have the advantage that the same routine can convert both directions between the standard DES format and the compressed format (that has all the ignored bits in the last byte).


Is solving $m^3 = k*n + c$ hard? Given the equation
$$m^3 = k\cdot n + c$$
I know $n$ and $c$, and I need to find $k$, so that $m$ is a natural number. $n$ and $c$ are large numbers, so i can't use bruteforce.

How can you find a solution?

Your problem is equivalent to solving $m^3 \equiv c \pmod n$. This corresponds to breaking RSA for $e=3$. We know no efficient way for doing that without factoring $n$.

If you know the factors of $n$ you can compute the private exponent $d$ as $e \cdot d \equiv 1 \pmod{\varphi(n)}$ using the extended euclidean algorithm and then compute $m$ as $c^d$.


Is it safe to use PBEWithMD5AndDES? I'm encrypting some of my (not so much important) files with PBEWithMD5AndDES. Is it a strong method or it can be de-crypt easily without knowing my selected password?

I'm new to crypto, thanks in advance.

Yes, it can be decrypted easily because it will use DES (CBC) mode of operation. DES only has an effective key size of 56 bits. So the key and the can be brute forced regardless of the (PBKDF1) key derivation.

MD5, while considered broken by itself, is less of an issue when it is used within PBKDF1 - as long as the password contains enough entropy of course.

If possible you should upgrade to Password Based Encryption (PBE) using PBKDF2 and AES. Beware that PBE usually uses CBC mode encryption, so it is not suitable for transport protocols.


Why can't we use the first block of AES-CBC as MAC As per topic, why can't we use the first block as MAC instead of using the last block? what's the rationale?

The MAC value should be calculated over all of the input, not just the first block. The chaining of CBC makes sure that the bits in the last block of ciphertext depends on all the previous blocks.


Is there any advantage using this kind of ROM-based randomized hashing in digital signatures? The said randomized hasing is actually a sort of padding, and it goes like this:
Parameters:
1. hash function H()
2. length N in bytes of the output of the hash function.
Input:
1. M the message to hash.
Generate:
1. Generate r := N/2 random bytes.
2. Compute lo := H(r|M)
3. Compute hi := r xor lo
4. _Return (hi|lo)
Verify:
1. Compute r := hi xor lo
2. Compute v := H(r|M)
3. _Return v == lo

Is there any advantage to it other than slightly better verification of the correctness of the padding?

You are essentially describing a salted hash which is very important for some post-quantum signature schemes. In some lattice-based schemes it is important that the same signing key never be used with the same hash so that some message-replay defence is required. Schemes such as FALCON achieve the anti-replay by salting the message before hashing. Your method is one way in which this could be achieved.


Locker room birthday paradox The local YMCA has new locker rooms with built-in 3-digit combination locks. If I understand the Birthday Paradox correctly, I have a better than 50% chance of finding a lock combination with 33 tries on a given lock. (The lock combination gets set by the member at the time of locking the locker door.)

Is my analysis correct?

No, that is not correct.  Assuming that the lock combinations are assigned randomly, and you have no apriori knowledge of the combination, you need 500 tries before you get a 50% chance of success.

What the birthday paradox means is that if you have 38 locks (not 33, and assuming that the combinations were assigned randomly and independently), there is a better than 50% chance there are two locks with the same combination.  This doesn't help you with finding the combination of any particular lock.