What criteria make the theta step of Keccak's round function reversible? From what I've been reading, Keccak's round function is reversible. That's pretty obvious for the $\rho$, $\pi$ and $\iota$ transforms. For $\chi$ to be reversible, $x$'s range has to be odd — but that's alright since Keccak's $x$ has a range of 5. Yet, what criteria make the theta step reversible?

Checking some small $x$, $y$ and $z$ ranges, it shows that:

where [x][y][z]'s ranges are [3][3][2], $\theta$ is not reversible, and
where [x][y][z]'s ranges are [3][3][3], $\theta$  is not reversible either.

So, what makes the $\theta$ for (eg) [5][5][64] reversible?

I went through it, and while this isn't a complete answer, which should shed some light (and note: when I'm talking about $x$, $y$ and $z$, I'm referring to the ranges those indicies can take on; not any specific index)

First rule: if $x$ is even, then $\theta$ is invertible.  The proof of that is actually fairly elegant; however it's also rather irrelevant to Keccak (because even if you were going to tweak Keccak, the $\chi$ step requires $x$ to be odd).

Now, from here on down, we'll assume $x$ is odd.

Here is how it works; there is a function $L(y)$ that maps the range of $y$ into a set of integers; $\theta$ with the parameters $(x, y, z)$ is invertible iff $z$ is not a multiple of any of the integers within the set $L(y)$

$L(y)$ also has the property that $L(a) \cup L(b) \subset L(ab)$

Here is the list of $L(y)$ for $y<38$:

$L(2^n) = \emptyset$

That is, if $y$ is a power of 2, $\theta$ is always invertible

$L(3n) = \{ 1 \}$

What that means is that, since all values of $z$ are multiples of 1, then $\theta$ is never invertible if $y$ is a multiple of 3.

$L(5) = \{ 15 \}$

In the Keccak case, the actual value of $z = 64$ is not a multiple of 15, and hence $\theta$ is invertible.

$L(7) = \{ 7 \}$

$L(10) = \{ 15 \}$

$L(11) = \{ 341 \}$

$L(13) = \{ 819 \}$

$L(14) = \{ 7 \}$

$L(17) = \{ 85 \}$

$L(19) = \{ 9709 \}$

$L(20) = \{ 15 \}$

$L(22) = \{ 341 \}$

$L(23) = \{ 2047 \}$

$L(25) = \{ 15 \}$

$L(26) = \{ 819 \}$

$L(28) = \{ 7 \}$

$L(29) = \{ 475107 \}$

$L(31) = \{ 31 \}$

$L(34) = \{ 85 \}$

$L(35) = \{ 7, 15 \}$

$L(37) = \{ 3233097 \}$

Now, there are certain obvious regularities with above listed $L$ function values; for example, if $y$ is prime other than 2, then every $L(y)$ listed consists of a single element which is a divisor of $2^{y-1}-1$; and in every case listed, we have $L(ab) = L(a) \cup L(b)$; however I cannot prove either of those observations hold in general.


Is there a way to bound linear complexity of a sequence less than its period Linear complexity of a sequence $s_0,s_1,\ldots$ over a finite field is the shortest length $n$ of linear recurrence of the sequence such that
$s_{n+j}=\sum_{i=0}^{n-1}a_is_{i+j}$ for $j=0,1,2,\ldots$
for constants $a_i$ in the field. My question is at which $n$ should we stop computing $a_i$? Assuming the sequence is periodic with period $N$ at which $n$ should we stop the search for the coefficients in the recurrence relation above so that the relation will be valid for all subsequent longer sequences until the full period?
The definition doesn't seem to give any clear idea of the computation of linear complexity. Even the Berlekamp Massey algorithm doesn't say at what $n$ less than $N$ to stop.

My question is at which $n$ should we stop computing $a_i$? Assuming the sequence is periodic with period $N$ at which n should we stop the search for the coefficients in the recurrence relation above so that the relation will be valid for all subsequent longer sequences until the full period?

If the sequence is periodic then the linear complexity of the sequence will not change after some point. Remember, an LFSR with length $L$ can produce a periodic sequence at most length $2^L-1$ if the minimal polynomial is maximal.
But the Berlakamp-Massay algorithm cannot detect the period, it must process all inputs. It works interactively such that it updates the internals if a new bit cannot match the output, i.e. there is a discrepancy. Once the period is reached it will not update the internals but the algorithm can only be modified to output the last modified internal distance.
If you know the period, you can stop the Berlakamp-Massay after processing $N$ bits. The reason can be seen as in the next extreme example. Consider the periodic sequence where in the period it has 99-zero followed by 1.
$$\overbrace{\underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}}^{\text{ the preiod}}\, \underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}\cdots  \underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}\cdots$$
The linear complexity of this sequence is 100. Therefore you have to process all of the period to find the linear complexity of the sequence.

The definition doesn't seem to give any clear idea of computation of linear complexity. Even the Berlekamp Massey algorithm doesn't say at what $n$ less than $N$ to stop

Because it is designed to produce the LFSR that produces the given sequence, nothing more. As said before it must process all of the inputs.
If you want to find the period use period finding algorithm like Z-algorithm


Apple encrypted DMG volumes strength? Apple OS X can create encrypted AES 128/256 DMG volumes. Here is written about a men who was able to hack it. And also that DMGs use PBKDF2-HMAC-SHA-1. I couldn't find more information about encrypted DMGs. So does that mean that apples encrypted DMGs could be hacked?

I would have posted this as a comment if I could:
Please re-read the entire article that you have linked to.
All that was done was a brute force attack.

The reason brute force was possible was because the missing password was narrowed down to "about 22472" different possibilities.
And that 22000 was tried by a computer dedicated to doing such calculations.

This shows nothing about the security of the encryption scheme, only that when you know almost all of a password and have the means to try all possibilities efficiently, you can brute force it successfully.


Security Level Estimate when Cascading/Compositing Ciphers? Way back when, DES had a theoretical security level 56-bits. 2-key TDEA provides about 80-bits of security, and 3-key TDEA provides about 112-bits of security. Obviously, those security levels are not linear in the cascading of the underlying block cipher.

First question

How does one estimate the increase in security level when compositing?

Second question

Is it necessary that the composition is not closed so that the composite does not form a group? I.e, if A(B(C(x))) = y, then there cannot be a A' such that A'(x) = y. (I believe so).

Third question

How does this apply to Diffie-Hellman over integers? If I run the Diffie-Hellman algorithm twice with 3072 moduli (i.e., 128-bits of security each) and concatenate the two shared secrets, then how many effective bits of security are present? (Intuitively, I think its around 128-bits or 129-bits).

Fourth question

How does this apply to RSA? If I run the RSA algorithm twice with 3072 moduli (i.e., 128-bits of security each) and transport two shared secrets, then how many effective bits of security are present? (Intuitively, I think its around 128-bits or 129-bits).

Sorry to ask these questions. The back story has to do with elliptic curves and patents, and I'm trying to figure out if its feasible to exchange/agree/transport an AES-256 key in distinct pieces using traditional crypto primitives while maintaining security levels and avoiding elliptic curves.

First question

It depends upon the scheme.  It also depends upon what kind of composition you are talking about.  Triple-DES uses multiple encryption.  That's one kind of composition.  The approaches you talk about in your third and fourth questions are a different sort of composition.  They will have different security properties.

Second question

Yes.  If the operation forms a group, then using multiple encryption does not add security.

Third question

This provides only 128-129 bits of security, but not for the reasons you expected.  The reason is Diffie-Hellman with a 3072 bit modulus provides only about 128 bits of security; one can break Diffie-Hellman with a 3072 bit modulus using something like $2^{128}$ work (very roughly).  So, one can break two Diffie-Hellman exchanges using $2^{129}$ work (very roughly).  In other words, this does not add security.

This is not a practical weakness in practice, because in practice 128 bits of security is more than enough; no one is going to be able to perform a computation that requires $2^{128}$ work (not in my lifetime).  That said, this is a certificational weakness in the protocol, and no one would consider this to be good protocol design; it is rather crummy protocol design.

Fourth question

Same answer.

Final note

This is kind of silly.  Why don't you tell us the real problem you really have?  It sounds like your question is heading in the direction of crummy protocol designs.  Maybe if you tell us the real problem, we can help you find a better solution to the problem.


Is there any use for PBKDF with empty password? As the name suggests, password based key derivation functions are used for deriving a cryptographic key from, well, a password.

Is there any use for PBKDFs with empty password? Does it give any advantage over simple hash or HMAC? More specifically, in the case of PBKDF2-HMAC it would mean applying HMAC with an empty key, simplifying it to a double hash.

For example, according to its documentation, OpenSSL allows calling PKCS5_PBKDF2_HMAC() with no password given, but RFC 6070 does not define test vectors for empty passwords (which IMHO would be an important edge case for test vectors).

While it might be possible to use an empty password, the reason for that is most likely that any exclusion would also be known to the attacker.

However, I wouldn't call it an important test case. A PBKDF does not protect from choosing bad passwords, it only makes the dictionary attack take a lot more computational effort. If one of the first guesses is correct already, no password-based KDF will protect against that. And if the empty password is allowed, it surely is quite high in that list.

Alternatively, they could have just overlooked that case. Or they decided against it. Only the authors might be able to answer your question with certainty.


Is it possible to build short proofs of arbitrary computations over a big list? With the use of Merkle Trees, you can prove the presence of an element of a very big list, with an amount of information logarithmic in the size of the whole tree. Merkle proofs, thus, probabilistically confirm the result of this specific fold:

isMember :: ∀ t . List t -> Bool
isMember e = foldr (\ h t -> h == e || t) False

My question is if the same result can be extended to arbitrary folds; or, in other words, is it possible to prove arbitrary computations about a big list using some clever trick similar to Merkle Trees?

Specifically, I want to store a huge dataset (>20 GB) on several computers, and then I want any of those nodes to make arbitrary claims about that dataset (like: the max element is 198500461354!), in such a way that other nodes can verify that claim is true without having to run max over the whole dataset themselves.

Merkle aggregation can help you compute aggregation functions over the leaf data in a Merkle tree.

The technique is described in detail in Crosby & Wallach's paper on history trees [1], an append-only Merkle tree. Merkle aggregation can be used to provably compute things like $\max(\cdot,\cdot)$ functions over all leafs.

The idea is quite straightforward.
Each node can have an attribute and there's an aggregator function $\alpha(l, r)$ which takes the attributes from the two children and returns the parent's attribute. For example, the aggregator function can be $\max(\cdot,\cdot)$.

By recursively applying $\alpha(\cdot,\cdot)$ starting with the leafs, attributes can be computed or aggregated for all nodes in the tree, all the way up to the root. Furthermore, the computed attributes are hashed in the Merkle tree. Specifically, a node's hash is no longer just $H(h_l, h_r)$ but $H(h_l, a, h_r)$, where $h_l,h_r$ denote the left and right child hashes and $a$ denotes the aggregated attribute computed via $\alpha(l,r)$.

Including the attributes in the Merkle hashing enables a prover to convince a verifier that the aggregation was performed correctly. Of course, the Merkle proof is a bit different now. Specifically, a Merkle path from a leaf to the root consists not just of the hashes along the sibling path, but also of the attributes along the path and the sibling path, so as to verify the aggregation.

Hope this helps!

References

[1] "Efficient Data Structures for Tamper-Evident Logging", by Scott A. Crosby, and Dan S. Wallach


CBC Padding Oracle in SSL3. Why only in SSL3 not in TLS1,TLS1.1, etc I read about PODDLE attack which downgrades the TLS version to SSL 3.0 to exploit CBC padding oracle attack. I looked at the specs for TLS 1.1

And found CBC is still used in its ciphersuites. Why is POODLE needs to downgrade to SSL 3? Can't the POODLE attack works by downgrading to TLS 1 or TLS 1.1? Is the CBC implementation in SSL 3 different than that in TLS 1 and TLS 1.1?

Essentially the reason is that in SSL3 the padding was not specified which was corrected in the specification of TLS. Here is a detailed and readable explanation of the attack.

However, there is a variant of the poodle attack that also works on TLS because the same procedure as for SSL3 could be used on TLS packets. While this was not standard-compliant it would work and some implementations are vulnerable.


Determining susceptibility to frequency analysis I'm looking to create some tokens using a keyed hash mechanism to represent our individual customers.  I was planning on using combinations of the customer's personal information (e.g. H(Firstname,Surname,DOB)) in the token to prevent frequency analysis, but is there some way I can quantify this?

For example, qualitatively I assume that using:

H(Firstname,Surname,DOB,FirstPurchaseDate)

will be more secure than using just:

H(Firstname)

as the latter will render some values of the first name identifiable by frequency analysis given a large enough sample (I will have to open source the protocol for this, so I'm assuming that attacker knows which variables the tokens consist of).  I would like know what combinations of variables will render frequency analysis impractical - are there any established techniques for this?

Whatever parameters you pass in will affect the resulting hashes.  If you compute only H(Firstname), then two users with the same first name will lead to the same hash even if they have different surnames.

P.S.  Consider letting users simply have a name so that you respect the vast populations of people out there whose names do not conform to the anglophone forename/surname model of names, or other problematic oversimplifications.


What use is the signature without the message under RSA? Using RSA for signing & verification, is there a way to take a valid signature for an unknown message, and for someone else to generate a valid signature using a different key against the valid signature, given knowledge of the original public key?

First, let me describe how I understand signing/verification with RSA:

You start with a keypair with modulous $N$ that is the product of two large primes, along with integers $e$ and $d$ such that $e d ≡ 1 \pmod {\varphi(N)}$, where $\varphi$ is the Euler phi-function. The signer's public key consists of $N$ and $e$, and the signer's secret key contains $d$.

To sign something, the signer computes $\sigma ≡ m^d \pmod {N}$. To verify, the receiver checks that $\sigma^e ≡ m \pmod N$.

( http://en.wikipedia.org/wiki/Digital_signature#How_they_work )

What are the risks to making $\sigma$ public, if $m$ is kept secret, along with the signers private key, $d$?

The public key, $N$ and $e$, is public, as is $\sigma$, the signature.

$\sigma^e$ is easily calculatable, which gets us $m \pmod N$, but not $m$ itself.

Given $m \pmod N$ but an unknown $m$, what can we do with it?

Can a second signer, with public key $N^{\prime}$ and $e^{\prime}$, and private key $d^{\prime}$ be used to generate $\sigma^{\prime} = m^{d^{\prime}} \pmod {N^{\prime}}$?

How resistant to brute forcing is that? How about if some sort of verification oracle is available?

Since $m \pmod N$ is lossy, without $m$ (or more likely $\text{pad}(\text{hash}(m))$ in practice), is anything about $m$ recoverable?

Is there another system for signing whose signatures are of less use without the message?

Caution: the question assumes that the message $m$ can be larger than the public modulus $N$ and sent separately from the signature (perhaps, encrypted), contrary to textbook RSA as in the original article. The answer makes that assumption unless otherwise specified.

If we signed a secret message $m$ by publishing its signature $σ$ computed as $m^d\bmod N$, at least two very bad things would happen:

The message would not be so secret anymore
That's because anyone knows the public key $(N,e)$, and thus from $σ$ can compute $σ^e\bmod N$, which is $m\bmod N$. This reveals a lot of information about $m$, which goes straight against the requirement to keep $m$ secret. In modern cryptography, the adversary succeeds if she learns anything about a secret message (except its length), and $m\bmod N$ qualifies. For example:

$m\bmod N$ allows (with overwhelming odds) to recognize $m$ among a moderate list of arbitrary messages.
If $m$ is shorter than $N$ then $m\bmod N$ is $m$ and thus $m$ is no longer secret at all (this occurs when $m$ is less than $256$ bytes for $2048$-bit $N$, a common size).
If (as in the question) it is computed and published the signature $σ'$ of the same $m$ according to a different RSA key $(N',e')$, then this reveals $m\bmod N'$. By the Chineese Remainder Theorem we can efficiently compute $m\bmod(N\;N')$, and this reveals $m$ if it's size is less than the sum of the size of $N$ and $N'$, extending the above to longer messages than was possible with a single signature.
If $m$ is known except for a segment shorter than $N$ (that is $m=m_0\mathbin\|m_1\mathbin\|m_2$ with $m_0$ and $m_2$ known, and $m_1$ shorter than $N$), from $m\bmod N$ it is easy to find $m_1$, thus $m$, as follows: if $|m_i|$ is the number of bits in each segment of $m$, we have $m\bmod N=\big((m_0 2^{|m_1|}+m_1)2^{|m_2|}+m_2\big)\bmod N$ thus $m_1=\big((m\bmod N)-m_0 2^{|m_1|+|m_2|}-m_2\big)2^{-|m_1|}\bmod N$ where $2^{-|m_1|}$ is the multiplicative inverse of $2^{|m_1|}$ modulo $N$, which is easily computed using the Extended Euclidian algorithm.

It would be easy to make forgeries
In particular, it would be possible to forge a large class of messages, including C strings showing as anything desired. For any $m_0$, $N$ and $e$, it is easy to exhibit $m_1$ such that $m=m_0\mathbin\|m_1$ verifies $\sigma^e \equiv m \pmod N$. Just choose $m_0$ ending with a terminating 0x00 bytes, decide a size $b$ of $m_1$ with $b$ multiple of 8 and $2^b>N$, pick any $\sigma$, compute $m\gets m_0\,2^b+((\sigma^e-m_0\,2^b)\bmod N)$ ).

Note: in common textbook RSA, $m$ is not sent separately and is recovered as $m\gets\sigma^e\bmod N$, hence $0\le m<N$. This makes the attack more difficult. However for small $e$, and when $|m_0|$ is small enough (roughly up to $\log_2(N/e)/e$ bit including terminating 0x00), we find $b\gets8\,\lfloor \log_2(N/(m_0+1))/8\rfloor$, compute $σ\gets\left\lceil\sqrt[e]{m_0\,2^b}\right\rceil$ and $m\gets σ^e$. This $σ$ verifies as the signature for this $m$, and prints the same as $m_0$.

Rather, good and common practice in order to RSA-sign a confidential message is to:

Encrypt and sign (or sign and encrypt)
Encipher the message (typically using a symmetric algorithm such as AES in CTR mode with random IV), then RSA-sign the cryptogram (ciphertext, rather than the plaintext), e.g. as in 2 below; or transform the message into a signed message (again e.g. as in 2 below), then encipher that whole signed message.Note: if possible, use encrypt-then-sign. If for some reason sign-then-encrypt must be used, make sure to encrypt the signature even if it is randomized; pay care that deciphering of any invalid ciphertext can not trigger undesirable behavior on the receiver side; and pay care that signature verification of partially invalid messages does not leak information about the message.

(and) Use a signature scheme with hash-based padding
In order to RSA-sign a message $m$ (confidential or not), signature must NOT be computed as $σ=m^d\bmod N$, which would be an unsafe use of textbook RSA. Rather, one might (there are other secure ways)

compute $h=H(m)$ for some hash function $H$ like SHA-256, with $h$ what will actually be signed (albeit still not using textbook RSA, as it could be vulnerable to forgery if the adversary could obtain the signature of chosen messages)
appropriately pad $h$ into a so-called message-representative $r$ with $0<r<N$ by some method (possibly involving adding randomness), the most common such methods being RSASSA-PSS and RSASSA-PKCS1-v1_5 in PKCS#1;
compute the signature as $σ=r^d\bmod N$
build the signed message as $m\|σ$ (that is, append the signature); the verifier will extract $m$ and $σ$ from $m\|σ$, compute $h=H(m)$, compute $r=σ^e\bmod N$, and check $r$ against $h$ according to the padding method.


Are there lower bounds to how efficient one can make obfuscated code? I am wondering if there are any theoretical reasons why obfuscated programs cannot be nearly as efficient as the plaintext programs and whether there is any necessary computational overhead from running obfuscated code instead of plaintext code.

Let $\mathcal{O}$ denote an indistinguishability obfuscator; for each circuit
$C$ and random data $\mathbf{x}$, $\mathcal{O}(\mathbf{x},C)$ is an obfuscated circuit that computes the same function as $C$. Is it possible that the obfuscator $\mathcal{O}$ only increases the depth, width or gate count of the circuit $C$ by a linear factor? If not, then what level of complexity overhead is required for the obfuscated circuit
$\mathcal{O}(\mathbf{x},C)$? In other words, given a measure $L$ of the complexity of a circuit (for example, $L(C)$ could denote the depth of the circuit $C$), does there exist a constant $\alpha$ and an obfuscator $\mathcal{O}$ where $L(C)\leq\alpha\cdot L(\mathcal{O}(\mathbf{x},C))$ for each circuit $C$ and string $\mathbf{x}$? For which functions $f$ and complexity measures $L$ does there exist a constant $\alpha$ and an obfuscator $\mathcal{O}$ such that $L(C)\leq \alpha\cdot f(\alpha\cdot L(O(\mathbf{x},C)))$ for each circuit $C$ and string $\mathbf{x}$?

I am not very much interested in the computational complexity of the obfuscation operator $\mathcal{O}$ (as long as the obfuscator $\mathcal{O}$ terminates in polynomially many steps), but I am instead interested only in the complexity of the resulting obfuscated circuit $\mathcal{O}(\mathbf{x},C)$.

tl;dr-  No, in a general model, there's no lower bound except simply that $\alpha \ge 0.$   The easiest way to see this is to consider the fact that, in the general case, the property of one program being an obfuscation of another implies that the first program is also an obfuscation of the second.  Likewise, two differently generated obfuscations of the same programs are also obfuscations of each other.

To get a more practical bound $\alpha$ for use in real-world analysis, a more restrictive model for allowed programs and computers would have to be adopted, as the general case doesn't offer any such bound.

Proof that obfuscation doesn't imply a performance hit in the general case

An obfuscated program can be arbitrarily more efficient than a non-obfuscated one, i.e. $\alpha \to 0 .$

The quick proof is to consider the symmetry of obfuscation.  For example, consider a family of mutually indistinguishable obfuscations of the same program, e.g.$$
C_{i+1}~=~\mathcal{O}\left(C_i\right) \,. {}^{\phantom{-1}}
{\rlap{\qquad \forall i \in \mathbb{N}}}
\tag{1}
$$Now we've got an infinite set of programs that're mutually indistinguishable; and, assuming that $\mathcal{O}\left(\phantom{C}\right)$ tends to cause a hit in performance, then the performance of an obfuscated program $C_i$ becomes arbitrarily poor as $i \to \infty .$

We can then redescribe this family as$$
C_{i}~=~\mathcal{O}^{-1}\left(C_{i+1}\right) \, ,
{\rlap{\qquad \forall i \in \mathbb{N}}}
\tag{2}
$$where we're basically flipping which programs we describe as obfuscations of the others.

While that symmetry argument's probably the easiest, we can also note that obfuscation can include a robust optimization step or something to get $\alpha$ down.

So, in short, no, there's no practical lower bound for $\alpha$ beyond $0$ in the general case.  If you're interested in finding practical bounds for $\alpha$ for use in real-world scenarios, then special-case models will need to be assumed rather than the general case.

Pedantic:  Obfuscation could cause a program to be instant

Consider a program

DoHaltingProblem();
Print("Done!");

If an obfuscator can prove that the halting problem doesn't halt (noting that the issue of halting is incomplete, such that the property of being a halting problem is observer-subjective), then it knows that Print("Done!"); will never execute, allowing it to produce an empty-program

// Literally no instructions to perform

that an observer that perceives the program as containing a halting problem can't knowingly determine to be equivalent.  Then, technically, $\alpha = 0 .$

Kinda pedantic, but I guess that I just felt weird writing $\alpha > 0 .$


Why do I need to store the salt for generated hashes? I am new to crypto and authentication so have been doing reading around this and thought that I had a pretty good understanding of how this works. However when implementing my hashing using bcrypt.js I am once again confused.

I thought that the steps were:

Store Credentials:

Generate random salt
Append salt to password
Generate hash from concatenated string
Store the username, hash and salt

Verify User:

Find user record using username
append stored salt to entered password
hash concatenated string
compare generated hash with stored hash

However reading the bcrypt.js readme I can generate with:

var salt = bcrypt.genSaltSync(10);
var hash = bcrypt.hashSync("B4c0/\/", salt);

then compare with:

bcrypt.compareSync("enteredPassword", storedHash)

So it seems that there is no need to store the salt at all.

Also looking at the generated hashes:

[
    {
        "username": "UserOne",
        "hash": "$2a$10$M6qZCSbwhXipdmMy7kQ4V.obtALLSAjZsMYD/oGDAo0i/fcSGrmn2",
        "salt": "$2a$10$M6qZCSbwhXipdmMy7kQ4V."
    },
    {
        "username": "UserTwo",
        "hash": "$2a$10$Yb04C6pVgKVdNjHRB42vKOkr5Wf4QVG8gXyXVqZWnzCs6/MFnIC9G",
        "salt": "$2a$10$Yb04C6pVgKVdNjHRB42vKO"
    }
]

The salt seems to be appended to the hash. Not appended to the password before hashing. This seems pretty pointless to me as any attacker could just strip the salt from the hashes to get a table of not salted hashes.

As I said I am really new to this stuff and getting my head around it is a little difficult. Any simple explanations much appreciated.

The hash returned by bcrypt.hashSync is more than the hash itself, it contains all parameters needed by bcrypt. You do not need to store anything else yourself, this information is everything bcrypt needs to hash and compare an incoming password.

The actual hash was computed by combining the password and salt, so no worries there. The structured data is there merely to make your life easier and only need a single object to store.

In your first example, the output is:

$2a$10$M6qZCSbwhXipdmMy7kQ4V.obtALLSAjZsMYD/oGDAo0i/fcSGrmn2

This breaks down into:

version information: 2a
the number of rounds to perform: 10
the salt: M6qZCSbwhXipdmMy7kQ4V.
the actual hash: obtALLSAjZsMYD/oGDAo0i/fcSGrmn2

You can see the details in the code


If RSA is limited to 117-200 bytes or so, is that a very limited use case? Am I missing something, or is RSA very very limiting when it comes to ecrypting data when it comes to the actual message size?

I have read that you can only encrypt a message of around 117 to 200 bytes in size (depending on your key size: 1024 or 2048 bits). Is this correct?

If so, I think I have read people suggesting on using it for larger files. I guess they are just repeating the process many times over and over in blocks of 117 bytes?

In practice, asymmetric algorithms like RSA are usually used for key transport. In other words, instead of a true message, they are used to encrypt a secret key for a symmetric cipher.

That symmetric cipher key is used to encrypt the actual message, and that could be gigabytes, depending on the algorithm.

Standards like TLS, PGP, and S/MIME use RSA in this way.

By the way, a limit of 117 bytes is for a 1024-bit RSA key. Keys that small are no longer recommended.


Example of product cipher more secure than its components Can anyone give me an example of a product cipher which more secure than its components.
Here is how the explanation should proceed.

There is cipher C1 which can be attacked with the technique A1, and cipher C2 which can be attacked with the technique A2, but the product of the two, C1C2 can not be attacked with A1, A2 or the combination of the two.

For

a $1$-bit message $m$
a randomly generated, fixed prime $k$ (the key)
per-ciphertext randomly generated $r$ and/or $e$

C1, C2

$$C_1 : (k * r) + m$$
$$C_2 : (2 * e) + m$$

A1, A2

$$\begin{align}A_1(c_0, c_1) : c' = c_0 - m_0\\c'' = c_1 - m_1\\k = \operatorname{gcd}(c', c'') = \operatorname{gcd}(k*r_0, k*r_1)\end{align}$$
$$\begin{align}A_2(c_0) : m = c_0 \bmod 2\end{align}$$

C12

$$C_{(12)} : (k * r) + (2 * e) + m$$
$$A_{(12)} : \text{Solve the AGCD problem}$$

Notes

Attacks assume the known-plaintext attack scenario
$C_2$ by itself might be considered a pathological example by itself, but as you can see above, when combined with some $C_1$ it contributes immensely to security.
$A_1$ might require multiple applications if $k$ is not prime


DecryptNode for non-leaf Node in CP-ABE I've looked at paper Ciphertext-Policy Attribute-Based Encryption by Bethencourt, Sahai, Waters and see this an answer here for the explanation of DecrypNode for a leaf node.

I could understand the derivation of this $f_n$ for a leaf node but not for a non-leaf node in the $s$.

I could not understand the move from step 4 to 5 ( the last move).

I will be very grateful Can somebody help in understanding the last move here?

How qx(0) = qx(1) /\1(0) . qx(2) /\2(0) . qx(3) /_\3(0) . ...  ? I dont think legarange interpolation says this. I think i am missing something heere. Please help me in understanding this.

Thanks and Regards

The last two steps is from Lagrange interpolation such that $\sum_{i\in S_x'} q_x(i)\triangle_{i,S_x'}(0)=q_x(0)$. The concept is the same as that of leaf node, but now we are at the parent node. Doing this recursively up to the root node would give the secret exponent.


Relation between key size and PRNG state size Some (supposedly) cryptographically secure PRNGs have an internal state of only 160 bits or less. When the algorithm is otherwise properly designed, that seems like enough to generate a 128 bit key for e.g. AES.

Can the PRNG also be used for the generation of longer keys, e.g. RSA keys with 1024 bits?

My intuition is that it would take (on average) a brute force attack of 2^159 key generations to find the same key, which is probably harder than factoring the 1024 bit key (according to various key length comparisons).

Is there an easier way to crack an RSA key generated using such a PRNG? The OpenSSL PRNG documentation states that an internal state of at least 4096 bits is required to securely generate an RSA-4096 key; that would contradict my intuition.

Your intuition is correct.

While more bits of entropy is better when generating a key, attacking RSA through the key generation process is an independent attack of factoring the modulus, and is predicated on a different computational hardness assumption, search of the keyspace compared to the hidden subgroup problem for finite Abelian groups (for factoring or discrete logarithm.) Factoring at least seems subexponential but superpolynomial, so is significantly easier than search; Many search problems appear to be NP hard, with exponential time complexity in the average case.

The attack on the key generation process depends on the cryptographic strength of the PRNG, and is analogous to attacking a symmetric ciphers in many ways. Since the attacks against PRNG's are so similar to attacks against symmetric ciphers, you can use the guides at keylength for symmetric ciphers as guides to the minimum state for key generation as its entirely appropriate. If you're using RSA for key exchange, and your symmetric key length is smaller than the key length of your PRNG seed, they won't bother attacking the key generation process.

The question does highlight a very important concern about prudent cryptography however, and that is that key generation is highly vulnerable to attack by poor implementation. A cryptographically secure PRNG is essential if using a PRNG for key generation.


Cryptographic hash with ability to ignore specific bits based on a hidden pattern? I'm looking to use password-style hashing to validate an environment, where some parts may be irrelevant. For example:

requirement = 0b1010
pattern = 0b1011
mask( a, b ) = a & b
hash( a ) = <any cryptographic hash>
condition = hash( mask( requirement, pattern ) )

# public
environment = 0b1110
hash( mask( environment, pattern ) ) == condition
-> true

So for the requirement 0b1010 and pattern 0b1011, both environments 0b1010 and 0b1110 would match (though typically there would be many more possibilities, since I expect only a small proportion of an environment to be relevant for a particular test)

The pseudo-code above would accomplish my goal, but it requires the pattern to be available in plain-text (since it must be applied to the given environment directly). The final check is performed publicly, and I would like to hide the pattern at this point, i.e.:

mask( a, b ) = ???
hash( a ) = ???
encryptedPattern = ???
condition = mask( hash( requirement ), encryptedPattern )

# public
environment = 0b1110
mask( hash( environment ), encryptedPattern ) == condition
-> true

The ultimate brute-force approach would be to generate salted hashes for every matching environment (doubling-up some possibilities to hide the information about how many bits the pattern masks out) and test them all in-turn, but clearly this isn't practical once more than a few bits are considered irrelevant.

I haven't been able to find anything on hashes constructed to have deliberate collisions, or accept ranges, and I don't believe it would be possible to retain positional information through a hash while maintaining irreversibility. At the same time, this feels like something which has probably already been studied, and I'm just missing the relevant terminology to find it.

Is there any existing work on this type of check, or methods which could be extended to support it? Alternatively, is it provably impossible?

For context, my eventual plan is to extend this by checking hash( mask( hash( environment ), encryptedPattern ) ) == hash( condition ), and use the unhashed condition (which would only be available by getting the "password" correct) as a key to decrypt other data.

Suppose you had such a hash. Then anyone who knew some value for which the condition matched could find out the full pattern/mask:

You know some environment for which mask(hash( environment ), encryptedPattern ) == encryptedCondition.
You can flip one bit at a time, compute the masked hash, and see if you still get a match. If you do, that bit was masked out in the (unencrypted) mask pattern.

So possibly what you want is impossible. However, if you only need the pattern to remain hidden from those who do not know any matches, it may be possible using homomorphic encryption.

Take a suitable homomorphic encryption system that allows computing ANDs and verifying the results*. Encrypt the mask m = E(pattern) and the condition c = E(requirement).
The user encrypts a value E(environment), ANDs with the mask and compares to the condition: E(environment) & m == c.

* The system must be deterministic and have E(x) & E(y) = E(x&y).

(Note: the use of deterministic encryption means that a user can guess and test values against pattern and requirement. This is quite weak, but conceivably there could be applications.)


How to implement correctly an Integrated Encryption Scheme? I am developing a REST client (from an Android Point Of Sale) where I'm given a public RSA 2048-bit key and I need to encrypt transaction information. Since that single block cannot be encrypted (and AFAIK it should not) with the public key, we need to encrypt it using AES 128-bit. So we generate a random key (using KeyGenerator class), encrypt the info and send the AES key encrypted under their public key. AES is in ECB mode for their requirement which I know is insecure.

So the question would be: what pitfalls (apart from ECB) this method has?

My idea was to implement a kind of ECIES (but without Elliptic Curve) where a key derivation function is used (altough I'm a noob and don't know how to implement it) and using an authenticated encryption method like AES-GCM.

To extend the question I will like some context as I think I have sparse information and need to "connect altogether".

You have the right idea!  There's a very general construction for public-key encryption called KEM/DEM that works as follows to encrypt a message $m$:

Key encapsulation mechanism, KEM: Generate a key $k$ and an encapsulation $y$ using a public key.
Data encapsulation mechanism, DEM: Use $k$ to authenticate and encrypt $m$ giving an authenticated ciphertext $c$.
Transmit the encapsulation $y$ along with the ciphertext $c$.

The recipient, with the secret key, can recover $k$ from $y$ and then decrypt $c$.

For RSA, you can make a KEM as follows with a public key $n$:

Pick an integer $x$ between $0$ and $n$ uniformly at random.
Compute $y = x^3 \bmod n$.
Compute $k = H(x)$, where $H$ is (say) SHA-256.

The recipient uses secret knowledge of the solution $d$ to $3d \equiv 1 \pmod{\lambda(n)}$, where $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$ if $n = pq$, to recover $x = y^d \bmod n$, and then computes the same $k = H(x)$.

The security requirement for a DEM is modest.  An authenticated cipher like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305, with nonce set to zero, will do just fine.  (I recommend AES-256 if you must use AES, to avoid multi-target attacks; I recommend crypto_secretbox_xsalsa20poly1305 over AES-GCM, to avoid side channel attacks on AES and GHASH in fast software implementations.)

ECIES is an example of the KEM/DEM structure—for a public key $A$ on an elliptic curve with standard base point $B$, you pick a scalar $t$ uniformly at random, compute $T = [t]B$, derive the key $k = H([t]A)$, and use $T$ as the encapsulation of the secret key $k$ which you use in an authenticated cipher to encrypt the message; the recipient knows the secret $a$ such that $A = [a]B$, and given $T$ recovers $H([a]T) = H([a\cdot t] B) = H([t\cdot a]B) = H([t]A) = k$ to decrypt the authenticated ciphertext.

You can also generate $k$ independently and shoe-horn it into an encapsulation like RSAES-OAEP.  But, while this is probably the most common way to do RSA encryption out of inertia, it is more complicated than necessary.


Generate AES key from weak string I'm trying to generate AES256 key from user input password.
The size of the password can be anything from 4 bytes long to 32 bytes long but let's assume
it is the smaller one.
My API support either : SP800-108 HMAC in counter mode, SP800-56A, PBKDF2 or CAPI_KDF
According to several articles I read, the common PBKDF2 suffers from multiple weaknesses and so it's not an option.
I would like to know which one from the above is the most secure KDF for my purpose.
In addition I would like to know what the relations between the algorithms above to Argon2 and Scrypt.
Thank you in advance :)

You need a key stretching function, not a mere key derivation function. A key stretching function is technically a kind of key derivation function, but most key derivation functions are not key stretching functions. A key stretching function is intrinsically slow to reduce the possibility of brute force guessing, and includes a salt input to make precomputations useless when attacking many accounts. See How to securely hash passwords? for more explanations: hashing a password and deriving a key from a password are very similar cryptographic problems with basically the same solution.
SP800-108 and SP800-56A are families of ordinary (non-stretching) key derivation functions. They are not suitable here. I don't know what CAPI_KDF is but according to the Windows API documentation it doesn't take a salt or a difficulty parameter so it can't be a key stretching function.
PBKDF2 is a key stretching function. It's designed precisely for what you want to do. It has weaknesses, but that's compared to more modern key stretching functions. Specifically, PBKDF2 intrinsically requires a lot of computing power, but very little memory, so it can be executed more cheaply on GPU or ASIC (which an attacker would typically use) than on a CPU (which the legitimate server is using). Scrypt and Argon require a lot of RAM (comparatively) which can only be realistically available on the same kind of hardware that a typical server is using, so the attacker doesn't have an advantage in terms of computing power. So PBKDF2 is not the best choice if you have a choice. But you don't have a choice: you don't have access to bcrypt, scrypt or Argon2. (Note that “bcrypt” here is the algorithm, it's unrelated to “bcrypt” as in bcrypt.h in the Windows API.) So use PBKDF2.
PBKDF2 for hashing passwords (or deriving keys from passwords) is ok. It isn't ideal, but it's ok. All of your other options would be catastrophically wrong.
Generally you should only use the key obtained with PBKDF2 to wrap (encrypt) another key. This way, when the user updates her password, you only need to update this wrapped key.
If you're both authenticating the password and deriving a key from it, see Is it safe to split the output of PBKDF2?
Note that a key stretching function can't do miracles. If the password space is too small, it's realistic for an attacker to try them all. For example, at 1 attempt per second (which is on the high side), it only takes a few hours to break a 4-digit PIN (13.3 bits of entropy). A case-insensitive 4-letter password with random letters has 18.8 bits of entropy and would only last a few days without parallelization. You really should make the minimum length higher.


Is my HMAC secure if I have a complete series of HMAC'd prefix strings Let's say I have a long sentence, like "The quick brown fox jumped over the lazy dog." Let's further say that I need to keep this string encrypted, so I use an HMAC. Let's further further say I want to be able to do prefix searches for this string, so I also store all possible prefixes of this string, for example:

$\operatorname{HMAC}_K(\text{"T"})$, $\operatorname{HMAC}_K(\text{"Th"})$, $\operatorname{HMAC}_K(\text{"The"})$, $\operatorname{HMAC}_K(\text{"The "})$, etc. where $K$ is the key.

I recognize there are some weaknesses between rows here involving overlap, but what I'm interested in is whether having this one row's set of HMAC values is enough to make things insecure. Could an adversary work out the key, or any part of the plaintext, given a series of HMAC values for all of a given input's prefix values?

Feel free to use any flavor of HMAC if it'll help you argue that there's a weakness.

I'll start by assuming that your instance of HMAC is a secure MAC function, which comes down to making various assumptions about the hash function it is instantiated with.

If this assumption holds, then an adversary will not be practically able to recover the key, even if they have access to a large number of MACs and the corresponding plaintexts, or even if they get to choose their own plaintexts — if it was possible for them to obtain the key, they'd be able to compute their own MACs and thus commit existential forgery, contradicting the assumed security property.

As for plaintext recovery, in general there's nothing that prevents a MAC function which is secure against existential forgery from leaking some information about the input plaintext, and indeed it's not hard to delibrately construct examples of such MACs (as Ricky Demer's answer shows).

However, the security proof of HMAC given by Bellare actually proves a stronger property, namely that HMAC is a PRF as long as the compression function of the hash it is instantiated with is also a PRF (or, more generally, than HMAC is a privacy preserving MAC (PP-MAC) as defined by Bellare, as long as the compression function is also a PP-MAC and the hash function itself is computationally almost universal (cAU); see remark on Lemma 4.2).  This is a rather strong security property, and it indeed shows that, as long as the hash function satisfies the assumptions of the proof, HMAC will not leak information about the plaintext to an adversary who does not possess the key.


Difference between computational complexities in General Number Field Sieve I'm told that General Number Field Sieve works with computational complexity $e^{\sqrt[3]{\frac{64}{9}+o(1)}\;(\ln n)^{\frac{1}{3}}\;(\ln\ln n)^{\frac{2}{3}}}$. However, without some computation work it should run with computational complexity $e^{\sqrt[3]{3+o(1)}\;(\ln n)^{\frac{1}{3}}\;(\ln\ln n)^{\frac{2}{3}}}$.

This does not seem to be as a big difference but according to the following table it is:

How can be the difference so huge if only a constant changes?

By moving the $o(1)$ and using elementary algebra, the formulas given can be rewritten with a single digit difference, as
$$\left(e^{(3^{-2/3})\;(\ln n)^{\frac{1}{3}}\;(\ln\ln n)^{\frac{2}{3}}}\right)^{4+o(1)}\;\text{ and }\;\left(e^{(3^{-2/3})\;(\ln n)^{\frac{1}{3}}\;(\ln\ln n)^{\frac{2}{3}}}\right)^{3+o(1)}$$

Two things are now apparent:

The exponent changes from about 4 to about 3; this qualitatively explains why there is such an enormous gap.
The $o(1)$ beats any outer multiplicative factor, and the formulas are thus missing some unknown, possibly large multiplicative factor when we use them for any particular $n$. This explains why we can at best use the formulas to predict approximately how the run time of each of the attacks (or the ratio of the two run times) scales with $n$ (and then, not rigorously); but not to quantitatively predict the relative runtime of the two algorithms for some $n$.


How Diffie-Hellman authentication works? There are a lot of good videos on a simple Diffie-Hellman in the internet but unfortunately that is susceptible to the MITM attack. I understand how with DH  the two parties are able to calculate a shared secret (shared private key?)

So now i am trying to understand the authenticated version, which should be safe from the MITM attack. Unfortunately i have not found a simple explanation to how it should work.

As I understand it requires the use of some certificates (pre existing keys?). Having some pre existing keys does not make a lot of sense to me, since the whole purpose of DH is key exchange.
And vice versa:
If i can just generate a private and public key for both parties and transfer the public keys than why do i need DH at all?
Is an entirely secure method available to establish a connection between the two parties who don't have some preexisting knowledge of each other (by using authenticated DH)? If so then how does the authentication scheme work?

Diffie-Hellman comes in two basic forms - static and ephemeral - and a number of combinations of those.

Ephemeral Diffie-Hellman means that both parties of a key agreement generate new - ephemeral - key pairs and send their respective ephemeral public key to the other party. If both parties generate ephemeral key pairs each time, you get Perfect Forward Secrecy. This type of key agreement is usually used in conjunction with signature algorithms (RSA, DSA, ECDSA) to authenticate the ephemeral public keys of one or both parties. When Ephemeral Diffie-Hellman is used plainly, without a supplemental signature algorithm, it is anonymous, unauthenticated and susceptible to MITM attacks.
Static Diffie-Hellman means that both parties of a key agreement use long term - static - key pairs. This form of Diffie-Hellman becomes authenticated exactly when at least one party is able to link the other party to the static key that is used. Typically, this is done either by that party having advance knowledge of the Static Diffie-Hellman public key of the other party, or by both parties belonging to some form of Public Key Infrastructure, in which a trusted third party connects the identity of the peer to its public key.

Hence, regarding your questions:

The purpose of Diffie-Hellman is to agree on a shared secret. This is perfectly possible with long term static keys. The public keys will still have to be exchanged somehow, but it might be done ahead of time, through authenticated channels.
Static Diffie-Hellman public keys would typically be exchanged through a Public Key Infrastructure. Having two parties directly exchanging static public keys to use with Static Diffie-Hellman, would indeed not necessarily be better or more practical than them generating a shared secret directly, and storing that shared secret instead of the public key of the other party.
The purpose of authentication is typically to tie an online presence to some form of identity that makes some form of sense to the other party. Typically, you want a method of authentication that identifies the other party in the way that makes most sense given the circumstances. Theoretically, if the parties have no advance knowledge of each other, and will not assign any other identity to each other beyond the initial online presence, they could use the public keys from the initial anonymous key exchange for authentication. Normally, authentication would however be accomplished either by exchanging public keys in advance, or by means of a public key infrastructure.


Avoiding overflow when encrypting with RSA When encrypting with RSA one calculates $ m^e \pmod n $ by doing the following:

m^e % n

Where $m$ is what we encrypt. Often $e$ is a very big number to make it more difficult to crack.

So how does one avoid overflow when encrypting?

Actually, the fundamental mathematical operation is not
$$
\begin{align}
  \mathbb{N} &\to \mathbb{N} \\
  m &\mapsto (m^e) \bmod n & \text{(elevate to the power of \(e\), divide by \(n\) and take the remainder)} \\
\end{align}
$$
but
$$
\begin{align}
  \mathbb{Z}/n\mathbb{Z} &\to \mathbb{Z}/n\mathbb{Z} \\
  m &\mapsto (m^e) \bmod n & \text{(elevate to the power of \(e\))}\hphantom{\text{, divide by \(n\) and take the remainder}} \\
\end{align}
$$
It is an operation in modulo arithmetic.

In computations, the elements of $\mathbb{Z}/n\mathbb{Z}$ are almost always represented by the representative in the range $[0,n-1]$. Each elementary operation is performed in $\mathbb{N}$, then the result is truncated modulo $n$. For example, if $n$ fits in $k$ machine words, then a multiplication of two elements of $\mathbb{Z}/n\mathbb{Z}$ can be performed by computing the product, which fits in $2k$ machine words, then taking the remainder modulo $n$, yielding a representation of the element of $\mathbb{Z}/n\mathbb{Z}$ that is again in the range $[0,n-1]$ and in particular fits in $k$ words. Taking the exponential of a number involves a series of multiplication, each of which is truncated to $[0,n-1]$ in this way so as to obtain the smallest representative of the element of $\mathbb{Z}/n\mathbb{Z}$.

Even multiplication of two $k$-word numbers can be performed with intermediate values fitting in $k$ words. The naive method is wasteful both in the amount of memory and in that it builds a large number only to divide it afterwards. Methods such as Montgomery multiplication avoid computing a double-size number by reducing the size of the result after each intermediate step in the multiplication.


Relative security of a Vigenère cipher Within a closed computer network, I am ciphering some plaintext data as an added security measure. This is below several other layers of protection. For various technical reasons, I am restricted to plain-text, UTF-8 data. To that end, I have been using a Vigenère cipher with pre-shared key database. The keys range from 30 to 100 characters, and are not dictionary words.

My question is regarding the Vigenère cipher: It is my understanding that the security of this cipher is directly related to the length and security of the keys. Long and tightly secured keys bring this cipher on par with many more complex techniques. Is that true, or is this a "kiddie" cipher that could be cracked while you sleep?

Edit It may bear mentioning, the text that is being ciphered is JSON encoded data arrays, which is human readable but not "natural language" -- it contains many symbols interspersed with the actual data.

EDIT 2 Plaintext length varies unpredictably, from 100 characters to 5,000 plus. The data is being transported via SSL, so this is, as I mentioned, intended as yet another added layer, not the whole and sum of security used.

The Vigenère cipher has many weaknesses, but perhaps the most obvious ones are:

An attacker, who knows (or can guess) as many consecutive characters of any plaintext message as there are in the key, can trivially recover the key and thus decrypt all messages.  (In fact, the characters need not even be consecutive, they just need to cover the entire key, or at least most of it.)
For most natural messages, it's fairly easy to guess the key length, for example by looking at correlations between characters $n$ positions apart.
An attacker who knows (or can guess) the key length can divide the ciphertext into blocks of this length and decrypt one block with the other as the key to obtain a linear combination of the two messages.  This will often have enough structure to allow the original blocks to be (at least partially) reconstructed, which in turn allows recovery of the key.  (Also, if there are multiple messages encrypted with the same key, or if the key itself is not completely random, other similar attacks may be possible even without guessing the key length.)

In short, I would strongly recommend not using the Vigenère cipher for any purpose, except perhaps for puzzles that are meant to be broken.  At the very least, use a stream cipher like RC4, which is simple enough to implement off the top of your head.  Also, if you need to encrypt multiple files, include a unique initialization vector with each (or derive one from some unique value, like the name of the file) and hash it together with your master key.

(Using a stream cipher in such a way that they output remains valid Unicode text is a somewhat non-trivial exercise in format-preserving encryption, but it should be no harder than doing the same with a Vigenère cipher.  Personally, I'd suggest encrypting the input as a binary octet stream and then Base64-encoding it into printable ASCII as the simplest secure method.)


Are the definitions of IND-CCA secure and of IND-CCA secure under standard model identical? Suppose there is a public key cryptosystem based on the discrete logarithm problem and let this cryptosystem be IND-CCA secure under standard model. Does this statement mean that the given cryptosystem is IND-CCA secure if Diffie-hellman assumption holds (that is the problem on which the given cryptosystem is based) or there may be any other assumptions (problems)?

A cryptosystem is not "based on an assumption" ; it is based on some mathematical structure (e.g. prime order elliptic curves, or prime order fields). Informally, a cryptosystem is said IND-CCA secure (which means: it satisfies the indistinguishability security notion, against adversaries which are given access to a decryption oracle) under some assumption A if given access to an adversary that breaks the IND-CCA security of the scheme, one can construct an algorithm breaking A.

But you cannot say that "A is the problem on which the cryptosystem is based": for a given cryptosystem, different security notions can be based on different assumptions. For example, take the case of ElGamal: it is IND-CPA secure under the DDH assumption, and (a slight variant of) it was also proven IND-CCA1 secure (CCA1 indicates that the adversary can make decryption queries only before receiving the challenge ciphertext - this is also known as security against lunchtime attacks), but only under a very different and less standard assumption (see this paper for example, or some of the related papers it mentions in the intro).

So when a cryptosystem is said to be IND-CCA secure, it does not tell anything about the assumption on which it is based.

The term "in the standard model" relates to a completely different things (it does not say anything either on the particular computational assumption to which a security notion for the scheme can be reduced): it is common in crypto, when dealing with a hard problem, to consider simplified "worlds" in which the players could have access to some ideal primitive, and then to instantiate this primitive "in practice" with something which seems a good candidate for this ideal primitive, based on our current understanding of it.

The most common example is that of the random oracle model: we assume that the players are in a world in which they have access to an oracle which acts as a truly random function, and then we prove that some cryptosystem is secure (e.g. IND-CCA secure) under some computational assumption in this simplified world. This does however not prove that in the real world, the cryptosystem would be secure; using SHA-256, for example, as a random oracle seems to work in practice, but SHA-256 is not a random oracle.

Saying that something is secure in the standard model is just a way to say that no such idealized world is considered: the proof is "in the real world" and does not assume any idealized primitive.


Why is hybrid encryption more effective than other encryption scheme? Currently I am learning about Hybrid Encryption but I was not able to find any good study material.

Below is my understanding:

One of the reason why we use Hybrid Encryption because public-key cryptosystems often rely on complicated mathematical computations and are thus generally much more inefficient than comparable symmetric-key cryptosystems. A hybrid cryptosystem is one which combines the convenience of a public-key cryptosystem with the efficiency of a symmetric-key cryptosystem.

Steps of Hybrid Encryption:

  To encrypt a message addressed to Alice in a hybrid cryptosystem, Bob
  does the following:

Obtains Alice's public key.
Generates a fresh symmetric key for the data encapsulation scheme.
Encrypts the message under the data encapsulation scheme, using the symmetric key just generated.
Encrypt the symmetric key under the key encapsulation scheme, using Alice's public key.
Send both of these encryptions to Alice.

  To decrypt this hybrid ciphertext, Alice does the following:

uses her private key to decrypt the symmetric key contained in the key encapsulation segment.
uses this symmetric key to decrypt the message contained in the data encapsulation segment.

I am pretty much understood how Hybrid Encryption works but I don't see how this is better than Public Key Cryptography.

Question :- Why is Hybrid Encryption superior?

It is doing an extra work for generating a symmetric key by using Alice's public key. This will also involve complex mathematical computation.
Along with sending data here it also needs to key along.
Alice also needs to first decrypt the symmetric key and then decrypt the message. It almost seems like a double work.

I found some answers here but still it seems incomplete link1 and link2

Alice also needs to first decrypt the symmetric key and then decrypt the message. It almost seems like a double work.

Encrypting a short plaintext (i.e. the symmetric key) requires only one asymmetric (e.g. RSA) operation, while encrypting a longer message would in theory require many RSA operations.

Suppose we want to encrypt a 1 MiB message.  Using 2048-bit RSA-OAEP exclusively (i.e. without hybrid encryption) would require over 5500 RSA encrypt operations (leaving aside for now the question of mode of operation), all of which are expensive in terms of performance.  Using hybrid encryption, we can perform a single expensive RSA encrypt operation on a symmetric key, and do all of the remaining work using fast symmetric encryption like AES-GCM.

  Along with sending data here it also needs to [send the] key along.

You're right about this.  Hybrid encryption does make the ciphertext longer in cases where the messages are very short.  However, 2048-bit RSA-OAEP (for example) operates on plaintexts of at most 190 bytes, so the threshold at which hybrid encryption becomes more efficient is fairly low.


Are one-time pads crackable in theory? I've been taught that one-time pads are the only perfect encryption since the only way to recover the message is by knowing the key.

For example, for a target bitstring of 100 bits, I cannot scan all bitstrings of 100 bits and XOR each with the target, hoping to recover the message.  This approach will produce all messages that can be expressed with 100 bits.

However, not all bitstrings are random, e.g. 11111111111111 is less random than 01101001001101.  This observation seems to contradict the idea of an unbreakable one time pad.

We know two random bitstrings are independent of each other, as well as independent from non-random bitstrings.  So, knowing a random bitstring will not allow you to shorten the description of a second bitstring and vice versa.  Thus, if we randomly generate a bitstring BS1, then when XORed with the key BS2 it will produce a third bitstring BS3 that is not compressible.

Proof: If BS3 is compressible, then knowing BS1 would allow us to describe BS2 with a short description (i.e. BS3).  Then, either BS1 and BS2 are not both random or are not independent.  The only case where they are random, but not independent, is if one is a part of the other.

This means that if XORing BS1 with ciphertext BS4 results in a compressible BS5, then BS1 is at least part of BS2 or contains part of BS2.

So, at least in theory, it seems that one-time pads are breakable, although this approach is not computable since we'd need to compute that a bitstring is truly random.

This argument contradicts what I've been taught, and I'm wondering if OTPs are only said to be perfect because randomness is not computable.

For example, for a target bitstring of 100 bits, I cannot scan all bitstrings of 100 bits and XOR each with the target, hoping to recover the message. This approach will produce all messages that can be expressed with 100 bits.

That's not the reason why one-time-pads are considered secure. The reason is that even if you try all possible keys that you get all possible plaintext and you have no method of choosing which one is right. The size of the plaintext/ciphertext/keystream doesn't matter.

  However, not all bitstrings are random, e.g. 111111111111 is less random than 01101001001101. This observation seems to contradict the idea of an unbreakable one time pad.

111111111111 is equally likely as 01101001001101 or any other value of the same size when chosen randomly.

  Proof: If BS3 is compressible, then knowing BS1 would allow us to describe BS2 with a short description (i.e. BS3). Then, either BS1 and BS2 are not both random or are not independent. The only case where they are random, but not independent, is if one is a part of the other.

Values are compressible if they are part of a set where certain values are more likely than others. This is not the case for $C = P \oplus K$ if $K$ is fully random. This is because $C$ will be fully random as well, independent of $P$ being random or not.

  This means that if XORing BS1 with cyphertex BS4 results in a compressible BS5, then BS1 is at least part of BS2 or contains part of BS2.

This will never be the case as BS5 will not be compressible; each possible value of BS5 will be as likely as the other values of BS5 because of the reasons explained above.


Inverse function of RSA and safe prime requirement of DH Key exchange Ok so the inverse function of RSA encryption (that is decryption) is
$ m \gets c^{d}\bmod N$ where $d$ is the secret exponent
As I understand the hardness of RSA depends on two things: the Integer factorization problem and the discrete logarithm problem. While studying DH Key Exchange, it is a requirement that a safe prime is chosen that will serve as the modulus. But the decryption function of RSA already has a non prime modulus. How come RSA cannot be broken with the modulus not being prime, let alone a safe prime? And what is wrong with choosing a multiple of two primes as modulus in DH Key exchange?

One possible statement of the Discrete Logarithm Problem modulo prime $p$ (the one used in practice in DSA, and more generally when working in a Schnorr group) goes:

given

large random prime $q$,
very large prime $p$ with $p-1$ a multiple of $q$,
integer $g$ of order $q$ modulo $p$ (equivalently, such that $g^q\bmod p=1$ and $g\bmod p\ne1$ ),
$a$ obtained by taking random integer $x\in[0,q)$ and computing $a\gets g^x\bmod p$

find $x$.

The best known algorithms to solve this on classical computers (including Pollard's rho for logarithms) have cost $O\left(\sqrt q\;\log p\;\log\log p\right)$ when $p$ is suitably large (e.g. 3072-bit $p$ or larger for 256-bit $q$).
Variants exist with the following:

$p=2q+1$ (equivalently, $(p-1)/2$ is prime¹); but then the security bound is much lower for equal $\log q$, because the best algorithm becomes (an extension of) GNFS.
It is asked that $g$ is of order $p-1$ (equivalently, that $g$ is a generator), rather than of order $q$ as in the above. It has at least the virtue of insuring that the order of $g$ is large.
Discussion on $p-1$ being a multiple of a known large $q$ is removed and replaced by hope that's the case, which holds with good probability for random $g$ and very large prime $p$. One problem is, it can get hard to find $q$ and/or ascertain² the order of $g$.

By any of the above definitions of the DLP, the modulus $p$ is prime. That makes it incorrect (or at least, neither proven nor widely conjectured) to state, as the question does:

The hardness of RSA depends on two things: the Integer factorization problem and the DLP.

Also, by any of the above definitions of the DLP, the order of $g$ is a given (it's the given $q$, or $p-1$ in some variants). Even if we extend the definition of the DLP to allow for composite modulus $n$ instead of $p$, and as long as we keep assuming that the order of $g$ is a given in that extended DLP, the above statement remains incorrect (or at least, neither proven nor widely conjectured): we don't know how to break RSA given an hypothetical oracle breaking that extended DLP.
If we further extend the definition of the DLP by not assuming that the order of $g$ is a given, then it can be proven that breaking this further extended DLP allows to factor $n$, thus break RSA. The above statement becomes true, but equivalent to the common wisdom:
The hardness of RSA depends on the Integer factorization problem.
or otherwise said: breaking the integer factorization problem breaks RSA. The converse is an open problem, and sometime conjectured.

What is wrong with choosing a multiple of two primes as modulus in DH Key exchange?

If additionally the order of $g$ is known, we can factor the modulus $n$ as $n=r\,s$ with primes $r,s$. And then, using the Pohling-Hellman algorithm, we can reduce the DLP modulo $n$ to several easier DLP problem modulo $r$ and $s$ (or modulo $r^2$ is $s=r$).
In Diffie-Hellman, we don't need to make the order of $g$ known, thus we could get away with choosing $n$ in a way making it hard to find its factorization, as in RSA. But then security of DH would depend to some degree on integer factorization on top of some variant of the DLP, and that's generally not something wanted. It's done only in some contexts, like RSA accumulators.
Further, in many applications of the DLP to cryptography including Schnorr signature and DSA, the order of $g$ needs to be public. Thus using a composite $n$ would require using a much larger modulus at equivalent security, leading to slower computation for no benefit.

¹ That is, $p$ is a safe prime. That's stated as a requirement for DH key exchange in the question, but it's not: any Schnorr group (as in the first part of the question) will do.
² However, we can still pick $g$ of likely order $p-1$ with low residual odds of the contrary: pick a random $g$ until $g^{p-1}\bmod p=1$, and $g^{(p-1)/r}\bmod p\ne1$ for all primes $r$ dividing $p-1$ and $r$ low enough that we find it with simple factorization methods: trial division to some bound and a few rounds of Pollard's rho for factorization.


The Collision Differential for MD4 - a question on notation (Wang, et al) In the paper "Cryptanalysis of the Hash Functions MD4 and RIPEMD" the authors introduce the following notation (paragraph 4.1):

$\Delta$$H_0$ = 0 $\xrightarrow{(M_,M')}$ $\Delta$$H$ = 0

What exactly does this mean? I understand that  $\Delta$$H$ is probably the difference between hash outputs, but what about  $\Delta$$H_0$?

Disclaimer: I have zero knowledge about differential cryptanalysis, so my apologies if the formula above is some kind of standard notation there.

In the MD4 algorithm, the message which is being hashed is split into a series of 512-bit blocks. The collision attack which you reference forms a collision in a single block. That is, the attack forms two colliding messages, X and X', which are identical for every block but one. The paper refers to the blocks of X and X' which differ from one another as M and M', respectively.

Because the parts of X and X' which come before blocks M and M' are identical, they have the same hash. The hash of these blocks is referred to as H$_0$. So $\Delta$H$_0$ = 0 is just saying that the intermediate hash of the messages before blocks M and M' are identical.

$\xrightarrow{(M_,M')}$ means that block M is hashed as a part of its message, and block M' is hashed as a part of its message.

Once these message blocks have been hashed, the hashes of the two messages are still identical, which is what $\Delta$H = 0 is saying.

So, what the equation as a whole is saying, in English, is: "The intermediate hashes of two messages are identical. Then, we process a single block of each message. These blocks are called M and M'. Even though these blocks are not identical, their final hashes are identical."

Note that in some papers for differential cryptanalysis, M and M' will refer not to a single message block, but to the message as a whole. So this is not standard notation.

When I was starting out in differential cryptanalysis, I also had a hard time understanding this equation, but I hope this has helped you.


Elliptic curve with prime subgroup equal to field size I am aware that when the equation $\#E(\mathbb{Z}_p) = p$ holds for prime $p$, the elliptic curve is called "anomalous" and is insecure do to "Smart's attack".

Consider the similar case that $E(\mathbb{Z}_p)$ has a proper subgroup of (prime) order $p$, so $p \neq \#E$. In this case $p$ divides $\#E$ and $\#E > p$. This relationship of the (sub)group order matching the field size (thus forcing primality) is desirable for some applications.

Is such a curve secure for the discrete log performed in the $p$-order subgroup, or is this vulnerable to a similar attack? What would be the process to generate such a curve that is arguably safe for cryptographic use?

From what I read, curves over $GF(2^n)$ for some $n$ are less stable. But analogously, for $E(GF(2^n))$ there could be a subgroup of order $2^n$ and as long as $2^n$ has a large prime factor it should be safe for the discrete log. Is this also a possibility?

It seems that curves like that do not exist.

Hasse's bound states that $|N-(p+1)| \le 2\sqrt p$, where $N=\#E$. Writing the order of the group as $N = ph$, you get:

$|ph-(p+1)| \le 2\sqrt p \rightarrow$

$|p(h-1)-1)| \le 2\sqrt p \rightarrow$

$|\sqrt p(h-1)-\frac{1}{\sqrt p}| \le 2$

The only way this inequality is true for $p > 5$ is if $h = 1$, i.e., $\#E=p$.


Shor algorithm and schnorr signature in ed25519 Does the application of Shor's algorithm in any way relate/affect the schnorr signature in ed25519?

Shor's algorithm can compute discrete logs in elliptic curves and thereby recover the secret scalar from a public Ed25519 key, which you can use to forge signatures of your choice.

So, yes, it affects Ed25519—it completely breaks Ed25519, or it would if you could engineer a quantum computer capable of executing it.

It can also compute discrete logs in finite fields, which you can use to forge traditional finite-field Schnorr signatures.


with RSA encryption, how do I find the md5sum of the private key from the public key? This is a purely mathematical question on RSA encryption.

Having $e$ as the public key exponent and $n$ the modulus of a public key. Can I recover the md5sum of the private key $d$ (inverse of $d$ according to the modulus.)

Thanks for your help.

You cannot get a hash over the entire private key if you've just got $n$ and $e$. You can however create a hash over the modulus $n$. This is sometimes used as identifier for keys within a key pair, e.g. in PKCS#11. Usually SHA-1 is used however, not MD5.

The modulus is unique for RSA key pairs and links the public key and private key together.

md5sum is a GNU utility that performs MD5, it's not an algorithm in itself.


How to build a difference distribution table? i am studying about differential cryptanalysis, and found one metric to measure the resistance of a sbox to it, but to use it, it is necessary to build a difference distribution table, like the one in this link, this is is the table of sobox s1 of des, how do I build the table for AES sbox for example?

Those tables are fairly easy to build conceptually but require quite some work to actually carry out.

Note that: The columns show the XOR for the in-going pairs and the rows show the number of pairs that had the specified XOR afterwards.

This pseudo-code generates the table:

InLength; // input length of the S-Box in bits
OutLengh; // output length of the S-Box  in bits
Table[In][Out]; // the table, In is the XOR of the in-going pair, Out is the resulting XOR, the table returns the number of occurences

// Initialize the table:
for(in = 0;in<2^InLength;in++)
{
  for(out = 0;out<2^OutLength;out++)
  {
    Table[in][out] = 0;
  }
}

// this makes us go through all the possible value of p1
for(p1 = 0;p1<2^InLength;p1++)
{
  // this makes us go through all the possible value of p2
  for(p2 = 0;p2<2^InLength;p2++)
  {
    XOR_IN = p1 XOR p2;
    XOR_OUT = SBOX(p1) XOR SBOX(p2);
    Table[XOR_IN][XOR_OUT]++;
  }
}

What this does is basically build each possible input pair of the S-Box, calculate its XOR, runs both through the S-Box and calculates the XOR of the result and increments the value at this position.

This table would be too complex to show here for AES as it would be a 256x256 table. For the actual AES S-Box refer to the Wikipedia article.


Finding the Shared Key In DHKE I am trying to work out the shared key between Alice and Bob in DHKE equation. The generator is 7 and the Prime P = 71. Bobs private choice of number is 28 and he also receives g ^ A = 70 from Alice. Alice does not seem to have a private choice of number in this equation, all I know is that g ^ A = 70. So how can I calculate the value of the shared key?

I am just having difficulty working it all out. The modulus arithmetic involved is also confusing me. If someone could try to explain it to me.

I know that it must be: A = 7^x (Mod 71) = 70;
and: B = 7^28 (Mod 71);

Then Alice Computes: gB ^ A (Mod 71);
and Bob Computes: (gA)^28 (Mod 71);

You are confusing your notation. You are saying that $g^A\equiv 70 \bmod{71}$, but then you are also saying that $A\equiv 7^x\bmod{71}$. That is not true. So let's clarify the notation.

Let $A$ be Alice's private exponent and $B$ be Bob's private exponent.

You know that $B=28$ and you know that $g^A\equiv 70\bmod{71}$. You do not know $A$, however, but you do not need to know $A$.

The shared key between Alice and Bob is ${g^A}^B\equiv {g^B}^A \bmod{p}$. So given what you know, you can compute the shared secret.

To figure out what Alice's private exponent is, you would have to solve the discrete logarithm. For numbers this small, that would be easy, but in general (and for the size of numbers we use in practice) that is infeasible.


What are the details of the DES weakness of reusing the same IV in CBC mode with the same key? I think I once faced the recommendation, that the initialization vector should always be random and never be used twice with the same key.

How serious is this weakness?

Also, is AES less effected than DES?

The initialization vector is a property of the mode of operation (aka "chaining mode"), not of the block cipher itself. A block cipher does only one thing, which is mapping blocks (block size depends on the cipher, 64-bit for DES, 128-bit for AES) unto other blocks. The chaining mode is what says how input data should be transformed into block values, and how the corresponding encrypted blocks should be combined.

The simplest chaining mode is ECB, in which data is split into blocks in the natural way. The main problem is that for a given key, the block cipher will always transform the same input block value into the same output block value (the algorithm is deterministic), which means that with ECB, the encrypted message will show identical block values where the input blocks were identical. The Wikipedia page linked to above has a nice picture which illustrates what's wrong when applying ECB to a picture. In a general way, this is because "real-life" data has redundancy.

CBC corrects the problem by "randomizing" the input blocks by XORing each input block with the previous encrypted block: encrypted blocks have a "random look" (if the block cipher is any good) so this makes the occurrence of two identical blocks improbable. The IV is just the "previous encrypted block" for the first data block.

CBC is secure as long as the P xor C values, where P is a plaintext block and C the previous encrypted block (or the IV), do not collide more often (or less often) than randomly chosen value would. Since real-life input data has structure, this implies that this "random distribution" must come from the encrypted blocks. A good block cipher will ensure that, except for the IV which is not an encrypted block; so the IV must be randomly chosen. At the extreme case, if the IV is always the same for a given key, then two plaintext messages which begin with the same bytes will yield encrypted messages beginning with the same sequence of block values, and the attacker will see it. More generally speaking, if the IVs have some structure in their choice (e.g. a counter), then that structure could interact with that of the plaintext messages, and again yield collisions which reveal information on the encrypted messages. Conversely, if for a given key you encrypt only a single message, then you can use a conventional IV (e.g. an all-zero IV), because trouble begins when considering two messages encrypted with the same key.

All of the above equally applies to DES and AES. However, the 128-bit blocks of AES make it a bit less vulnerable to sloppy IV selection, because real-life data tends to show less redundancy at the 128-bit level than it does at the 64-bit level. This is still a weakness, and you shall use properly generated random IV for AES too.

Some recent mode of operation (e.g. EAX) have less stringent requirements on IV selection: EAX only needs unique IV values, but does not require random selection (a counter, incremented for each message, is fine with EAX).


Is murmur3 (128) a good hash function to use as a proof (hash) of a document in a smart contract? I want to store document hashes in a smart contract as a prove of a document (eg pdf contract - could be large, dozones of MB) related to a blockchain transaction.

Is murmur3 128 hash functions a good choice for this?

murmur3 is not a cryptographic hash function, but it as difficult as with cryptographic functions to construct a document with same function which will make sense.

Actually, it's even worse than what Otus suggested; it's trivial to find a second-preimage; that is, given a message, it is easy to find a second message that hashes to the same value.  In fact, you can make the second preimage start with an arbitrary text, and so this is a practical (rather than just an academic) attack.

It's actually quite straight-forward; the state update function for MurMur3-128 is:

h1 ^= mixK1(k1)
h1 <<<= 27;
h1 += h2;
h1 = 5*h1 + constant_1;
h2 ^= mixK2(k2);
h2 <<<= 31;
h2 += h1;
h2 = 5*h2 + constant_2;

where h1, h2 are the hash state, k1, k2 are 128 bits from the current part of the message, and mixK1, mixK2 are invertible functions.

What we do is process the arbitrary preliminary text (which we're assume is a multiple of 16 bytes in length), this will result in some state h1, h2.

Now, what we do is find some 16 byte block k1, k2 that converts this state into a state that is obtained during the processing of the original message; once we have done that, we can append the rest of the original message, and that will result in the same hash as the original message.

Finding such a k1, k2 is quite straight-forward; we just work backwards through the above logic.  We start with the h1, h2 being the target values, and compute what the previous state is.  When we hit the h1 ^= mixK1(k1) and h2 ^= mixK2(k2) lines, those are (in the backwards direction) the last time we'll update h1 and h2, and so we just set mixK1(k1) and mixK2(k2) to be the values that'll give us the state after processing our chosen prefix.

Since mixK1 and mixK2 are invertible, that gives us K1 and K2, which are the 128 bit values we're looking for.

Note that this is somewhat different from the analysis by Jean-Phillip Aumasson, as he is actually tackling a harder problem.  He assumed a secret start state (and was able to find collisions); I'm assuming a known state state (and able to find second preimages)


Is it dangerous to encrypt lots of small files with the same key? I want to encrypt 1000s of old files on old hard drives before uploading them to the cloud. I'm planning to use AES-GCM with only one or a few keys. (I'm using Apple's CryptoKit library which provides this algorithm and a few others.) It would be convenient to encrypt and store the files individually, so I could download and decrypt them individually. Is this bad practice? I'm wondering if having many small examples of ciphertext could give an attacker an advantage.
A bit of background on my goals: I travel a lot and work with a laptop. Where some people would use an external drive, I want to use the cloud because 1) I don't want to be carrying around external drives, and 2) I want online storage in case of theft or damage to my devices.
I said "one or a few keys" because I don't want to store (in Keychain) or remember tons of keys. But if there is another way to generate multiple keys from a password or master key - appropriate to this situation - then I'd like to know about that.
I should break this into two sub-questions about two similar situations:
Situation 1: Lots of individual files, but no names or directory structures visible.
So an attacker sees a drive full of stuff like:

file0000001.enc             20 KB
file0000002.enc            123 KB
file0000003.enc         600 bytes
file0000004.enc             1.1MB
...

Situation 2: The directory structure, or maybe even file names, are preserved. So if something standard like an OS config directory were encrypted, the attacker would know some or all of the plaintext for some example files.
/personal-files/foo.txt   500K
...
/etc/http/httpd.conf       21K    -- a common file, could guess some or all of the plaintext
...

So, are either of these a problem? Or are they safe with AES-GCM (or a similar recommended algorithm)?

I'm assuming that the OP wants to access all files individually and updates or rollback to old versions, too.
The Cryptokit has only AES-GCM and ChaCha20-Poly1305.
Using the same key for all of the files is a dangerous path. Both AES-GCM and ChaCha20-Poly1305 are vulnerable in the case of (key,IV) reuse. For example,

if you encrypt the file $f$ with AES-GCM with the key $k$ and $IV_f$ to get $$(ciphertext,tag) = AES\text{-}GCM(k,IV_f,f)$$ and the file stored as $$IV_f \mathbin\|ciphertext\mathbin\|tag.$$ Where the IV's are unique for each file, otherwise you already in the pit of $(Key,IV)$ pair reuse.
Now, later you access the file and updated it. Used the same $k$ and $IV_f$. Now you gave an observer, not necessarily an active attacker, two files encrypted under the same $(key,IV)$ pair, the old version of the file and the updated). Now the confidentiality is lost or even more, an active attacker can make forgeries, too.

What are the options?

Continue to use the same key with a new IV.
You need to keep track of all of the used IVs and determine a new unique IV for every new file and whenever a file update. The better is;

Use a new key and new IV for each file and updates.
Generate a new random key and IV for a new file or update of a file to a fresh encrypt. How?
Get a master key $K_m$ and store it with a password manager like Keypass.

Using the file name and the update date and time of the file in the $$HKDF(K_{m}, fileName \|update)$$ can be a solution. However, there are traps here, too. The filename can be changed or you move the file into another location, the update information changed and you lost all!

The better one is using random information for each file like a 256-bit random bit as salt and use it together with HKDF. The HKDF can be used to derive multiple keys and even the IV. First, Extract a pseudorandom key (PRK) from the Initial Key Material (IKM) as $K_m$
$$PRK = \text{HKDF-Extract}(salt, IKM)$$
Then use the Expand with the additional info to arrive the Output Key Material (OKM) with the desired length $L$ and prefer AES-256.
$$OKM = \text{KDF-Expand}(PRK, info, L)$$
call it two times
$$File_{key} = \text{KDF-Expand}(PRK, \text{"KEY"}, 256)$$
$$File_{IV} = \text{KDF-Expand}(PRK, \text{"InitialValue"}, 96)$$ to derive the key and IV.
The IV size is 96 since GCM's recommended IV size is 96. During the update of the file, get a new random salt and use the HKDF again. The random salt can be generated /dev/urandom/ where available or in IOS SecRandomCopyBytes.
Store the file as;

$$Salt \mathbin\|IV \mathbin\|ciphertext\mathbin\|tag.$$

HKDF: HMAC-based Extract-and-Expand Key Derivation Function (HKDF) is defined in and proposed by H. Krawczyk and P. Eronen in May 2010 as RFC5969.

The age library
What we write above for developing a tool/library yourself. This has lots of pitfalls, too. Just consider the OpenSSL's evolution over time then it becomes almost unmanageable.
SAI-peregrinus made a comment about the age library. I've overlooked the library and saw that it is an active library and the developers are aware of the recent incoming attacks/problems and apply patches about them.
So instead of building your own library consider one that is well maintained and fit your needs.


Why does the recommended key size between symmetric and asymmetric encryption differ greatly? In various articles it is mentioned that for secure communications, the recommended key sizes are 128-bit key size for symmetric encryption (which makes it $2^{128}$ possible keys?) and 2048-bit key size for asymmetric encryption ($2^{2048}$ possible keys?).

Why do they differ so greatly? It seems like I am missing a very big part of the equation.

Symmetric encryption and asymmetric encryption algorithms are built upon vastly different mathematical constructs.

In typical symmetric encryption algorithms, the key is quite literally just a random number in $\left[0 .. 2^n\right]$, where $n$ is the key length. The strength of the key is based upon its resistance to brute-force attacks, where an attacker would need to perform an attack with complexity $O\left(2^n\right)$ to correctly guess the key.

Asymmetric algorithms, on the other hand, use a different kind of key. For example, an RSA modulus is of the form $m = pq$, where $m$ is the modulus, and $p$ and $q$ are two large, distinct, randomly-chosen prime numbers of roughly equal sizes. The strength of the key is based upon the modulus' resistance to factorization into its prime components. An attacker using a general field number sieve would need to conduct an attack with complexity $O\left(\exp\left(\left(\left(\frac{64}{9} + o\left(1\right)\right) \cdot n\right)^\frac{1}{3}\left(\log n\right)^\frac{2}{3}\right)\right)$ to factor the modulus (and thus break the private key), given a modulus of bit-length $n$.


Should we MAC-then-encrypt or encrypt-then-MAC? Most of the time, when some data must be encrypted, it must also be protected with a MAC, because encryption protects only against passive attackers. There are some nifty encryption modes which include a MAC (EAX, GCM...) but let's assume that we are doing old-style crypto, so we have a standalone encryption method (e.g. AES with CBC chaining and PKCS#5 padding) and a standalone MAC (e.g. HMAC with SHA-256). How should we assemble the encryption and the MAC?

MAC-then-Encrypt: Compute the MAC on the cleartext, append it to the data, and then encrypt the whole? (That's what TLS does)
Encrypt-and-MAC: Compute the MAC on the cleartext, encrypt the cleartext, and then append the MAC at the end of the ciphertext? (That's what SSH does)
Encrypt-then-MAC: Encrypt the cleartext, then compute the MAC on the ciphertext, and append it to the ciphertext? (In that case, we do not forget to include the initialization vector (IV) and the encryption method identifier into the MACed data.)

The first two options are often called "MAC-then-encrypt" while the third is "encrypt-then-MAC". What are the arguments for or against either?

I'm assuming you actually know all of this better than I do. Anyway, this paper neatly summarizes all these approaches, and what level of security they do or don't provide. I shall paraphrase it in English, rather than Mathematical notation, as I understand it.

Encrypt-then-MAC:

Provides integrity of Ciphertext. Assuming the MAC shared secret has not been compromised, we ought to be able to deduce whether a given ciphertext is indeed authentic or has been forged; for example, in public-key cryptography anyone can send you messages. EtM ensures you only read valid messages.
Plaintext integrity.
If the cipher scheme is malleable we need not be so concerned since the MAC will filter out this invalid ciphertext.
The MAC does not provide any information on the plaintext since, assuming the output of the cipher appears random, so does the MAC. In other words, we haven't carried any structure from the plaintext into the MAC.

MAC-then-Encrypt:

Does not provide any integrity on the ciphertext, since we have no way of knowing until we decrypt the message whether it was indeed authentic or spoofed.
Plaintext integrity.
If the cipher scheme is malleable it may be possible to alter the message to appear valid and have a valid MAC. This is a theoretical point, of course, since practically speaking the MAC secret should provide protection.
Here, the MAC cannot provide any information on the plaintext either, since it is encrypted.

Encrypt-and-MAC:

No integrity on the ciphertext again, since the MAC is taken against the plaintext. This opens the door to some chosen-ciphertext attacks on the cipher, as shown in section 4 of Breaking and provably repairing the SSH authenticated encryption scheme: A case study of the Encode-then-Encrypt-and-MAC paradigm.
The integrity of the plaintext can be verified
If the cipher scheme is malleable, the contents of the ciphertext could well be altered, but on decryption, we ought to find the plaintext is invalid. Of course, any implementation error that can be exploited in the decryption process has been by that point.
May reveal information about the plaintext in the MAC. Theoretical, of course, but a less than ideal scenario. This occurs if the plaintext messages are repeated, and the MACed data does not include a counter (it does in the SSH 2 protocol, but only as a 32-bit counter, so you should take care to re-key before it overflows).

In short, Encrypt-then-MAC is the most ideal scenario. Any modifications to the ciphertext that do not also have a valid MAC can be filtered out before decryption, protecting against any attacks on the implementation. The MAC cannot, also, be used to infer anything about the plaintext. MAC-then-Encrypt and Encrypt-and-MAC both provide different levels of security, but not the complete set provided by Encrypt-then-MAC.


Could a very long password theoretically eliminate the need for a slow hash? Before I provide details, I want to clarify that I am not looking to implement this practically, but I'm only asking to get a better understanding.

The way I currently understand it, we use slow hashes for passwords because there are too few possibilities in passwords. This means people could calculate all the potential passwords (or a whole lot of them) fairly quickly when using a performance hash, and find what made the digest. E.g. if in an imaginary world where digests are 3 bytes and slow hashes last a decade my password is "abb" and it results in digest "x3x", someone who got this hash could start retrieving my password by hashing "aaa", then "aab", then "abb" and see that the result is "x3x", and so my password must be "abb". With a slow hash, he wouldn't have time to calculate all three results.

This makes sense for short passwords, but I thought the strength in modern block ciphers lied in the key space. For Two-fish for example, it can have a key from any of 2^256 different variations. Trying all those variations would just be insane, and so it can't be done (for now).

Given these two things, wouldn't the strength of a performance hash as a password storage tool increase with each letter? Alphanumeric letters cover 32 to 127 in ASCII, so that's 6 bits entropy per character (I think). If that's true, would a password of 43 characters be secure when hashed with say, SHA 256?

Despite the impracticalities of using a 43-char password, I would say yes, such a long password would be secure when hashed with just SHA256.  Assuming 127 possible ascii characters, a password of 8 characters would require an attacker to search about 2^56 possibilites (viable), whereas a password of 43 characters would require searching about 2^300 possibilities (infeasible, considering that 2^128 for encryption using a 128-bit key is infeasible). Having such a long password would make a slow-hash redundant.  With the case of a 43-character password, I doubt that rainbow tables would be issue either.


Understanding the Pohlig-Hellman algorithm The paper has the following relation:
$$y^{(p-1)/p_i} \equiv \alpha^{x(p-1)/p_i} \equiv \gamma_i^x \equiv \gamma_i^{b_0} \pmod p$$

where $\gamma_i = \alpha^{(p-1)/p_i}$. I understand this relation and can show how each step is derived. However I'm stuck at the next step. From the paper:

  $\gamma_i$ is primitive $p_i$th root of unity. There are therefore only $p_i$ possible values for $y^{(p-1)/p_i} \pmod p$, and the resultant value uniquely determines $b_0$

What exactly does this mean and how do I get $b_0$ from $\gamma_i$?

Note that $\alpha$ is a primitive element in $GF(p)$ and $\gamma_i$ is a generator of a subgroup $G_i\subseteq GF(p)$ with order $p_i$, i.e., $G_i=\{\alpha^{(p-1)/p_i},\alpha^{2(p-1)/p_i},\ldots,\alpha^{p_i(p-1)/p_i}(=1)\}$. Since $y^{(p-1)/p_i}\in G_i$, there exists a unique value $b_0\in \mathbb{Z}_{p_i}$ such that $y^{(p-1)/p_i}=\gamma_i^{b_{0}}$. To compute $b_0$, you can for instance apply the baby-step giant-step algorithm.


Store hashed password using Digest authentication Digest Authentication is something like this:

Server sends client a nonce.
Client hashes username and password with nonce.
Client sends hashed value back to server.
Server validates hash.

However, it seems like this requires the server to have access to the password plaintext, otherwise it wouldn't be possible to verify each hash with unique nonce values.

Is there some way to follow this authentication protocol without requiring the server to have access to password plaintexts?

The server doesn't need the plaintext.  When the password was "saved" the server generated a nonce and concatenated that with the password and then hashed the combination.  The server saves the nonce and the hash, not the password.  Now, when client sends the hashed value to the server all the server does is compare that it against the saved value.