Birthday-attack calculation in planning password salting strategy The book Cryptography Engineering by Fergusun, Schneier, Kohno section 2.7.1 explains Birthday Attacks: "In general, if an element can take on N different values, then you can expect the first collision after choosing about sqrt(N) random elements." This is an approximation.

We are planning to upgrade the way we store password hashes and salts in our database. We need to allow for something on the order of 100 million salts, which is between 26 and 27 bits (two to the 26 or 27 power; I don't know how to format superscripts here). Taking the square that gets me to about 54 bits.

Seven bytes is 56 bits. Assuming that /dev/urandom is sufficiently random (evenly distributed and not predictable), do seven bytes of random salt meet the Birthday Attack criteria?

I realize this is not the only consideration in picking the salt. I'm trying to find out if I'm correctly applying the Birthday Attack theory.

EDIT: The final exercise at the end of the named book chapter asks the same question, which I can now answer confidently!

Yes! I'd recommend at least 64 bits, but that's only because powers of two are convenient and space is cheap. Furthermore, usually a salt of the block size of the hash you're using is usually best, because salting at all will almost always involve an extra block, so why not fill it up given that there will be no performance impact?

But once again, yes, you're correct in your analysis of the Birthday Problem.


Practical necessity of semantic security under chosen plain text attack (CPA) in CBC mode I was not able to understand why we practically need a CPA security in Cipher Block Chaining. (which insist on having a random IV), let say if the encryption is not CPA secure i.e , the adversary can identify two cipher-text are same and conclude the two plain-text would have been same. of what use this information is for adversary. i see he is able to know that both the message are same , so what? i think he can't find the plain-text.

In other words is CPA security is strictly a academic definition of security. Does in practice attacker can extract the plain text out of this?

Repeatedly encrypting the same message to the same ciphertext is full of practical attacks. Encryption is supposed to leak no information about the content of the message other than its length, and there are very real ways to exploit the information leakage you mention. Some of them have to do with the fact that plaintext domains are not always very large. Others have to do with the fact that an attacker who can perform a chosen plaintext attack (CPA) gets to learn a lot about the ciphertext.

Here are some attacks, assuming that we use a CBC-like encryption scheme that is deterministic (and thus not semantically secure):

If the attacker sees the encryption of message A, then later learns message A, he can then know the contents of message A whenever it was sent in the past or the future. That's a very real threat if the total messages that could be sent are reasonably small.

Example: Consider an army that coordinates movement by sending instructions to each other on who is to move where. The attacker might be able to catalog intercepted encrypted communication and then determine what the message meant based on what happened after it was sent. When a duplicate message is intercepted, they will know that what happened the last time the message was sent and thus what is likely to happen this time the message is sent.

Plaintexts that begin the same way will have ciphertexts that begin the same way. Even if two ciphertexts don't match, some prefix of them may match. If they do, knowing the contents of one ciphertext can lead to knowing the beginning of another ciphertext. While this isn't much different than the previous case, it means that the problem is much worse than simply having ciphertexts that are the same, it extends to ciphertexts that begin the same way.

Example: Consider a style of document with a person's (Alice) identifying information at the beginning. Even if two document contents differ, the attacker will still know the documents belong to the same person. If Alice ever sends the attacker one document, he learns how to identify a document encrypted by her. If one of those documents is recovered from another person's (Bob) computer, the attacker learns that Alice likely communicated with Bob. Information about the content of the the document is expected to remain confidential under encryption, failing to do so is a failure for the encryption.

It's also possible that the small domain of the plaintext will pair with the context of the ciphertext and reveal information.

Example: Consider a program like SSH that transmits what a user types, sending small sets of encrypted key strokes at a time. We would have limited number of possible ciphertexts because every key maps to the same ciphertext each time. If every set of messages is stand alone (no ciphertext chaining across gaps in key strokes), then an attacker could use frequency analysis to determine which ciphertext mapped to which keys. They could then do a decent job of learning what the user had typed. It would be even worse if every message were stand-alone, in which case it would be ECB. (In case it wasn't obvious, note that deterministic CBC has a similar taste to ECB.)

The attacker may be able to inject chosen plaintext into a live system and see the resulting ciphertext. (This is a very real attack that we must be able to withstand and motivation for why we consider chosen plaintext attacks.) He can then brute-force decrypt other ciphertext by simply finding plaintext that encrypts to the known ciphertext. The smaller the plaintext domain, the easier this is.

Example: A bank may encrypt the amount of money involved in a transaction in one block of the ciphertext. The attacker may be able to conduct his own transactions and determine what numbers encrypt to what ciphertexts, then be able to learn about other ciphertexts.

(Obviously, the specific players in those examples are arbitrary, you could swap them out for any number of other situations.)

The main problem is that we don't know how messages are going to be formatted and what kind of content it will contain, and it's very possible to pick formatting and content that will leak information through the encrypted ciphertext. Encryption is supposed to do it's job of protecting all information you give it, and leaving some edge cases vulnerable and telling the user that they're only secure if they take extra precautions to avoid those edge cases isn't acceptable. Nobody wants to use something that is insecure for edge case (especially not when there's the option of eliminating those edge case vulnerabilities). It would be like your house being stable for everything, except if you slam the bathroom door the kitchen ceiling falls in. Who'd want that?


Is this formula/problem hard to crack? I have a simple calculation. Its inputs should be very hard to discover, but I want to be certain, hence the question.
Start with value $A$, a known 1024-bit number.
Input $I_1$ and $I_2$ are 512-bit numbers, and their hashes are known as $h_1 =Hash(I_1),  h_2=Hash(I_2)$.
Output $O$ is the result of $O=(A\cdot I_1)+I_2$.
Given $A,O,h_1$, and $h_2$, is it feasible to brute force $I_1$ and $I_2$?

$$O=(A\cdot I_1)+I_2$$
Take $\mod A$ of the equation.
$$O \bmod A=\left( ( A\cdot I_1)+I_2 \right) \bmod A = I_2 \bmod A$$
So we get the $I_2$. the rest is substructing the $I_2$
$$O - I_2 = A\cdot I_1$$ and the final is simply dividing by A.
$$I_1 = \frac{O - I_2}{A} $$
The given $h_1$ and $h_2$ are not used! One may argue to use the hashes to identify the multiple solutions, however, the Euclidean division says they are unique since $A$ is a 1024-bit number and $I_i$'s are 512-bit numbers.


CBC-MAC , fixed length, all blocks returned CBC-MAC, with fixed length message.

Is it safe to return all ciphered blocks instead of the last?

My intuition says it is less secure, since is gives an attacker more information.
But how could one attack this scheme?

I'll assume All ciphered blocks means the same as ciphertext for CBC-Encryption with implicit zero IV, while CBC-MAC is the last block of that.

All ciphered blocks is unsafe as a message authenticator for messages longer than one block, for it succumbs to a trivial attack (here with two blocks):

Eve intercepts message $M=M_0||M_1$ and its authenticator $A=A_0||A_1$
she knows $A_0=E(M_0)$ and $A_1=E(A_0\oplus M_1)$
she builds $M'=(A_0\oplus M_1)||(A_1\oplus M_0)$ and its authenticator $A'=A_1||A_0$.

The verifier will then accept as valid $M'$ and its authenticator $A'$ just as well as $M$ and its authenticator $A$.

Addition for completeness: $M'\ne M$ unless $M_1=M_0\oplus E(M_0)$, which is extremely unlikely to occur by chance.


The REACT transform and Replayable CCA Before stating my questions, let us recall the REACT transform [OP01], which enables to construct a CCA-secure hybrid PKE scheme, $\varepsilon'_{pk}$, from an OW-CPA PKE scheme $\varepsilon_{pk}^{asym}$, an IND-secure symmetric encryption scheme $\varepsilon^{sym}$, and hash functions $H$ and $G$. The transform works as follows:

$c_1 = \varepsilon_{pk}^{asym}(R), c_2 = \varepsilon_{K}^{sym}(m)$, where $K = G(R)$ and $R$ is chosen at random.

Then $\varepsilon'_{pk}(m) = (c_1, c_2, H(R,m,c_1,c_2))$

My questions are: Why is it necessary to include $c_1$ in the hash $H$? What would be the consequences of dropping it from the hash (i.e., $\varepsilon''_{pk}(m) = (c_1,c_2, H(R,m,c_2))$? I guess that the main reason is to achieve non-malleability, but is it possible that by dropping it we obtain a transform to Replayable CCA (RCCA) security [CKN03]? Informally, RCCA was like CCA security “except that they
allow anyone to generate new ciphertexts that decrypt to the same value as a given ciphertext” [CKN03]. Since we are including $m$ in the hash, we can guarantee that the original message is preserved, but we allow modifications on $c_1$.

I am asking this because I'm interested in schemes where a certain degree of malleability is permitted. In particular, re-encryptions of the original ciphertext are permitted, as long as they decrypt to the original message.

References:

[OP01] Okamoto, T., & Pointcheval, D. (2001). REACT: Rapid enhanced-security asymmetric cryptosystem transform. In Topics in Cryptology—CT-RSA 2001 (pp. 159-174). Springer Berlin Heidelberg. $\rightarrow$ PDF
[CKN03] Canetti, R., Krawczyk, H., & Nielsen, J. B. (2003). Relaxing chosen-ciphertext security. In Advances in Cryptology-CRYPTO 2003 (pp. 565-582). $\rightarrow$ PDF

I believe it would match the relaxed RCCA security, but it looks like it wouldn't be of much use because reencryption would not be secure.  You could generate reencryptions of any ciphertext, but they would not be indistinguishable from each other, i.e. given $c_1$ and $c_2$ you can determine easily whether $c_2$ is a reencryption of $c_1$.


Are SHA-256 and SHA-512 collision resistant? This is my first post on this forum, apologies if this post is naive. I want to learn cryptography and I want to start with this question.
Context: Designing a TinyUrl system. The user inputs a lengthy URL and the system computes the hash and encodes it binary64 and sends it back to the user.
From what I understood so far (from this forum and also from Wikipedia) that SHA-2 algorithms are not collision-free. If these functions are indeed not collision-free, how to make them collision-free?  There are resources on the internet that recommend adding jitter, for example, a unique string at the beginning of the URL, a viable solution in software systems design. This not only makes the different URLs produce different hashes, but it also makes the same URL produces 2 different hashes on 2 different tries (presumably for 2 different users). In the reverse lookup, the system can ignore the prefix and redirect the user to the original URL using HTTP 302. However, this adds its own complexity to the system that is generating/using unique prefixes across different servers of a distributed system.
Question-1: What are the chances that 2 different strings/URLs produce the same hash when used SHA-256 or SHA-512?
Question-2: Assuming that the system saves 30billion URLs their hashes in database, what is a recommended hashing function, if not SHA-2? Please note that a requirement of the system is it should be highly available, meaning: hash computation should not take very long.
Appreciate any help. Thanks in advance!
PS: Happy to get started with cryptography.

Cryptographic hash functions by design cannot be collision-free since they operate on arbitrary-sized input to fixed-sized outputs like 256 for SHA-256 and 512 for SHA-512. $$H:\{0,1\}^* \to \{0,1\}^b$$ where $b$ is the $H$'s output size.
By the pigeonhole principle, collisions are inevitable. Simply consider 100 holes and 101 pigeons. With this condition when the pigeon placed on the hole, there must be at least one hole more than one pigeon.
This doesn't mean that one can find a collision very easily. For SHA-256 you need around $2^{128}$ inputs to see at least one colliding pair with 50% probability. For SHA-512 that is $2^{256}$. This is due to the generic birthday attack that has cost $\mathcal{O}(2^{n/2})$ with 50% for $n$-bit output hash function. Those numbers are huge to be considered. For example, the collective power of the Bitcoin Miners can reach $~2^{93}$ SHA-1 hashes per year. This means that they need 2^{37} years to find one with 50%.
We don't try to make them collision-free, we live with it by knowing the boundaries.
Currently, neither for SHA-256 nor SHA-512 there is a collision attack better than the generic collision attack. There are attacks on the reduced rounds, however, this simply indicates that better than generic is hard! We will be surprised that one can find two inputs colliding. This happened on MD4 even randomly. MD5 collisions are trivial and SHA-1 has been shattered. Don't confuse that those are not secure hash functions even in the early 2010s.

What are the chances that 2 different strings/URLs produce the same hash when used SHA-256 or SHA-512?

If we model the SHA-256 uniform random then $1/2^{256}$. This is a simple probability; the first element can get any position then the second element has $1/2^{256}$  probability to hit the first one.

Question-2: Assuming that the system saves 30billion URLs their hashes in database, what is a recommended hashing function, if not SHA-2? Please note that a requirement of the system is it should be highly available, meaning: hash computation should not take very long.

30 billion URL ($\approx 2^{32.48}$ URL ) have the probability of collision;
$$(2^{32.48})^2/2^{256}/2 = 2^{69.6 - 256-1} \approx 1/2^{187.4}$$
We call an event is-not-gonna-happen if it has probability $<\frac{1}{2^{100}}$. You can use any 512-bit cryptographic hash function like SHA-512, SHA3-512, and BLAKE2b without fear of collision.  You may look at BLAKE2b quite fast compared to alternatives and its parallel version BLAKE3.

Are SHA-256 and SHA-512 collision resistant?

Yes, currently as of 2021 and in the near future, yes.


Using Pedersen commitment for a vector I'm reading Bootle/Groth. I'm trying to understand how they are committing to a vector using Pedersen commitment. Here's my understanding of Pedersen commitment in the context of this paper:

We have a group $\mathbb{Z}_p^*$, $g$ as a generator.
The generator produces random group elements $(g_1,\dots,g_n,y)$.
We commit to the vector $\vec{m} = (m_1,\dots, m_n)$ by choosing $r$ randomly from $\mathbb{Z}_p^*$ and then $c = Com(\vec{m};r)$ is $c = y^r \prod_{i=1}^n g_i^{m_i}$.

The paper goes on to describe how $\vec{m}$ is actually a row of coefficients in a polynomial, and the verifier may send an input $x$ to be evaluated (without finding out what the polynomial is!). What I am wondering, though, is:

Does my understanding of this scheme make sense?
If so, what makes this scheme (computationally) hiding and binding? I don't know how to walk through a proof of this.

Yes, you got the scheme essentially right - except that the group cannot be $\mathbb{Z}_p^*$, as the latter does not have prime order. It can however be many other things - like the multiplicative subgroup of squares over $\mathbb{Z}_p^*$, or an elliptic curve. Let us simply consider the scheme as you described it, over some group $\mathbb{G}$ of prime order $p$.

Why is the scheme hiding?

Intuitively, the scheme is perfectly hiding because for any commitment $c$, and for any tuple $(m_1, \cdots, m_n)$, there exists an opening $r$ that "explains" $c$ as $c = y^r\prod_{i=1}^n g_i^{m_i}$, and the distribution of this $r$ (taken over the coins used to generate $c$) is uniform.

More formally, denoting $a\gets_r S$ the action of drawing $a$ uniformly at random from $S$, the commitment scheme is perfectly hiding because for any pair of tuples $(m_1, \cdots, m_n)$ and $(m'_1, \cdots, m'_n)$, the distributions $$D = \left\{c : r\gets_r\mathbb{Z}_p, c \gets y^r\prod_{i=1}^n g_i^{m_i}\right\} \text { and } D' = \left\{c : r\gets_r\mathbb{Z}_p, c \gets y^r\prod_{i=1}^n g_i^{m'_i}\right\}$$ are perfectly equal. This is easy to show: for $i=1$ to $n$, let $\alpha_i$ denote the exponent of $g_i$ in base $y$ (id est, $g_i^{\alpha_i} = y$). Let $\alpha \gets \sum_{i=1}^n \alpha_im_i$ and $\alpha' \gets \sum_{i=1}^n \alpha_im'_i$.

Then $c$ is computed as $y^r\prod_{i=1}^n g_i^{m_i} = y^{r+\alpha}$ in $D$ (for a random $r$), and as $y^r\prod_{i=1}^n g_i^{m'_i} = y^{r+\alpha'}$ in $D$ (for a random $r$). The equality of the distributions is therefore immediate.

Why is the scheme binding?

We can show that the scheme is binding under the discrete logarithm assumption. Let $\mathcal{A}$ be a PPT adversary which, given the parameters of the system (in this case, $(y,g_1, \cdots, g_n)$) can produce (with non-negligible probability $\varepsilon$) a commitment together with valid openings to two different plaintexts, id est: $(c,(m_1, \cdots, m_n),r,(m'_1,\cdots, m'_n),r')$, where $c\in\mathbb{G}$ is a commitment, $(m_1, \cdots, m_n) \neq (m'_1, \cdots, m'_n)$, and $$c = y^r\prod_{i=1}^n g_i^{m_i} = y^{r'}\prod_{i=1}^n g_i^{m'_i}.$$

Let us use this algorithm to break the discrete logarithm assumption with non-negligible probability. Upon receiving a random discrete-log challenge $(g,y)$, we pick $i$ at random between $1$ and $n$, and set $g_i \gets g$. Then we pick $n-1$ values for $\alpha_j$, $(\alpha_j)_{j\neq i}\gets_r \mathbb{Z}_p^{n-1}$ and set $g_j \gets y^{\alpha_j}$ for any $j\neq i$. Observe that $(y, g_1, \cdots, g_n)$ is perfectly distributed as a valid tuple of parameters for the Pedersen commitment scheme. Therefore, we run $\mathcal{A}(y,g_1,\cdots, g_n)$ and obtain $(c,(m_1, \cdots, m_n),r,(m'_1,\cdots, m'_n),r')$ where it holds with probability $\varepsilon$ that $(m_1, \cdots, m_n) \neq (m'_1, \cdots, m'_n)$ and $c = y^r\prod_{j=1}^n g_j^{m_j} = y^{r'}\prod_{j=1}^n g_j^{m'_j}$. We check whether $m_i \neq m'_i$, and restart the protocol otherwise. Note that as our (uniformly random) choice of $i$ is perfectly hidden from $\mathcal{A}$, and as $(m_1, \cdots, m_n) \neq (m'_1, \cdots, m'_n)$ with probability at least $\varepsilon$, it holds that $m_i \neq m'_i$ with probability at least $\varepsilon/n$.

Let $\alpha \gets \sum_{j\neq i} \alpha_j m_j$ and $\alpha' \gets \sum_{j\neq i} \alpha_j m'_j$. If $m_i \neq m'_i$, we therefore have the following:

$y^r\prod_{j=1}^n g_j^{m_j} = y^{r'}\prod_{j=1}^n g_i^{m'_j}$

hence $y^r g^{m_i}\cdot y^{\alpha} = y^{r'} g^{m'_i} y^{\alpha'}$

hence $y^{r-r'+\alpha-\alpha'} = g^{m_i-m'_i}$, with $m_i - m'_i \neq 0$

hence $y^{(r-r'+\alpha-\alpha')\cdot(m_i-m'_i)^{-1}\bmod p} = g$: we obtain the discrete log of $y$ in base $g$.

Therefore, if $\mathcal{A}$ breaks the binding property of the Pedersen commitment scheme with probability at least $\varepsilon$, we can construct an algorithm which, given access to $\mathcal{A}$, extracts the discrete logarithm of $g$ in base $y$ with probability at least $\varepsilon/n$.


Zero knowledge of two factor Here I overconfident in myself state that I can show, that n has two factors.

This is not completely true, can possibly show $n$ is composite - prover generates RSA key with modulo $n$, and gives $e$ to verifier.

Verifier takes random number $x$, and checks if $x^{e*d}=x$, where $d*e=1$ (mod  $n-1$). If it is, then $n$ is prime, if not $n$ is composite and has factors.

Verifier sends $x^e$ to prover, and if prover sends back $x$ we can be sure that prover has factors of $n$. This doesnt, however garanties that there is just two factors.

How to prove-verify that there is only two factors in $n$?

UPDATE: This is not zeroproof, it is interactive here as was pointed in comments. Well, then. Question becomes more broader - can (duh) show that $n$ is not a prime. How to show it has two factors, zero knowledge, without interactivity?

Firstly, convince the verifier that $n$ is not a prime number. (Prime is in P)
Use Zero-Knowledge Proof to make sure that $n$ has no square factor (no $p^2|n$)

See this paper Practical zero-knowledge proofs: Giving hints and using deficiencies for details.
Showing that $n$ has exactly two factors: if not, the number of quadratic residues is roughly less than $1/8*n$. Verifier just randomly chooses a value y and ask prover to prove whether y is quadratic residue.

If the probability is roughly $1/4$, then accept.
Verifier can't cheat since he can only compute the quadratic residue, and let the probability raise, but not decrease below $1/8$.


What cryptographic protocol or algorithm I can use to encrypt/decrypt a subset of columns of a database table for each user? What cryptographic protocol or algorithm I can use to encrypt/decrypt a subset of columns of a database table for each user?

For example say I have a database table with 50 columns

col1, col2, col3, col4......col50

Now I want to reveal the data such that

user1 can see (have access to) col15 and col17 only  at time t1 and
user2 can see (have access to) col7, col9 and col20 only  at time t1
user3 and user4 can both see data only in col40 at time t1.
user1 can see (have access to) col24 only (which means access to previously assigned col15 and col17 will be disabled) at time t2
user1 can have access to additional column say col 42 at time t3. so At time t3 user1 has access to both col24 and col42

I am thinking if I can issue tokens to users such that each token would hold access to set of columns in a database table or something like that.

What kind of efficient protocol or algorithm I can use to construct such scheme ?

My scalability requirements

At most I will have is probably 1000 columns (maximum)
I can have millions or billions of users. Algorithms than can scale for millions is also ok

A solution using attribute-based encryption

You could solve the problem you pose relatively elegant using attribute-based encryption (ABE; cf. [1]). For example, using a ciphertext-policy ABE you could do the following. Let {col1, col2, ..., col50} be the universe of attributes and, for each user, assign a key with respect to the attributes she is allowed to access. To take your example user1 would get a key with respect to {col15, col17}. Each column is then encrypted with respect to its column attribute so that every user who is in possession of a key with the respective attribute can decrypt the column.

An alternative solution

Since it seems that the number of columns you want to encrypt is rather small you could also use an alternative approach known as hybrid encryption: you choose a symmetric encryption scheme and encrypt each column under a separate key. Additionally you use an asymmetric encryption scheme which is used to encrypt the respective symmetric keys for the users who have access to a certain column. Let $k_1, \dots, k_{50}$ be the symmetric keys used to encrypt column 1 to column 50, then - again taking your example - you would encrypt $k_{15}$ and $k_{17}$ under the public encryption key for the asymmetric encryption scheme of user 1.

Scalability requirements

Since the number of columns is relatively small (< 1000), I think that both solutions above should perform well. Note that for the second solution the size of the ciphertexts which are handed to the users are of linear size in the number of columns. Using the ABE approach you will be able to get constant size ciphertexts (depending on the used ABE), but this will come at the cost of more expensive encryption and decryption. So choosing one of those two approaches can be viewed as choosing a trade off between ciphertext size and efficiency.

References

[1] What is Attribute Based Encryption?


Does it necessarily mean that an RSA moduli generated with poor randomness is not random? In 2012 a group of researchers collected a large amount of RSA moduli and calculated their greatest common divisor in order to find common factors between them. By finding a common factor they could the divide and completely factorize the key. They concluded that the vulnerable moduli where generated by PRNGs with inadequate randomness.
Does it necessarily mean that those key are not random?

If each key was generated by selecting two random primes of the desired length then the chance of two keys with a common prime would be incredibly small. If i'm reading How are primes generated for RSA? correctly there are about 2^502 possible 512 bit primes (prime length is half modulus length, so a 1024 bit RSA key would use 512 bit primes).

Since keys have been found which share a prime and the chance of that happening with randomly selected primes is so incredibly small the only reasonable conclusion is that the primes were not selected randomly.


Whether this PRG is secure or not This is the question.

Suppose $G$ is a secure PRG with expansion factor $\ell(n) = 2n$ such that $n$ is a security parameter.
Is it always the case that,
$G'\colon \lbrace 0,1 \rbrace^n \to \lbrace 0,1 \rbrace^{3n}$,
defined by, $G'(s) := G(s) || \bar{s}$ is also a PRG ?
Here, $||$ represents concatenation of bit strings, and $\bar{s}$ represents the bitwise complement of s (e.g., if $s$ is $100010$, then $\bar{s}$ is $011101$).

My unsure attempt of solving this says it is a broken PRG (i.e. not secure) because, I always check on following points for a construction to be a secure PRG:
.. $\ell(n) > n$,
.. efficient,
.. deterministic, &,
.. pseudorandom, i.e., $| Pr[D(G(s) = 1] - Pr[D(r) = 1] | \leq \operatorname{negl}(n)$.

And the construction in question failed in passing the pseudorandomness.

My attempt was, let's say $w$ is final output (of $3n$ size, which is given to the distinguisher) and I leaked the first bit of my construction (i.e., only $n-1$ bits i.e., $s[2:n]$, are passed into G and are expanded to $2n-1$ bits) such that first bit of $w$, i.e., $w[1]$ is complement of $w[2n+1]$ (because last $n$ bits are simply concatenated and $2n+1$ refers to the first bit among the last $n$ bits).

XORing $w[1]$ with $w[2n+1]$ gives us $1$ which clearly depicts inefficient randomness and failure of computational adversarial indistinguishability (i.e., ability to guess bits better than a probability of $1/2$ exist).

I'm unsure whether this is the right approach though.
When we are talking about PRGs, my knowledge says we cannot modify/control the seed (nor we can see it, though we control its size), and then we know that $G$ will output $2n$ bits (i.e., an expansion factor of $2|s|$).
Is it possible to explicitly only send $s[2:n]$ bits to a PRG to get the expanded $2n-1$ bits back and then attach that first bit in the starting of the pseudorandom string ?.

What's your verdict towards my approach ?. Thank you, for your time &, I really liked you read it.

I have another explanation that proves $G'$ is secure, however, I'm sure with a probability of 50% that, that is not right and rather this is right (i.e. $G'$ is not secure).

Your intuition that $G'$ is insecure is correct, but your approach is a bit off. In the PRG security game, the adversary is not allowed to influence the choice of seed, which is always chosen uniformly at random.

To attack $G'$, notice that given just $G'(s)$, you can reconstruct $s$ from $\bar{s}$. Therefore a distinguisher, when given a challenge output $w$, can compute $G'(\bar{w}[2n+1] \cdots \bar{w}[3n])$ and check whether this gives $w$.


Link between openssl 'req' command and 'unable to get local issuer certificate'? I was using the following command to build a self-signed certificate after creating a private key:

openssl x509 -in "server.csr" -out "server.crt" -req -signkey "myprivate.key" -days 365

After some ensuing troubles, and lots of googling I cobbled together a script, which culminated in:

openssl req -config ${CONFIGFILE} -new -x509 -sha256 -newkey rsa:2048 -nodes -keyout "server.key" -days 365 -out "server.crt"

How does this work, given I'm no longer passing it my "myprivate.key" to actually self-sign the cert?

Is "server.key" now being used to do the signing, and do I need to somehow combine this new key with the original "myprivate.key" to create a keychain? I ask since commandline tools don't seem to like the resulting certificate (e.g. curl says: 'SSL certificate problem: unable to get local issuer certificate').

Your second command generates a new RSA key and writes it in server.key, along with the self-signed certificate in server.crt.


Why is SHA3 prefixed with SHA despite the fact that it is structurally different from SHA2 and SHA1? Why is SHA-3 prefixed with “SHA” despite the fact that it is structurally different from SHA-2 and SHA-1?

SHA-0, 1 & 2 and MD5 is based on Merkle–Damgård construction, while SHA-3 falls under Sponge functions.

Therefore why SHA-3 is still prefixed with “SHA” despite the fundamental difference in its construction?

SHA3 is the name of the hash function standard, and the acronym is for 'Secure Hash Algorithm', pretty neutral one saying nothing about the structure.  The algorithm itself was originally named Keccak by the developers.  After winning the SHA3 competition, Keccak became SHA3.


DSA signatures with related k and unknown payloads Suppose that we are given DSA parameters $p$, $q$, $g$, a public key $y = g^x$, and two signatures $(r_1,s_1)$ and $(r_2,s_2)$. We are told that $(r_1,s_1)$ and $(r_2,s_2)$ were produced by related nonces $k_1 = k$ and $k_2 = k+1$, but we do not know the value of $k$, and we do not know the messages.

(In practical terms: the PRNG is broken, but it's somehow well-seeded, and we can't submit any messages for signing. We cannot guess the contents of the messages, e.g. they're encrypted with a secret key.)

So we know
$$ \begin{array}{lll}
  r_1 = (g^k \bmod p) \hphantom{(g\cdot{})} \mod q &&
  s_1 = k^{-1} (h_1 + x \, r_1) \hphantom{{}-s_2} \mod q \\
  r_2 = ((g \cdot g^k) \bmod p) \mod q &&
  s_2 = k^{-1} (h_2 + x \, r_2 - s_2) \mod q \\
\end{array} $$
but we don't know the $h_i$. Can we find the private key?

Does it help to have more (but $\ll q$) known signatures made with $k+2, k+3, \ldots$ (but with unknown messages)?

(Inspired by Attack on DSA with signatures made with k, k+1, k+2)

If the messages are unknown, there are no two messages $m_i, m_j$ such that $m_i = m_j$ and the messages have sufficiently high entropy (which might be shared across several messages, if the hash function is a CSOWF and the messages e.g. have low entropy unique sub strings or are made unique in some other way), and the underlying hash function is secure in a random oracle model and has an output bit length equal to or greater than $2n$ such that $q \lt 2^n$ (see below), then this scheme is secure in this hypothetical scenario.

Firstly, note that

$s_i \equiv h(m_i)/(k+i) + xr_i/(k+i) \pmod q$

Case #1 - large untruncated hashes (non-DSA compliant)

Suppose we give the adversary oracle access to the first term of the right hand expression

$h^\prime_i = h(m_i)(k+i)^{-1} \mod q$

Define the adversary $A_h$ such that $i$ is fixed, and that $A_h$ might submit any $j \ne i$ to the oracle and get the corresponding $h^\prime_j$ value. Then $A_h$ submits $i$ and gets either $h^\prime_i$ or $z \leftarrow_{uniform} \mathbb Z_q$. $A_h$ might continue to submit any queries to the oracle subject to the first constraint that $j \ne i $. If the function $h(m)$ and the $m_i$ messages have the assumed properties, $A_h$ will have but negligible probability of succeeding.

As noted, the assumption about the uniformity of $h(m)$ is problematic if the underlying implementation conforms to FIPS 186-3 with the only exception of the way the randomizer values are generated. Since FIPS 186-3 prescribes that the left most $n = |q|$ bits of $h(m)$ are used, we will get a clear bias with $h(m) < 2^n-q$ being twice as probable than $2^n-q \le h(m) < q$. However, if the hash output is at least $cn$ and is not truncated before being reduced $\mod q$ this bias will be at most $2^{-n(c-1)}$

Secondly, note that we now have

$s_i = h^\prime_i + xr_i(k + i)^{-1} \mod q$

Define the adversary $A_s$ such that $A_s$ might adaptively submit any $j$ subject to the same conditions as above. When $A_s$ submits $j = i$, the oracle returns either $s_i$ or $w \leftarrow_{uniform} \mathbb Z_q$. $A_s$ might then continue to submit queries as above.

Now, note that for any $w$ and $i$ there exists a value $z_{w,i}$ such that

$w = z_{w,i} + xr_i(k + i)^{-1} \mod q$

Hence, if the adversary $A_s$ is able to tell if the $s$-oracle returned $w$ or $s_i$, we have a distinguisher for $A_h$ as well, by noting that $A_s$ is able to tell $z_{w,i}$ from $h^\prime_i$.

Case #2 - truncated or equisized hashes (DSA compliant)

If the hash output is exactly $n$ bits in length, there will be a significant bias in $h(m) \pmod q$ as noted above. Given the other assumptions regarding the messages and the hash function, we might assume this is the only bias we have to consider. However, presuming $q$ is a uniform prime in the range $2^{n-1} \lt q \lt 2^n$, multiplication by $(k+i)^{-1} \mod q$ will mask this bias to some extent. Given that both terms of the right hand expression share this factor, the above proof is not valid in this case. Intuitively, though, the combined (and theoretically detectable) bias of $h(m_i) + xr_i$ ought to be masked to some reasonable extent by the $(k+1)^{-1}$ factor sequence, as long as the total number of signatures is not large enough.


Quorum-based encryption The task

Encrypt data in a way that a freely choosable quorum of n people out of a group of m participants are required to decrypt that data.

It is not necessary to have to fulfil the quorum to encrypt data.

What crypto systems and algorithms exist that solve this task?

Example: A poor solution that does the trick

A method that seems obvious but scales poorly, is to create a separate ciphertext for each permutation of n people, creating m keys and encrypting each plaintext-copy n times with n different keys.

m = 4, n = 3

ciphertext1 = m( m( m( plain, keyA ), keyB ), keyC )
ciphertext2 = m( m( m( plain, keyA ), keyB ), keyD )
ciphertext3 = m( m( m( plain, keyA ), keyC ), keyD )
ciphertext4 = m( m( m( plain, keyB ), keyC ), keyD )

Downsides:

This requires a single point of trust. Whereever the plaintext is encrypted, all keys have to be known as well.
It does not scale. The effort in storing and distributing keys and ciphertext is very high. Furthermore the encryption function needs to be called m*n times

A slightly better variant would use the scheme above and instead of encrypting the payload, an encryption key that works on actual data would be encrypted instead.
 This removes the need to perform the encryption operation on the payload multiple times and to store multiple copies of the encrypted payload.

This sounds exactly like secret-sharing. Briefly, you can secret share a secret key $sk$ in a k-out-of n fashion where the corresponding public key $pk$ is known by everyone.

Then, everyone can encrypt a message $m$ to a ciphertext $c$ using the public key yet, only a quorum of size $k$ can decrypt $c$.

In particular, this kind of secret sharing can be done without any central party by running a distributed key generation algorithm (DKG) among participants.


$\ell_2$-norm vs canonical embedding norm on ring-lwe Ring-LWE based encryption (I pick up homomorphic encryption here) requires canonical embedding norm rather than $\ell_2$ norm to quantify the polynomial  size (e.g. noise).

Why is this better than $\ell_2$ norm?

Isn't $\ell_2$ norm always be correct?

Canonical embedding is just a embedding which maps a ring element to a complex element by evaluating the original polynomial by complex $n$-th roots of unities, where $n$ is the degree of base polynomial.
Canonical embedding norm is taking a maximum of the complex numbers (Since we evaluate a polynomial by $n$-distinct complex root of unities, we have $n$-dimensional vector, i.e. point-value representation of the original polynomial).

I think you are mixing up some concepts... There are two things here: the embedding and the norm.
Those schemes are defined over polynomial rings, but for several reasons (e.g. to relate them with lattice problems, to have some geometry) we want to analyze them in vector spaces.
So, representing those ring elements as vectors is what we call embedding. There are several ways to embed them. For instance:

"The naïve way": just represent a polynomial $p(x) = \sum_{i=0}^n a_i$ as a vector $\vec{p} = (a_0, a_1, ..., a_n)$;
The canonical embedding: For $1 \le j \le n$, define the isomorphism $\sigma_j$ from $\mathbb{Q}[x] / \langle \Phi_m(x) \rangle$ to $\mathbb{C}$ as $x \mapsto \zeta^j$, where $\zeta$ is an $m$-th root of unity in $\mathbb C$. Then for any polynomial $p(x) = \sum_{i=0}^n a_i$, associate the vector $\vec{p} = (\sigma_1(p), \sigma_2(p), ..., \sigma_n(p)) \in \mathbb{C}^n$.

Once you have an embedding, you can just use the norms as usual, because you are working on a vector space. And that is what papers usually do: they use the $\ell_2$ and the $\ell_\infty$ norms after choosing one method to embedding elements.
Therefore, what you are calling canonical norm is just the usual $\ell_2$ or $\ell_\infty$ on vectors obtained by the canonical embedding.
Maybe what is tricking you is "why to use the canonical embedding instead of the naïve one?". If this is the case, I suggest that you read at least the introduction and the section 2 of A Toolkit for Ring-LWE Cryptography.


Simplied DES why 10-bit key? In Simplified DES algorithm, the plain text is 8-bit & the key is 10-bit, why is that, why can't both be of 8-bits each?

If you're talking about the S-DES developed by Professor Edward Schaefer of Santa Clara University, I can try to explain you the reason.

The algorithm takes in input a 10-bit key (K) but, using a key generation algorithm, the plaintext is encrypted using two different subkeys (K1 and K2) that are generated by the algorithm.

First, you should pass the 10-bit key through a permutation phase.

To generate K1 follow the following steps:

split the key in two binary string with the same length
pass to a simple left shift function (shift=1) both the keys and then join them again
pass the key (still 10 bits long) through a reduction-permutation function(P8) that simply picks out and permutes 8 of the 10 bits.
The P8 function works according to the following rule: 6 3 7 4 8 5 10 9

An example: assuming that the output of the left shift functions is the 10-bit key 0000111000, then the output of P8 function would be 10100100.

The output of (3) is K1, the key that will be used during the first round of the encryption procedure.

Now, to find K2 the procedure is practically the same:

the input to (1) is not the initial key (K) nor K1, but it is the 10-bits key that comes from the left shift function used to find K1. Thus, after you've splitted this key in two equal length substrings, pass them through the left shift function (shift=2). Note the different shift value
after you've joined the substrings again, pass the resulting 10-bits key to the P8 function to get K2.

Note: the initial permutation phase (P10) takes in input the initial 10-bit key and get us the 10 bits permuted according to the following rule:
3 5 2 7 4 10 1 9 8 6
The difference between P10 and P8 is only that P8 permutes only some bits while, P10, permutes all the 10 bits.

Hope I was helpful!


Why is this MAC based on secure PRF with ordering and randomization insecure? Is this MAC secure:

  To authenticate a message $m=m_1||\ldots||m_l$ where $m_i \in
 \{0,1\}^{n/2}$, choose  $r \leftarrow \{0,1\}^n$ at random, compute
   $$t:=F_k(r)\oplus F_k(\langle 1\rangle || m_1) \oplus \ldots \oplus
 F_k(\langle l\rangle ||m_l)$$

  (where $\langle i \rangle$ is $\frac{n}{2}$ bit encoding of the integer $i$) and send $\langle r, t\rangle$. $F$ is a pseudorandom function.

The question comes from "Introduction to Modern Cryptography" (4.4c) where it is asked to prove that it is insecure, however I'm not sure it is. Here is my intuition (I understand that it is very weak):

The problem comes from the fact that $\langle i \rangle$ is $n/2$ bit encoded. Therefore there is only negligible chance that any r will be of form: $\langle i \rangle || m$ where $i$ is of polynomial size. If this was only $\log n$ bit encoded then we can do something.

So each message xor $F_k(\langle 1\rangle || m_1) \oplus \ldots \oplus F_k(\langle l\rangle ||m_l)$ is XORed with $F_k(r)$ which is basically a random bit string (since $F$ is PRF) that has negligible chance of occuring twice. Therefore each tag is independent from each other.

I tried to prove that it is secure by simulating what would happen if it was breakable, but i was unable to prove that any fraudulent tag would have a unique $F_k(\langle i \rangle || m_i)$ that we haven't sent already during the simulation.

$\langle \langle 1\rangle || m_1, 0^n \rangle$ is a valid tag on $m = m_1$


What are the qualities of a good block cipher? Beginner, Intermediate, Advanced, Expert Notice: I'm doing this to learn.  I know not to use a homemade cipher for anything that requires security.  I also have heard before I'm not supposed to be trying this, but I learn best through trying to make things from scratch, even if I fail.

Ciphers are incredibly complex, to the point most people probably don't appreciate them, myself included.  Trying to make one from scratch might help with this, so I'm looking for a list of qualities/achievables that can be worked towards for years to come.

This is the list so far, for a good block cipher at different learning levels:

Beginner :

Encrypted output can not be broken by hand.  The level of encryption during WW1 or so.

Intermediate :

Changing a single bit in the input should have a 50% average chance of changing each bit of output.
Each byte should have a 1/256 chance of not changing (basically #1 ^ 8)
The number of bytes found in similar by search should be very few (I need to write down the math, but my estimate is around 5%)

Advanced:

Not sure yet?

Expert :

Immune to Differential cryptanalysis?

This list is very incomplete, but gives an example of what I'm looking for.

What is your list of achievable qualities for block cipher at different skill levels?

I don't think we can really separate things into skill levels as such, but there plenty of targets to aim for in terms of security goals. You'll want resistance to:

Differential cryptanalysis

Truncated differential cryptanalysis
Integral cryptanalysis
Impossible differential cryptanalysis
Higher order differential cryptnalysis
Boomerang attacks

Linear cryptanalysis

Differential-Linear attack

Rotational cryptanalysis
Slide attacks
Meet in the middle attacks

Biclique_attacks

Brute force search
Side Channel attacks

Timing attacks

Algebraic attacks
Partitioning cryptanalysis
Attacks that don't exist yet (at least, publicly)

Some resistance can be achieved via:

Large enough keysize

Mandatory for simple brute force search

Large enough blocksize

A large enough size can preclude the conditions for a slide attack to be applicable

Avoiding using secret information in ways that leak timing information

No lookup tables
No shuffling of arrays according to secret information
No secret dependent rotations

High levels of diffusion that cause the avalanche effect quickly

Some other desirable traits:

Software efficiency on a wide variety of platforms (i.e. 8 bit, 32 bit, 64 bit)
Key agility

Ideally the key schedule is invertible
Ideally the actual keys used each round are extracted from the invertible key schedule in a weakly one way manner (first preimage resistant)

Don't forget to obey Kerckhoffs Principle

After you've done all that, you might like to make your construction tweakable

Some of the mathematical concepts related to cipher design are:

Information theory

Information Entropy

Finite Fields
MDS matrix

Matrix
Coding theory

Boolean functions

S-box (meaning NxM mapping, not a lookup table)
Bent functions


Deciphering the RSA encrypted message from three different public keys I have three different 1024-bit public keys with common exponent $e$ but different moduli. A message $m$ is encrypted (without padding) using the three keys, which results in three different encrypted messages.

Given the three pairs of public keys $(N_i,e)$ and the encrypted messages $c_i=m^e\bmod N_i$ , how do I decipher the original message $m$ ?

In the question, the same message is directly encrypted to three different public keys using textbook RSA. This has dire consequences, including the following (with 1./2./3. not using the multiple public keys, and the answer likely thought at 5. or its extension 6.):

It severely limits the size of the message (to less than 128 octets).
A guess of the message can be checked by anyone with a public key $(N_i,e)$ and the ciphertext $c_i$, which by a standard assumption in cryptography includes adversaries. They simply encipher a guess of $m$ with $(N_i,e)$ and check it against $c_i$. Poof goes confidentiality if the message is a name on the class roll, a guessable password..
If $m$ is less than say $2^{70}$ , there is a good chance that there exits $r<2^{30}$ and $s<2^{40}$ with $m=r\cdot s$. In that case, regardless of $e$, there's a meet-in-the-middle attack recovering $m$: the attacker computes $c_0/r^e\bmod N_0$ for all candidates $r$ and store that for quick search (10 GiB of RAM for hash tables and 128 GiB of seldom used disk will do); then for each candidate $s$ computes $s^e\bmod N_0$ and searches that; it there's a match, $m$ is found as $r\cdot s$ .
If $e$ is small, and/or the message $m$ is small enough (less than about $2^{1023/e}$ ), then $m=\sqrt[e]{c_i}$ (where $i$ is the index of the largest $N_i$ and it is used straight, not modular arithmetic). Even though the $c_i$ are distinct, this attack could still work in the case at hand, when $m$ is close enough to the limit $\sqrt[e]{\max(N_i)}$ . Further, that eth root attack can be easily extended to like $m<2^{1060/e}$, and much more when we consider the multiple encryptions, see 6.
If $e=3$, the system is plain vulnerable to the archetypal RSA broadcast attack (also the simplest form of Håstad's broadcast attack). $e=3$ is a common choice in textbook RSA, because that allows the fastest encryption, using modular squaring and one modular multiplication; and is as safe as can be when $m$ is essentially random in an interval like $[0,N_i)$ and chosen independently for each encryption (contrary to the situation at hand where the same $m$ was used thrice).

We should first check that the three $\gcd(N_i,N_j)=1$ for $0\le i<j<3$. Otherwise, the GCD is a non-trivial factor of $N_i$ and $N_j$, and we have factored $N_i$ and $N_j$ (at least in two-factors RSA), and can compute a working private exponent and decipher, per the normal way in textbook RSA. Succeeding in that way is not supposed to happens, but does here and there, due to Random Number Generators that are not true, and gave the same results on different platforms, when they should not; and in academic exercises.

Having thus checked (or blindly assumed) that we can invoke the Chinese Remainder Theorem, we use it to solve for $x$ the system of 3 equations $x\equiv c_i\pmod{N_i}$ for $0\le i<3$ with $x\in[0,\prod N_i)$. That goes:

$x\gets c_0$
$N\gets N_0$
For each $i$ with $1\le i<3$

$x\gets(((N^{-1}\bmod N_i)\cdot(c_i-x))\bmod N_i)\cdot N+x$
$N\gets N\cdot N_i$

At that point $N=\prod N_i$, and $x$ is the desired solution.

Then we computes $m=\sqrt[3]x$ (which will be an exact integer); this is a non-modular cube root, and thus easy. This will always work because $m<\min(N_i)$, thus $m^3<N$, thus $m^3=x$ since by the CRT, there's no other $m$ with $m^3\equiv c_i\pmod{N_i}$.
Attacks 4. and 5. combine and can work for some $e>3$. If $m<\sqrt[e]{\prod N_i}$ , then after computing $x$ just as above it comes $m=\sqrt[e]x$ (which will be an exact integer).

This can be extended to $m$ up to about $(3072+k)/e$-bit with with $O(2^k)$ work; with $e=5$ perhaps $m$ up to $\approx78$ bytes (out of the maximum capacity of $<128$ bytes). An idea is to scan integers $r$ with $0\le r<2^k$, until $\sqrt[e]{r\cdot N+x}$ is an exact integer.

Further, we can save significant computational work in this search by reusing an approximation of $\sqrt[e]{r\cdot N+x}$ in order to test if $\sqrt[e]{(r+1)\cdot N+x}$ is an integer, and computing an approximation of $\sqrt[e]{(r+1)\cdot N+x}$.

And perhaps that attack can get even better; see this answer wondering about extending the eth root attack by combining Coppersmith's theorem with lattice methods.

Conclusions:

Do not use textbook RSA without random encryption padding, unless enciphering a mostly random $m$ nearly as wide as the public modulus, and enciphering that $m$ only once.
Rather, use a sound random padding for each RSA encryption, and hybrid encryption for the whole thing.
Do not conclude that a large $e$ like $e=65537$ will always save the day; it does not. Apply the above!


Is $f(f(x))$ a one way function? I found from a book the following proof.

Although I understand the initial construction, I don't understand the last sentence that proves the statement.

Why $f(f(x))$, in the paper $h(h(x))$, is always equal to $0^{2n}$
Is this what they are saying?
Why is it clearly not a one way function?

Note: While writing this answer, I discovered what seems to be a gap in the proof given in the cited lecture notes.  I'll thus present a slightly modified version of the proof below, and discuss the discrepancy a bit at the end.

Let's start with a quick recap, since your quote and summary of the lecture notes leaves out some important bits.
The formal definition of a one-way function, slightly expanded from Definition 5 in your lecture notes, is:

A function (family) $f: \{0,1\}^n \to \{0,1\}^m$ is one-way if and only if it can be computed by a polynomial-time algorithm, and if there is no probibilistic polynomial-time algorithm capable of finding preimages for it with non-negligible probability.
In other words, for $f$ to be one-way, there can be no probabilistic algorithm $A$ that could, given the output $y = f(x)$ for some randomly chosen input $x \in \{0,1\}^n$ and a maximum run-time polynomial in $n+m$, find an input $x'$ (possibly, but not necessarily, equal the original input $x$) such that $f(x') = y$ with a probability that is more than a negligible function of $n$.

An informal summary of this, dispensing with all the formalism of asymptotic complexity theory, would simply be that $f$ is one-way if there is no practical way, given a random output of $f$, to find an input that yields that output when given to $f$.
Based on this definition, we can show that:

Padding the output of $f$ with, say, a bunch of zeroes doesn't affect whether it is one-way.  (By definition, the adversary will always receive a valid output, so they can just strip away the zeros and then proceed as if they were attacking the original, unpadded function.)

Also, adding a bunch of extra dummy bits to the inputs of $f$, which don't affect the output, doesn't change whether $f$ is one-way.  (Since the dummy input bits don't affect the output, the adversary can choose those dummy bits any way it likes; but finding the correct values for the other, non-dummy input bits is still exactly as hard as finding a preimage for the original, unmodified function.)

(These technically hold only if the amount of padding / ignored bits added is a polynomial function of the original input + output length, but that's plenty enough for our purposes: $n \mapsto 2n$ is certainly a polynomial function.)
So, given an (arbitrary) one-way function $f$ with $n$-bit inputs and outputs, we can construct another one-way function $h$ with twice the input and output length like this:

Let $x^*$ be the first $n$ bits of the input $x$ to $h$.  Ignore the rest of the input.

Compute $y^* = f(x^*)$.

Prepend an arbitrary constant $n$-bit string $c$ (e.g. $c = 000...0$) to $y^*$, and output the resulting $2n$-bit string $y = c \,\|\, y^*$ as $h(x)$.

Now, by construction, this function $h$ is one-way, since finding preimages for it is at least as hard as finding preimages for $f$.  (Of course, the security parameters for $f$ and $h$ differ by a factor of 2, but that makes no difference asymptotically; a polynomial function of $2n$ is a polynomial function of $n$.)
But also by construction, the first $n$ bits of the output of $h$ are always constant, while the remaining output bits depend only on the first $n$ bits of the input.  Thus, $h(h(x)) = c \,\|\, f(c)$ for all $x$, and so finding preimages for $h(h(x))$ is trivial (since literally any input will do).

Now, the construction given in the lecture notes you cite goes a little bit further, explicitly defining $h$ to yield an all-zero output whenever the first $n$ input bits are zero (and always setting the first $n$ bits of the output to zero otherwise).
While not strictly necessary (we'll get constant output from $h(h(x))$ anyway), this doesn't actually harm the one-wayness of $h$ either.  In fact, we can show that modifying $h$ so that it always outputs a constant value for a negligibly small fraction of the total input space doesn't affect its one-wayness (and that $1/2^n$ is, indeed, a negligibly small fraction as $n$ tends to infinity).
However, where the lecture notes go wrong is when they try to justify this by claiming that:

"A generalization of the previous theorem (fixing values in a one-way function) shows that $h$ is also a one-way function.  (In short, we are only fixing the values of $\frac{2^n}{2^{2n}} = \frac1{2^n}$ of all of the possible values of $x$.  Since we are only fixing a negligible fraction of the possible values of $x$, the same proof with slight modifications still applies.)"

In fact, this claim is false.  As a simply counterexample, consider the modified function $h'$ defined as:

Split the $2n$-bit input $x$ into two $n$-bit strings $x_1$ and $x_2$.

If $x_1 = c$, return $h'(x) = c \,\|\, x_2 = x$.

Otherwise, return $h'(x) = c \,\|\, f(x_1)$.

Clearly, $h'(x) = h(x)$ for all but a negligibly small fraction of the inputs (namely, those that begin with the $n$-bit constant string $c$).  Yet $h'$ is obviously not a one-way function, since any valid output $y = h'(x)$ always begins with $c$, and so is its own preimage!
Of course, this doesn't invalidate the actual claim, since the function $h$ actually constructed in the notes is in fact one-way (provided that $f$ is one-way).  Still, if these notes are from a course you're studying in, you might want to mention this gap in the proof to your instructor.


secp256k1 prime modulus vs order For curve secp256k1 prime modulus is $2^{256}-2^{32}-977$ and order is smaller number but has near half of starting bits set. If I draw number to be private key, it must be less than order. All field operations are modulo prime modulus and it means they must be smaller than modulus but can be  >= order? (or not?). Coordinates of public key point can exceeds order?
A very interesting case is in signing and verifying: in pseudocode: from nayuki library is modulo order.
 * if (nonce outside range [1, order-1]) return false
 * p = nonce * G
 * r = p.x % order
 * if (r == 0) return false
 * s = nonce^-1 * (msgHash + r * privateKey) % order
 * if (s == 0) return false
 * s = min(s, order - s)

This means, operations are done, first modulo modulus p, next modulo order?

Yes, field operations may involve numbers that are larger than the order. Public key point coordinates may exceed the order.
Parts of the protocol that handle scalars work modulo the curve order, while the parts that handle elliptic curve points work modulo the prime modulus.
Sometimes, as you noted, some information "crosses" between these domains: the main case being inside the ECDSA protocol, in the r value which is obtained from a X coordinate and reduced modulo the order to enter in the computation of s.


Strength of TLS handshake I asked this question recently but I was told it is not save to simply send over the identifier for your crypto method you want to use. for example, say the server has crypto method 3 5 and 6, the client had 2, 3, and 6.

The clients sends the methods it can do and the server checks the highest possible version. A man in the middle could intercept the message from the client and only send 3, so the server would use the weakest common method. Obviously you don't want this, we want them to use 6 (the highest is the strongest in this case).

I have tried to figure out why TLS does not have this weakness (other than the FREAK bug) but somehow I can't find out why TLS does this better. So my question: How does TLS ensure the use of the best crypto method both the server and client share?

Background info

I curently have a piece of code which has a crypto layer (very old) it currently sends 00 which indicates it needs to use our old crypto method but 01 will be TLS (which I'm going to implement) However having TLS and an insecure exchange to determine the crypto method is obviously as strong as our insecure exchange. But to keep it backwards compatible we can't simply switch our old crypto method for TLS so we need to do this exchange. which is why i need to know how to do this properly.

How does TLS ensure the use of the best crypto method both the server and client share?

It does not. The server is responsible for selecting the cipher and there is no guarantee that it will select the best. But, if a man-in-the-middle tampers with the ClientHello to change the ciphers offered to the server, then this tampering will be detected at the end of the handshake, because their is a final signature over all data of the handshake and this signature will not match anymore.


Elliptic curve representation According to this page, Edward's curve point doubling can be represented in a different way by assuming $c=1$ and $d = r^2$.

It then says we can represent $x y$ as $Y Z$ satisfying $r\cdot y = \frac Y Z$

I am a bit confused. How would I then calculate the $x$ coordinate? For example, they have provided the following explicit formula:

YY = Y12
ZZ = r*Z12
V = s*(ZZ-YY)2
W = (ZZ+YY)2
Y3 = W-V
Z3 = W+V

So after obtaining $Y_3$ and $Z_3$, how would I revert back to affine coordinates and calculate $x$ and $y$?

When $c=1$ and $d = r^2$, an Edwards curve $x^2+y^2=c^2(1+dx^2y^2)$ becomes $$x^2+y^2=1+r^2x^2y^2 \iff x^2(1-r^2 y^2) = 1 - y^2$$
With the $(Y,Z)$ notation, a point $P = (x,y)$ is represented as a pair $(Y:Z)$ satisfying  $ry = Y/Z$.  Note that this representation does not allow to distinguish $P = (x,y)$ from $-P = (-x,y)$.

Given a pair $(Y:Z)$, one can recover $\pm P = (\pm x, y)$ where $y = Y/(rZ)$ and $\pm x$ is the square root of $(1-y^2)/(1-r^2y^2)$.


How can I verifiably announce a choice without revealing its content? Here is the simplified problem:

Alice chooses from a small set of possible values.
Bob guesses which value Alice picked.
Alice reveals what value she picked.

Alice's choice must stay secret initially, until after Bob has made his guess.
However, to make sure Alice does not cheat, her choice must be verifiable once it is revealed.

My idea would be to publish a salted hash of the choice at first and publish the salt along with the choice. As far as I understand, there are two possible attacks on this:

Bob could try to find the secret choice using the hash: the salt should make up for the small set of valid choices, so this should be equal to a normal a preimage attack.
Alice could pick two values and search for two salts so that each pair will generate the same hash. Due to the small number of choices, this should be similar to a birthday attack.

From what I can tell, both attacks do not yet pose a realistic risk to e.g. SHA 512. Would this be a valid approach? Did I miss anything? Is there a better solution?

This is the premise of a commitment scheme.  The dramatis personae in this setting are the prover, Peggy, who wishes to prove foreknowledge of a message $m$ to a verifier, Victor, but only later reveal $m$, at which point Victor can verify that Peggy didn't change her mind in the meantime.

For a message $m$, Peggy can commit to $m$ by choosing randomization $r$ and computing a commitment $c = C_r(m) \in \mathcal C$ which she gives to Victor while keeping $m$ and $r$ secret.  Later, when Peggy wants to reveal the message, she gives Victor $m$ and $r$, so that Victor can verify $c = C_r(m)$.  The commitment $C_r(m)$ should have two properties: it should reveal essentially no information about $m$ to anyone who doesn't know $r$, but it should be essentially impossible to to find $m' \ne m$ and $r'$ such that $C_r(m) = C_{r'}(m')$ and thereby break a commitment.

The first property is hiding, and can be formalized by putting a bound on the advantage of any (possibly cost-limited) adversary $D(c)$ to distinguish the commitment $C_r(m)$ of any message $m$ for uniform random $r$, from a uniform random commitment $c \in \mathcal C$: $\left|\Pr[D(C_r(m))] - \Pr[D(c)]\right|$.  If the distribution of $C_r(m)$ is exactly the same as the distribution of $c$, then this advantage is exactly zero, and the commitment scheme is said to be information-theoretically hiding; otherwise it is computationally hiding.

The second property is binding, and can be formalized by putting a bound on the probability of any (possibly cost-limited) adversary $F()$ to find $(r, m, r', m')$ with $m' \ne m$ such that $C_r(m) = C_{r'}(m')$.  (If it looks odd to see no parameters in $F$, that's because we usually instantiate it with a random oracle $H$ or a common reference string $\sigma$ and ask that of $F(H)$ or $F(\sigma)$.)  If there is exactly one message possible for every commitment, then this probability is exactly zero, and the commitment scheme is said to be information-theoretically binding; otherwise it is computationally binding.

Standard examples:

Hash commitments.
$C_r(m) = H(r \mathbin\| m)$, or $C_r(m) = \operatorname{HMAC-}\!H_r(m)$, where $H$ is a uniform random function chosen in advance so that Peggy and Victor have no influence over it, modeled as a random oracle in proofs, and implemented by a preimage- and collision-resistant hash $H$ like SHAKE128.

Hash commitments are only computationally hiding, but a distinguisher on this can be translated into a preimage attack on $H$, so if $H$ is preimage-resistant then a hash commitment is hiding; conversely a preimage attack on $H$ may enable an adversary to learn a secret commitment value.
Hash commitments are only computationally binding, but breaking a commitment on this can be translated into a collision attack on $H$, so if $H$ is collision-resistant then a hash commitment is binding; conversely a collision attack on $H$ may enable an adversary to break a commitment.  Consequently, for example, MD5 and HMAC-MD5 are unsuitable for $H$ even though HMAC-MD5 still seems to be a good PRF.

People sometimes use hash commitments on Twitter because it's convenient and everyone knows how to compute SHA-256 to verify them.
Pedersen commitments.
$C_r(m) = g^r h^m$, where $g$ and $h$ are elements of a prime-order group $G$ in which discrete logarithms are hard—elements chosen uniformly at random in advance so that Peggy and Victor have no influence over them, modeled as a common reference string in proofs, and implemented by protocols like FIPS 186-4, Appendix A.2.3 using hash functions like SHAKE128.  Here, unlike hash commitments, messages are not bit strings but elements of $\mathbb Z/\ell\mathbb Z$ where $\ell$ is the order of the group $G$.

Pedersen commitments are information-theoretically hiding, because $r \mapsto g^r h^m$ is a bijection with inverse $c \mapsto \log_g (c/h^m)$, so the distribution of $g^r h^m$ for uniform $r$ is uniform in $G$.
Pedersen commitments are computationally binding, because anyone who can compute discrete logarithms in $G$ can find $x = \log_g h$ so that $g^r h^m = g^{r + x m}$ and thereby can break commitments with arbitrary messages $m'$ by choosing $r' = r + x (m - m')$.  More specifically: if a Pedersen commitment breaker $F(g, h)$ can find $(r, m, r', m')$ with $m \ne m'$ such that $g^r h^m = g^{r'} g^{m'}$, then $\log_g h = \frac{r' - r}{m - m'}$, so anyone who can break a commitment in this scheme can compute discrete logs in $G$.

Pedersen commitments are also homomorphic: if $c_0 = C_{r_0}(m_0)$ and $c_1 = C_{r_1}(m_1)$, then $c_0 c_1 = C_{r_0 + r_1}(m_0 + m_1)$, and as such are convenient for fancy cryptography in zero-knowledge proof systems.  People sometimes use Pedersen commitments to (accidentally?) put back doors in electronic voting, in an attempt to prove that votes shuffled for anonymity were not forged in the process.  Pedersen commitments have a back door if Peggy can choose the elements $g$ and $h$: if Peggy chooses them to have a known relation $h = g^x$, then she can forge commitments as above and commit unrestricted vote fraud.
Elgamal commitments.
$C_r(m) = (g^r, h^r m)$, where $g$ and $h$ are elements of a prime-order group $G$ in which discrete logarithms are hard—elements chosen uniformly at random as a common reference string, etc., like Pedersen commitments.

Elgamal commitments are computationally hiding, because anyone who can compute discrete logarithms in $G$ can, given a commitment $(u, v)$, recover $r = \log_g u$ and $m = v/h^r$.  More specifically: an Elgamal commitment distinguisher can be turned into a decisional Diffie–Hellman attack on $G$, so Elgamal commitments are computationally hiding if DDH is hard, although conceivably DDH could be easy while DLOG is hard in $G$.
Elgamal commitments are information-theoretically binding, because there is exactly one possible message for each commitment.

Elgamal commitments are also homomorphic: if $c_0 = C_{r_0}(m_0) = (u_0, v_0)$ and $c_1 = C_{r_1}(m_1) = (u_1, v_1)$, then the elementwise product $c_0 c_1 = (u_0 u_1, v_0 v_1)$ is $C_{r_0 + r_1}(m_0 m_1)$.  I don't know who uses Elgamal commitments in practice.  Elgamal commitments have a back door if Victor can choose $g$ and $h$: if Victor can choose them to have a known relation $h = g^x$, then from a commitment $(u, v) = (g^r, h^r m) = (g^r, g^{x r} m)$, Victor can recover $m$ by $v/u^x = g^{x r} m / (g^r)^x = m$.


Using 0 nonce for AES-256 in CTR mode My question is: I'm using AES with 256 bits key in CTR mode. Will it be less secure if I use a random key and static zero nonce?

key = random;
nonce = 0;

There will no problem with using the nonce as 0 but only for once with the same key as the nonce says number used once. Remember we can generate the nonce randomly and at it has $1/2^{128}$ chance to appear.
CTR mode turns a block cipher into a stream cipher. As in all stream cipher, if you use the same stream again it will be vulnerable to crib-dragging attacks. In CTR mode, it is using the same nonce again with the same key.
Never use nonce more than once with the same key. To prevent the reselection of a nonce with a good random number generator, you should stop using the same key much before $\sqrt{2^{128}} = 2^{64}$ nonce generation, that comes from the birthday paradox. Alternatively, you can use an LFSR based solution to generate the nonce deterministically as suggested by the NIST.

so, if I use different keys and zero nonce it will be secure?

With the nonces, you can use the same key for a long time, Using always 0 is no more CTR mode. It is completely a new mode of operation. I don't see a problem with that, except as Maarten commented; the Key Check values:

These are often calculated by performing a single block encryption with all zero's. Please make sure that those are not used or published, or you will be exposing the initial part of your key stream.

It is better to use a HKDF to derive a key and a nonce very easily with your randomly generated key using salt and info
Extract:
$$\text{HKDF-Extract}(salt, IKM) \to PRK,$$where  PRK is a pseudorandom key, IKM is the input key material. If your random source is good, you may not need Extract.
and
Expand:
$$\text{KDF-Expand}(PRK, info, L) \to OKM,$$where OKM is Output Keying Material. L is the desired key length.
Note: Rogaway, in their seminal work: Evaluation of Some Blockcipher
Modes of Operation, in figure 1.2: summaries of their findings — confidentiality modes. CTR:

An IV-based encryption scheme, the mode achieves indistinguishability from random bits assuming a nonce IV. As a secure nonce-based scheme, the mode can also be used as a probabilistic encryption scheme, with a random IV. Complete failure of privacy if a nonce gets reused on encryption or decryption. The parallelizability of the mode often makes it faster, in some settings much faster, than other confidentiality modes. An important building block for authenticated-encryption schemes 1. Overall, usually the best and most modern way to achieve privacy-only encryption.

Therefore stick the expert's findings!

1 : AES-GCM that uses CTR and Even a single AES-GCM nonce reuse can be catastrophic.


Why is this authentication procedure using Rabin crypto not useful? A friend asked me the following, pointing out that the method is not very useful (my problem is I do not see why it is not good):

Consider a person A which chooses $n$ as the public key for the Rabin crypto-system.
We want to be sure that we are communicating with person A so we send her a random item $r\equiv m^2 \mod n$.
Person A receives $r$ and decodes it using the factorization of $n$ and finds a square rot $m_1$ of $r$.
A then sends us $m_1$ and we check $r\equiv m_1^2 \mod n$.

Why is this not useful?

A is acting as a square-root oracle in that protocol. We can use that oracle to factor $n$ and break the scheme.

Suppose you are an attacker that wants to impersonate A. You:

Pick a random $m$;
Send $m^2$ to A;
Compute $p = \gcd(m_1 - m, n)$, thus factoring $n$.

This works with probability $1/2$ for each attempt.


Is a hash "reset sequence" possible? Is there such thing as "hash reset sequence" that brings hash to the same known state?

A hash function has a state. In MD5 and others vulnerable to the length extension attack, the attack works by continuing computation from existing hash.

So, the question here is - when I continue computing hash, is it possible that there is a sequence of data that will start moving the hash function output into some known corridor with known results? Similar to http://numericana.com/answer/magic.htm#1089 and other magic tricks.

Answering the most general interpretation first, yes, it is possible for some piece of data to take the state to some known state. This is because the compression function that moves from one state to the next necessarily has collisions, because its inputs are larger than outputs. For most states you would expect a single block of data to be enough to take you to any state.

However, such a one-block sequence would not apply universally, it would take from one particular state to the desired state. Finding such a sequence for a particular predetermined (current, desired) pair would amount to a preimage attack on the compression function, which we cannot do in the case of MD5. Best attacks take close to the $2^{128}$ time that brute force does.

If you wanted a sequence that took you from any state to a known state, you would need even more computation. Such a sequence might exist, but it could be long: e.g. if with each block you could halve the possible states you would need $2^{127}$ blocks. A brute force approach would be completely infeasible even in comparison to the earlier attack. Even using the sequence could be infeasible.

Finally, the full state of MD5 is not just the current state vector that the compression function affects. There is also the total length processed (modulo $2^{64}$), which is used when finalizing the value. So you could not use a single "reset sequence" as a literal reset, because it would not take two different-length prefixes to the same full state. (If you had an "universal reset sequence" you could first pad the inputs to the same length, but you would still need to know the lengths.)


Is there a key exchange protocol that requires only one message? Say I want to exchange a secret with someone, but I only get to send one message to the other person, and then we encrypt with that secret. Diffie-Hellman and ECDH require multiple messages to be sent back and forth to get a shared secret.
Is there a key exchange that requires just one message to be sent from one party securely? (I know that sending the key over plaintext works, but that isn't secure.)
(Define message as a packet over the internet or one SMS for example)

For forward secrecy without a synchronous handshake, you want something like the "ratcheting" protocol that Signal uses. It's a quite clever system, really:

Each party generates an asymmetric key pair, and gives the public key to anybody who wants it.
Each party generates and stores some number of [EC]DH parameters - one set for everybody you expect to need to talk to soon - then signs the public part of the parameters with the private key and makes the signed part publicly available too.

In Signal's case, the keys and signed public parameters are sent to the central server. Assuming you want to start a secure communication and either trust the server, have some way to verify the public key, or don't care about authentication, you can then do the following steps:

Download the recipients's key and their next, not-yet-used public key exchange parameters (the server and the recipient both track which parameters have been used).
Optionally, authenticate the key and verify the signature on the parameters.
Generate your own ephemeral set of key exchange parameters, and sign the public portion with your private key.
Use the private portion from your parameters and the public portion from the recipient's parameters to derive a symmetric key.
Optionally, encrypt a message with that key.
Send your public key, both sides' signed public key parameters, and the message all to the recipient.
Delete the ephemeral key parameters.

The recipient:

Looks up the pre-signed key exchange parameters, and verifies that the one of theirs just received had never been used before.
Optionally, verifies the sender's public key and the signature on their public key exchange parameter.
Retrieves their corresponding private portion of the key exchange parameters, and uses it plus the sender's public portion to re-derive the symmetric key.
Deletes the now-used private portion of the key exchange parameters, to ensure forward secrecy.
Decrypts the message, and/or encrypts one to send back, using the exchanged key.

For your scenario, if you can't have the central server, you'd need to retrieve the public key exchange parameter (and optionally public key to verify it) beforehand. However, you'd then be able to complete the key exchange and initiate secure communication, asynchronously, with one message... and (at least as soon as the recipient gets the message and completes the key exchange) it would be forward-secret.


$X_ {i_1}, . . . , X_{ i_ k} $ are IID random variables or not? In this paper
secret
sharing is to distribute information (the secret) over
a set of participants such that the secret can only be reconstructed if certain authorized combinations of participants join their information. The set of authorized combinations is called the access structure.

Formally, the secret is modeled as a random variable S, and a secret sharing scheme
assigns a random variable $X_i$ to each participant $i$ in such a way that if $\{ i_ 1, . . . , i_ k \} $is an authorized
set of participants, then S is a function of $X_ {i_1}, . . . , X_{ i_ k}$  that is, $H ( S |X_ {i_1}, . . . , X_{ i_ k} ) = 0$;

Here my doubt is $X_ {i_1}, . . . , X_{ i_ k}$ are IID random variables or not

My first understanding was yes, but in fact, it depends.

First understanding: You can view them as IID, unless you have some knowledge about the secret $s$ and enough other variables. Take for example a Shamir Secret, a simpler secret sharing scheme which is a special case of this. A Shamir secret allows to reconstruct $s$ with any set of $k$ parts from $n$ shares. It is built by choosing a random $k-1$ degree polynomial such that $f(0)=s$. Any set of $k$ or more distinct points allows you to reconstruct this polynomial curve and thus learn it's value for $x=0$. Any set of $k-1$ points (except $(f(0),0)$) would be unauthorized and insufficient to reconstruct the secret. Since each coefficient of the polynomial (except $s$, that you have no knowledge of, including it's distribution) is chosen randomly, every set of point. Conditioning on $k-1$ shares doesn't change in any way the distribution of the $k^{th}$ share: it is still random.

But in fact it's not necessarily the case: only parts of these shares must be randomly distributed. Take these Shamir secrets: every share is a tuple $(x,f(x))$, and given their construction and a tuple $(x_1,f(x_1))$, you would expect the next tuple not to have $x_2 \neq x_1 $, so that even if $f(x_2)$ would be independent of $(x_1,f(x_1))$, $(x_2,f(x_2))$ would not. Conversely, you could choose $x$ as random every time, risking a possible $x_2 = x_1$, but making all the shares IID.


Using PKCS #11 Certificate Objects for Verification What is the proper way to use the public key contained in a X.509 certificate with PKCS #11?

C_VerifyInit's hKey input says "hKey is the handle of the verification key"

Is it permitted to pass the handle of a certificate containing a public key?

Or is it required that the public key is extracted from the certificate and re-imported as a solo public key, and then this public key handle used for verify operations?

Thank you!

Quoting the PKCS#11 specification:

  Certificate objects (object class CKO_CERTIFICATE) hold public-key or attribute certificates. Other than providing access to certificate objects, Cryptoki does not attach any special meaning to certificates. (§4.6.2)

So no, you can't do anything with a certificate object other than store it and retrieve its attributes.

This is confirmed in the specification of C_VerifyInit:

  The CKA_VERIFY attribute of the verification key, which indicates whether the key supports verification where the signature is an appendix to the data, MUST be CK_TRUE.

A certificate object is not a key and CKA_VERIFY is not listed as a permitted attribute, so it can't be used for C_VerifyInit.

The ability to store a certificate in a token is primarily useful when it's stored together with the private key. You use the private key to sign data (including authentication challenges) and send the certificate signed by a CA as part of authentication. It's useful to store the private key in a cryptographic token because this offers better protection against a compromise of the key. It isn't particularly useful to store a public key or a certificate in a cryptographic token because it isn't confidential¹. The point of putting the certificate in the token is that it's easier to manage the key lifecycle (creation, enrollment, destruction, …) if the key and the corresponding certificate(s) are stored in the same location.

¹  Putting the certificate in a cryptographic token guarantees its integrity, but that's usually pointless because the code using the certificate is outside the token. You don't gain anything by preventing modifications to the certificate if you can change the code that uses the certificate to use a different one or ignore the verification result.


Secure encrypt-then-sign with RSA I understand that when you want to encrypt and sign data with RSA the generally recommended approach is sign-then-encrypt.

However, I have encrypted data that I need to sign, to prove the author of the encrypted data.

Encrypt wth recipient's public key
Sign with author's private key
Concatenate cipher text with signature

From reading papers such as this, it seems that the problems with sign-then-encrypt are quite subtle, but solutions are quite straightforwrd.

I haven't been able to turn up much on issues with encrypt-then-sign. I guess one problem is that someone could simply strip off the signature and replace it with their own. My first thought was to prefix the data with the author's public key before encrypting, but then the signature can only 'really' be verified by the recipient (public verification is more desirable for me).

What are the issues associated with encrypt-then-sign, and what solutions exist?

** Edit **

I thought of another potential solution to the problem of someone replacing the original signature with their own - using X.509 certificates. So in step 3 above we also concatenate the certificate of the author. When verifying the signature we check that the public key matches that of the certificate, and we also verify that the certificate was issued by a particular, trusted CA. With this scheme, not just anyone can replace the signature, only those who are issued a certificate from the trusted CA. Any issues with this approach?

The primary problem with encrypt-then-sign (signing the ciphertext) relates to the difference between signing for the purpose of assigning responsibility vs for the purpose of taking credit.  Encrypt-then-sign is OK for the former but not for the latter.  The issue is quite subtle.

In particular, in your protocol, the recipient has no reason to believe the sender (signer) was ever aware of the contents of the plaintext.  The signer must have been aware of the contents of the ciphertext and approved signing the ciphertext, but this does not mean that the signer knows or created the original message.

For instance, suppose we're using this to log into a site.  Suppose Alice, who is a system administrator, is going to authenticate to Sam, who is a server.  Suppose that, to authenticate, Alice is going to use your scheme to send a copy of the root password to Sam (encrypted and then signed); if everything checks out, Sam will conclude that Alice knows the root password and should be granted full access to the server.  Sounds reasonable, right?  But now look what can go wrong.  Mallet can intercept Alice's encrypted-and-then-signed packet, strip off Alice's signature, append her own signature, and forward it to Sam.  Sam will receive it and everything will check out: Sam can see that this was signed by Mallet and decrypts to contain the correct root password, so Sam will conclude that Mallet should be granted full access to the server.  That's bad.

The reason why an attack is possible in the latter example is that Alice and Sam were using the signature as a basis for taking credit: Alice was trying to take credit for knowledge of the root password, and Sam was willing to accept the signature as evidence for that.  However, encrypt-then-sign does not provide a basis for allowing the sender to take credit for knowledge of the contents of the message.

So, whether this scheme is adequate will depend upon the particular application you have.  Many applications only need authentication for the purpose of assigning responsibility: if something goes wrong, we know who to hold responsible (or, we know whose account to charge or whose quota to decrement), and encrypt-then-sign is fine for that.  But a few applications (the password authentication example I mentioned; auctions; and some others) use authentication to additionally allow the parties to take credit for knowledge of a message.  For those applications, vanilla encrypt-then-sign can be problematic.

There are ways to fix encrypt-then-sign so it doesn't have this shortcoming.  See the research literature below for details.

For more details on all of this, including what can go wrong as well as how to avoid these problems, you can read the following detailed explanation in the research literature:

Prudent engineering practice for cryptographic protocols. Martin Abadi and Roger Needham.  See Section 5.2 (but the entire paper is fantastic and a classic).
Security Protocols and their Properties.  Martin Abadi.  See Section 5.


ElGamal signature - exploiting fallacious implementation This question is related to ElGamal signature scheme as defined here
ElGamal signature without calculating the inverse

Show how one could exploit an implementation ElGamal signature scheme in which it is not checked that $0 \leq \gamma \leq p-1.$

As far as I can see, we have to find a $\gamma$ such that $\alpha^{a\gamma-x}\gamma^\delta \equiv 1 \pmod{p}$ for a message $x$.

Anyone happens to see a good choice of $\gamma$?

As Wikipedia’s Chinese remainder theorem article states:

  The Chinese remainder theorem is a theorem of number theory, which states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

Using that, you can solve this by finding a $\gamma$ satisfying

$$\gamma \equiv 0 \pmod{p-1}$$

and

$$\gamma \equiv \alpha^x \pmod{p}$$

and you’re done.


Why xor the message into the state for sponge hashes? Sponge hashes like Keccak(SHA-3) and CubeHash, xor a message block into part of the internal state. Why use a reversible operation like xor for that, instead of replacing that part of the state with the message block?

It clearly has no effect on pre-image and collision resistance. It's trivial to transform collisions/pre-images between the different mixing schemes.
It causes some weirdness if the attacker learns the internal state of the hash. This shouldn't happen, but makes me slightly uncomfortable.
Perhaps it increases security in a universal hashing scenario. Might make it impossible to construct key independent collisions. But my understanding of this is pretty foggy.
When replacing it's not necessary to store that part of the state between permutations. Reduces the memory usage in some scenarios.
When replacing instead of xor-ing the truncated permutation seems like a pretty normal compression function, with the sponge becoming a standard MD style construction with a tagged last block.

Section 4.3 of the paper Cryptographic sponge functions analyzes the Overwrite-mode for a sponge, which does just what you propose: instead of XORing the next part of the message into the non-hidden part of the state, replace the non-hidden part of the state by it.

They show that it can be implemented on top of the Duplex mode (which outputs the non-hidden part of the state), and for this reason has equivalent security as the usual Sponge mode (which XORs the message part), with the cost of two bits of capacity or bitrate used for padding and a frame bit.

This is also intuitively clear: All the security claims of a sponge are relative to the capacity, i.e. the size of the hidden part of the state. What you do with the non-hidden part doesn't really matter, as long as your new data somehow comes into play.


Should I use md5 for my new application? MD5 is a very fast hash and its output is short and easy to store. Should I use it for my non-security-sensitive application?

I don't think so, but I can't seem to convince anyone else that this is true.

When I need to show to others that they are wrong and it is their word against mine, I look to the words of industry recognized experts and then challenge them to find an industry recognized expert that supports their belief.

In this case, Bruce Schneier has written a lot on MD5 (in Bruce style, each word links to a different blog post or article of his).

Wikipedia even has a nice article on MD5 security.

That said, you specify in your question that this is potentially for a "non-security-sensitive" application. What do you mean by that? Your comment seems to suggest that you are signing hashes of files. That to me seems security sensitive.


Parallelization of CFB mode encryption and decryption While reading Evaluation of Some Blockcipher Modes of Operation by Rogaway (someone just linked it somewhere), I noticed two claims about CFB that I'm not sure I understand:

Regarding whether CFB mode encryption is parallelizable the paper says (on page  31):

  Yes, but awkward. See ISO 10116 for less awkward generalization.

Regarding whether the decryption is parallelizable it says (same page):

  Yes, but awkward.

I can't see how this is true at all. To encrypt a block with CFB mode you need the ciphertext of the previous block (or more if $s < n$), so how can you parallelize it?
Parallelizing the decryption algorithm, OTOH, seems very simple, especially when $s = n$ (which I suppose is the "common" case?). I'm unsure what is supposed to be awkward about it, unless it's the fact that with $s < n$ you need to look back more than one $s$-bit block of ciphertext? But since you are still just taking the previous $n$ bits of ciphertext, this seems just like CBC, which wasn't considered awkward.

The ISO 10116 reference might be helpful for showing which awkwardness it avoids, but I don't have access to it.

I've been thinking a little bit about it, and now I think it is possible, but you have to consider the generalization of CFB in ISO 10116 (I don't have access to the ISO 10116 standard, so I will assume that the description by Rogaway is correct).

The generalization of CFB from the ISO standard seems to have two main changes:

The feedback block (FB), of size $r$, can be longer than the input block (IB), of size $n$. The IB is constructed with the left $n$ bits of the FB.
A new parameter $k$ specifies how much the previous feedback block is shifted to the left on each step.

For each new plaintext block, the feedback block (FB) will be made of three parts:

The least significant $r - k$ bits of the previous FB
A sequence of one bits, of size $k - s$
The previous ciphertext bits, of size $s$

We are used to the case where $r = n$ and $k = s$ (e.g., the NIST 800-38A specification), so there is no sequence of one bits. However, when $r\ge n+s $, the input block for the block cipher will only take bits from the previous FB and one-bits, and not from the previous ciphertext bits since it only takes the left $n$ bits from the FB. This way you could partially parallelize the encryption operation.

A very illustrative way to understand why this allows some parallelization is to imagine a very very long feedback block, much greater than the input block. If you append the previous ciphertext to the right of the FB, shift the FB just a little to the left and take the left part of the resulting FB as your new IB, then the ciphertext will not take part of the new IB, at least for some rounds. These rounds are then parallelizable. Adjusting parameters $k$ and $r$ allow to precisely define the parallelization factor.


RSA - Ecrypting the same data with the same public key = same ciphertext? If an adversary knows my public key and guesses what was my plaintext, can he test for it somehow?

The most obvious way is encrypting the guessed plaintext with my public key and the same parameters that he can probably discover from the ciphertext, to see if the result is the same.

The answer to your question is "yes, RSA will encrypt the same cleartext to the same ciphertext every time." And yes, this is a known property of RSA. That's why every standard that uses RSA, such as PKCS or CMS, specifies the use of randomized padding.


Is this a good Pseudo-Random Number Generator? I discovered what appears to be a good quality pseudorandom number generator, but I have not subjected it to any statistical tests beyond bit frequency, bit pair frequency, and least-significant bit frequency tests. It generates a block of bytes by evolving deterministically, starting with a seed state. I'm new to Stack Exchange, so please bear with me.
Here is the process (test example):
start with a 32-byte sequence (256 bits) and an integer variable k, and for each byte X(i),

$s = 7 - (X[i+1]+X[i+2]) \bmod 15$
$X[i] = ((X[i] + k) * 2^s) \bmod 255$
$k = k + X(i)$

and I implemented this process in C as follows:
    #define CYCLES 1 // full cycles per byte of the seed size per evolution
    unsigned int i, j;
    unsigned char a, k;
    int s;
    for (i = 0; i < 32*CYCLES; i++) {
        a = X[i%32]+k;
        s = 7-(X[(i+1)%32]+X[(i+2)%32])%15;
        for (j = 0; j < abs(s); j++) {
            if (s<0) {
                a = ((a&1)==1)?((a>>1)+128):(a>>1);
            }
            else {
                a = ((a&128)==128)?((a<<1)+1):(a<<1);
            }
        }
        X[i%32] = a;
        k += a;
    }

The C implementation of modular multiplication by powers of uses bitwise operations and differs in only one way from an algebraic method: when a = 255, the output is always 255. This is essentially a rotation of the byte abs(s) times to the left when the sign is positive, and the right when it is negative.
If I initialize the array X with a seed value such as "ABCDEFGHIJKLMNOPQRSTUVWXYZ012345" and evolve it 32 times, then map out the resulting bits or do basic tests for randomness, it appears to be very similar to true randomness. Am I missing something, or is this a good PRN generator?

What could possibly be an advantage of your method from directly sampling the bytes from the prime number distribution?
Like:
Start at some integer $k$ and sample the 8 bits as: $k*30+\lbrace -13,-11,-7,-1,1,7,11,13\rbrace$, each time when it is a prime number, you set the bit at that position to 1, otherwise to 0. If your sampled Byte is $<= 64$ use k-= Byte, otherwise use k+= Byte for the next sample.
Isn't this much simpler than your method, or am I missing something of importance?


Can i generate a SHA512 hash if i know the SHA256 hash of some unknown data? if the SHA256 Hash of some unknown data is known !
Can i find the SHA512 of that unknown data ?

No, you can’t.

There are (at most) $2^{256}$ different possible SHA-256 hashes.

If it were possible to deduce a SHA-512 hash from a SHA-256 hash with no knowledge of the data, then there would be at most as many different SHA-512 hashes as different SHA-256 hashes.

Then, a SHA-512 hash would be at most as strong as a 256-bit hash.


Derive a key from public data using a secret master key Users in my system will be given a device that contains a 128-bit AES user key. The user key will be derived from 64 bits of public data related to the user, which is unique but very predictable (i.e. a sequential user ID value). The value of the user key must be kept secret from the users. I assume users are fully aware that the user ID is used in the key derivation and that they know its value. A centrally controlled "master" AES key will be used to derive the user key in each device. Users will have no access to this key.

I've been asked to design the derivation scheme. The goal is to ensure the user has no hope of determining their key based on the 64-bits of public data.

My current plan for this derivation is to concatenate a "context" byte to the user ID and then encrypt it with the master key, using ECB-mode and PKCS #7 padding and use the result as the user key.

Does this simplistic derivation scheme meet my design goal? Without knowledge of the master key, I can't fathom how users could infer anything about the user key from the public data. However the simplicity of my design worries me.

I have encountered key derivation schemes, such as RFC 5869 that might be appropriate. I would be much happier using a peer-reviewed method rather than designing my own if someone can point at a suitable standard.

I'd still go with HKDF. Since you already have a good uniform master key, you can skip the extraction step.

So HKDF simply becomes HMAC-SHA-2(masterKey, info+\x01) I'd start info with a string identifying your use, and add the user specific information after that.

Your system should be secure as well as long as you only produce a single block of output. Essentially the user specific info serves as an IV for a mode similar to AES-CTR.

NIST Special Publication 800-56C - Recommendation for Key Derivation through Extraction-then-Expansion defines a scheme similar to AES, but it's probably unnecessarily complicated for your scenario.


Is there any security issue if an attacker recovers the key stream generated by a stream cipher? I've learned that a stream cipher like ChaCha20 generates a key stream that gets XORed with the plaintext to get the ciphertext... If an attacker knows the plaintext, he could just simply XOR that with the ciphertext to get the corresponding keystream.
Is there any security issue with this? I realize that it is because of the XORing operation that this is easily possible. Is there an even better way to encrypt the plaintext using the keystream without using XOR, that would also facilitate message authentication?

First, there's no issue with modern stream cipher constructions - either using an AEAD block cipher mode of operation such as GCM, or the combination of ChaCha20-Poly1305 as Google had experimented and subsequently formalized in the form of Internet RFC documents.

Stream ciphers are basically reduced-capability one-time-pads as one may infer: stream cipher cipher streams only has as many possible values as there are keys, where as one-time-pads are truely random. This is fine since physically buildable computers (including those hypothetical quantum computers) are bounded in capabilities - in both time and space dimensions.

Second, the new trend in the field is to build AEADs from permutations using Duplex construction (I admit these aren't the popular knowledges you might learn from school or might encounter in your TV programs or newspapers).

Indeed, ChaCha20 and Poly1305 are separate primitives that were introduced as "backup"s to AES, etc. Even the original paper proposing Poly1305 introduced it as AES-Poly1305.

Roughly describing the concept:

Recall the SHA3 hash functions are based on 1600-bit Keccak permutation running in Sponge mode - the permutation is partitioned into 2 parts, 1 part is used to absorb data and squeeze out the hash digest, the other part is kept secret as the security capacity.

Duplex is similar, except the data is read as they goes in. Adding in some careful design, you get a AEAD from a single primitive - the permutation.

Examples of these types of cipher include Gimli, Xoodyak, etc. You'd find some more at NIST lightweight cryptography project page.