Rainbow tables and blowfish I'm thinking of implementing rainbow tables for a specific blowfish problem, but I have trouble thinking of the proper way to apply the original paper (and its application to hash functions) to blowfish.

Say we have a not too clever password hashing function, which just uses the password as a key to blowfish-encrypt a known plaintext of size $n$. I want to build a rainbow table enabling me to quickly find which key (where the key belongs to a space of size $N$) gave an encrypted text.

From what I understand of the rainbow tables original paper and wikipedia page, I should choose a number $k$ to be the length of my chains, and build them :

Given a starting key $x_0$, calculate $h_0 = \text{blowfish}_{x_0}(\text{plainText})$
Define $x_1 = R_0 (h_0)$ where $R_0$ is my first reduction function.
Keep doing that, calculating $x_{k+1} = R_k(\text{blowfish}_{x_k}(\text{plainText}))$

I understand the principle of building these chains, I understand how/why I'll be able to do a not-too-slow lookup on the sorted chains, but there are several things I still don't understand in this case :

How many starting keys should I choose ? If I just use $N/k$, my intuition would be that all the keys should end up being tested in one chain, but can we be sure of that ? To me blowfish is bijective (since reversible) on the plaintext, but how can I be sure that two keys won't give the same encrypted text ?
What reduction functions should I use ? It seems to me like this would play a crucial role in making sure that all of my search space has been done.
If the two assumptions above don't hold, is there an efficient way to know which keys still haven't been tested to make sure they are used to generate new chains ?

I hope my questions won't look too dumb, feel free to point me to other papers/proofs, I'd be happy to understand this fully.
Thanks a lot

How many starting keys should I choose?

The answer lies in the storage size and lookup time in the table. For example; if we split the $2^{40}$ into $t$ and $l$, the size of the chains and the number of chains, respectively. Let say $t = 2^{20}$ and $l = 2^{20}$

$t = 2^{20}$ chains;

Storage: $2* 64 * 2^{20} = 2^{27}$-bit that is $2^{21}$-Byts storage size.
Sorting: Only once you need to sort the $2^{20}$ chains ends by $\mathcal{O}(n\log n )$ time is $\approx 20*2^{20}$
The lookup time: at most for $2^{20}$ chains we have $2^{20} *\log_2(2^{20})$ by binary search.

You can use this site to calculate the parameters.

  If I just use N/k, my intuition would be that all the keys should end up being tested in one chain, but can we be sure of that?

No, we can not be sure about this.

  To me blowfish is bijective (since reversible) on the plaintext, but how can I be sure that two keys won't give the same encrypted text?

There is no problem in the password cracking case; you found a valid one.

  What reduction functions should I use? It seems to me like this would play a crucial role in making sure that all of my search space has been done.

$(H(k_{i-1}+i))$, $H$ is a hash funtion,  $k_{i-1}$ output of the previous node in the chain, $i$ the $i$-th node. Strip the $H$ to 64-bit.

  If the two assumptions above don't hold, is there an efficient way to know which keys still haven't been tested to make sure they are used to generate new chains?

Other than storing them, no.


Secure multi-party computation for digital signature Is there any practical algorithm that will allow to use public key cryptography (RSA or ECC) in the following way

There are N parties. Up to M are malicious adversaries (were trusted, but got taken over silently). I will be happy with solution for any N and M = 1.
Parties can communicate securely. No eavesdropping.
Private key K is somehow split and shared between all N parties. Maybe something like Shamir's Secret Sharing. No party can recover K without other N-1 parties data.
All parties receive some data S.
Parties should be able to encrypt S (actually hash of S, I need digital signature) with K, but without revealing any useful information about K to malicious adversary; or should detect that there are too many malicious adversaries and abort.

Here's a fairly straight-forward method, using RSA:

Set-up phase (assuming a trusted dealer that participates only with the setup phase; such a setup without a dealer can be done, but is considerably more complicated):

The dealer selects a random RSA public/private keypair $(n,e)$ and $(d)$
The dealer then selects $N$ values $d_1, d_2, …, d_N$ with the constraint that $d_1 + d_2 + … + d_N \equiv d \pmod{ \lambda(n) }$
The dealer privately sends $d_i$ to party $i$, and publishes the public key $(n, e)$

Signature generation phase:

Each party gets a copy of the value to be signed $S$
Each party $i$ deterministically pads $S$ (perhaps using PKCS #1.5 signature padding, perhaps using PSS using randomness seeded by $S$), and then raises that to the power of $d_i$ modulo $n$; that is, it computes $sig_i = \text{Pad}(S)^{d_i} \bmod n$
Each party sends $sig_i$ to a collector, which computes $sig = sig_1 \cdot sig_2 \cdot … \cdot s_n \bmod n$, and broadcasts it
Everyone checks if $sig$ is a valid signature to the value $s$; if not, then a malicious party is detected

Lets go through the requirements:

No party can recover secret key $d$ without other $N-1$ parties data

Met; without all the $d_i$ values, you cannot reconstruct the $d$ value.

5.Parties should be able to encrypt $S$ (actually hash of $S$, I need digital signature) with secret key $d$, but without revealing any useful information about $d$ to malicious adversary

Met; each party acts as an Oracle that'll compute $f(x) = x^{d_i} \pmod n$, however if the Discrete Log problem is hard, you can't recover $d_i$ from that.

Now, a malicious party could perform a Denial of Service attack (by not computing his $sig_i$ value properly.  On the other hand, I believe that this will always be true if you require that $N-1$ parties be unable to recover the key (or otherwise generate arbitrary signatures, which is effectively the same as recovering the key), and so I would claim that this meets your requirement.


Why use two affine transformations in Multivariate Cryptography? I'm reading Multivariate Cryptography and would like to know why we use two affine transformations to scramble the central map?

Why not use only one?

In the majority of multivariate cryptographic schemes (MQ) the encryption/signature function $E$ is a composition of secret affine invertible transformations $A,B$ and a nonlinear transformation $P$ (can be secret or public):
$$
E = B\circ P\circ A
$$

$P$ is typically invertible, and the goal of the scheme is to make $E$ non-invertible even though it is fully exposed to an attacker as a polynomial.

The mere fact that $P$ is invertible explains why we need both $A$ and $B$. Indeed, suppose that $A$ is missing, then in the equation
$$
E(x) = B(P(x))
$$
we substitute
$$
x = P^{-1}(y)
$$
and obtain
$$
E(P^{-1}(y)) = B(y),
$$
so we know $B$ and are able to invert $B$.

This is the simplest case; there are other variants, where $P$ is secret, or its inverse is not available in the closed form, or some of the output polynomials are dropped (OK for signatures). In some of these variants both $A$ and $B$ are still required as otherwise you could invert the scheme just by looking at the structure of the polynomial and comparing monomials of $E$ with monomials of $P$. However, say, if $P$ is secret, then both $A$ and $B$ can be considered as part of $P$.


Create a potential input for sha-256 hash given a substring of input? Let's say I'm given a specific SHA-256 hash.

Further assume that the SHA-256 input, that yielded this hash contained a known sub-string.
Is there a way to find the input (containing the specific substring) that hashes to the given output?

If so, is it possible to further find an input of length N (containing the substring) to be hashed to the same SHA-256 hash?

SHA-256 is¹ a cryptographic hash function. As such, it has preimage resistance: given a hash value, there is no way to find a string with that hash, except by trying all strings until you find one that works. Therefore you'll have to try all possible inputs, i.e. all strings that contain the known substring. (You can of course be smart about it: try the most likely strings first, if there's such a thing as most likely in your scenario.)

If you do find a string, you can be confident that it's the right one. Cryptographic hash functions also have the collision resistance property: it is infeasible (i.e. practically impossible) to find distinct strings with the same hash. There is no way to find another string with the same hash, of length N or otherwise.

¹  As far as anybody knows, or at least anybody who speaks publicly on the topic.


What are the ways to generate Beaver triples for multiplication gate? So to speed up the function evaluation we use beaver trick, to generate raw data in the offline phase and use them in the online phase to get the output share for the multiplication gate. So what are the methods to generate these raw data i.e. multiplication triples ?

Nowadays, the most standard method is to use oblivious transfers. Oblivious transfer involve a sender with two messages $(m_0,m_1)$ and a receiver with a selection bit $b$. At the end of the protocol, the receiver learns $m_b$ (and gets no information about $m_{1-b}$) while the sender gets no information about $b$.

Suppose Alice and Bob want to generate a random Beaver triple over $\mathbb{F}_2$ (that is, a Beaver triple of shared bits). Alice picks $(x_A,y_A)$ at random from $(\mathbb{F}_2)^2$ and Bob picks $(x_B,y_B)$ at random from $(\mathbb{F}_2)^2$. Alice now picks a random bit $r_A$ and acts as sender in an oblivious transfer with the following pair of inputs: $(r_A, x_A \oplus r_A)$ ($\oplus$ denotes the xor). Bob uses $y_B$ as selection bit. If $y_B$ is $0$, Bob learns $r_A$; else, he learns $ x_A \oplus r_A$. Therefore, Bob learns $x_Ay_B \oplus r_A$.

The players now do the same thing in the other direction with a random bit $r_B$ and the bits $(x_B, y_A)$, so that Alice learns $x_By_A \oplus r_B$. Alice computes $z_A \gets r_A \oplus x_Ay_A \oplus x_By_A \oplus r_B$ and Bob computes $z_B \gets r_B \oplus x_By_B \oplus x_Ay_B \oplus r_A$. You can easily check that $z_A \oplus z_B = (x_A \oplus x_B)\cdot(y_A\oplus y_B)$, therefore $(x_A,x_B), (y_A,y_B)$, and $(z_A,z_B)$ form shares of a Beaver triple over $\mathbb{F}_2$.

Oblivious transfers require (expensive) public key primitives; the most common construction are based on the Decisional Diffie-Hellman assumption (like the ElGamal cryptosystem). However, it was shown some years ago that one can generate an arbitrary number of oblivious transfers, starting from a constant number of OT (say, 80) and "extending" them using only very cheap primitives. Therefore, players can generate arbitrarily many Beaver triples while using only a constant number of public key operations, and then only cheap primitives (hash functions). This is the reason why OT is nowadays seen as the best choice to construct Beaver triples. Other classical primitives used to generate Beaver triples include homomorphic encryption. The advantage, which might make it relevant in some cases, is that it allows to generate Beaver triples over large order fields without having to rely on the bit decomposition of one of the inputs (generating a single Beaver triple on a large order field $\mathbb{F}$ requires $O(\log |\mathbb{F}|)$ oblivious transfers in general, although there are methods to improve that).


Is the RC4 KSA the same as an extractor? I am studying the RC4 stream cipher, particularly when it used to be applied in the TLS/SSL protocol.

Is it safe to say the KSA acts like an extractor taking in the shared secret key, k (between 128bits and 256bits) and then blows it up to a scrambled 256 byte array?

Then this is essentially used as a "seed" for the PRGA that comes next?

If the above is correct, then what is the difference then between an extractor and a key-scheduling algorithm?

NOTE: I have zero intention of using RC4 in any TLS application, this is purely for my own education.

It would not work as a randomness extractor as there is a detectable correlation between the key, the internal state, and the output.

http://saluc.engr.uconn.edu/refs/stream_cipher/fluhrer01weaknessRC4.pdf
https://eprint.iacr.org/2011/448.pdf

It does expand the key by concatenating it until it fills a 256-byte array and it is used to mix the internal state. So it acts like it, but it is not one, and should not be used as one.


Role of Fermat's little theorem in the proof of correctness of ElGamal signature In the Wikipedia article about the ElGamal signature scheme it is written, that Fermat's little theorem is used in the following proof of correctness:

From the signature generation in ElGamal we can derive, that:

$$H(m) \equiv xr + sk \pmod {p-1}$$

Then - the article states - Fermat's little theorem implies the following:

$$\begin{align}
g^{H(m)} &\equiv g^{xr}g^{ks}   &\pmod p\\
         &\equiv (g^x)^r(g^k)^s &\pmod p\\
         &\equiv (y)^r(r)^s     &\pmod p
\end{align}$$

The proof makes sense to me, i am just wondering, in what way Fermat's little theorem is used here, instead of just regular properties of exponentiation.

Thanks to fgrieu's comment above and the following quote from here (PDF):

  Theorem:

  Let $p$ be a prime and let $a$ be a number not divisible by $p$. Then if
  $$ r \equiv s \pmod {p − 1} $$
  we have
  $$ a^r \equiv a^s \pmod p$$ In brief, when we work $\mod p$, exponents can be taken $\mod{p − 1}$.

I (think i) understood, how the first (implicit) step relies on Fermat's little theorem:
$$\begin{align}
g^{H(m) \pmod{p-1}} &= g^{xr+sk \pmod{p-1}} \\
g^{H(m)} &\equiv g^{xr+sk} \pmod p
\end{align}$$


AES-CBC decrypts to wrong output? Someone I know showed this to me, and I can't put a finger to why it's happening. Am I missing something?
They encrypt the text, and the output is really guessable. $u\to t$, $i\to h$ (it's one letter behind), the $?$ are just spaces.

They trick you with the IV. The IV must be the same for encryption and decryption so that the encryption has the functionality that is;
$$ m = D_k(IV,E_k(IV,m))$$
To surprise you, they modify the IV according to their desire but you failed to see that. This is the more general case of the Bit-Flipping attack on the CBC mode.
This attack works because the message has only one block and the change on the IV only modifies the first block. Nothing special there.


Final Permutation in Feistel function As the final permutation of the Feistel function is the inverse of the initial permutation, it undoes the initial permutation.So how is this helpful?

In DES we must distinguish the Initial Permutation; the Final Permutation, which by definition is IP-1; and the final swap (or lack thereof), which makes the last round different from the others. The final swap is formally in the specification of DES as a definition of the preoutput block as R16L16, when input and intermediary blocks are LiRi.

The rationale of making a Final Permutation parallels that of the Initial Permutation: in the original 8-bit-hardware implementation of DES, IP allows loading the plaintext as eight byte-wide accesses, with each of 8 bit of the IC's data bus line leading to the input of 8 shift registers in the IC, holding L and R. FP allows unloading the ciphertext by the same mechanism (the output of the 8 shift registers leads to the data bus). IP of decryption undoes FP of encryption, while FP of decryption undoes IP of encryption, because FP is IP-1.

The final swap consists in making an additional exchange of Left and Right registers after the last round (or, to the same effect, not doing in the last round the exchange of Left and Right registers performed in the other rounds). The rationale is that, combined with FP being IP-1, it makes encryption and decryption identical except for preparing subkeys in reverse order. That identity simplifies hardware and software that must adapt to both roles (when subkeys are precomputed as is standard practice for speed-optimized software implementations, the exact same code does encryption and decryption). Without final swap, in order for decryption to undo encryption, we'd have to move the exchange of Left and Right registers at the beginning of a decryption round, rather than at end in an encryption round.

IP and FP do not exist in all Feistel ciphers; they are rather specific to DES. On the other hand, the final swap technique works for any symmetric Feistel cipher, and is often considered an integral part of that design pattern.

Note: in some implementations or descriptions of DES (but not the standard), FP is taken to include final swap then IP-1.


How to handle multiple key-agreements If I would use two different key-agreements e.g. SIDH and ECDH how would I handle these both derived keys?

Is there a different between XOR or SHA-256 the two keys? (Would one reduce the level of security?)
Or is there another safe method?

1. XOR

key = SIDH ⊕ ECDH

2. SHA-256

key = SHA-256(SIDH, ECDH)

If you are doing an ECDH key agreement $[a]B = [b]A = [ab]G$, you should be hashing the ECDH shared secret to derive a key $k = H([ab]G)$ anyway instead of using $[ab]G$ directly, for various reasons.  More than that, you should hash the transcript of the key agreement in too, giving $k = H([ab]G, A, B, \mathit{etc.})$.  Here $H$ might be SHA-256 or HKDF-SHA256 or BLAKE2b, with inputs encoded uniquely so that two transcripts can't collide.

The same goes for essentially any fancy mathematical magic for agreeing on an element of a fancy mathemagical structure, so it applies to SIDH too.  It doesn't really matter much whether you do $H(\mathit{ecdh}, \mathit{sidh}, \mathit{transcript})$ or $H\bigl(2, H(0, \mathit{ecdh}, \mathit{transcript}), H(1, \mathit{sidh}, \mathit{transcript})\bigr)$, where $\mathit{ecdh}$ and $\mathit{sidh}$ are the mathemagical elements you summoned from the ECDH and SIDH spells.  What matters is mainly that you encode all of the inputs to the hashes uniquely and label each hash input uniquely with its purpose in the protocol (done here using fixed-width numbers 0, 1, 2, but could be done using, say, length-delimited strings).


How hard are discrete logarithms problems in $\mathbb Z^{*}_{n}$ and $\mathbb Z^{*}_{n^2}$, where $n$ is the RSA $n=pq$ Use the notations form the Wikipedia article Paillier Cryptosystem
, assume that the chipertext $c$ and $c^{\lambda} \mod n^2$ are both given, is it possible to compute $\lambda$ easily?

No, it is not possible to compute $\lambda$ easily.  Specifically, if you have a black box that, given a random instance $c$, $c^\lambda \bmod n^2$, was able to recover $\lambda$ with nontrivial probability, you can use that to factor $n$ with nontrivial probability.  Hence, if we believe the factorization problem is hard, we must also believe that this modified discrete log problem is hard.

One way to arrive at that is "if you can find $\lambda$ given a random instance, you can compute (a multiple of) the order of a random element, and if you can do that, you can factor".

To compute this order using the black box, you take your random element $r$, select a random exponent $k>1$ ($k$ needs to be relatively prime to $pq(p-1)(q-1)$, making it a large random prime works), and then query your DLOG oracle for discrete log $(r^k)^\lambda = r \bmod n^2$; once you know $\lambda$, you also know that $r^{k\lambda-1} = 1 \bmod n$ (because if $(r^k)^\lambda = r \bmod n^2$, then $(r^k)^\lambda = r \bmod n$ as well).  That is, the order of $r$ is a divisor of $k\lambda-1$.

Once you have that multiple of an order $x = k\lambda-1$, you can then factor $n=pq$ by considering the odd value $y = x/2^j$, and then for random values of $s$ ($r$ works well for an initial guess), consider the sequence $(s^y, s^{2y}, s^{4y}, ..., s^{x})$.  If we see a 1 in the sequence proceeded by a value $z$ other than 1 or $n-1$, then we can factor; the factors are $gcd(n, z-1)$ and $gcd(n, z+1)$.  And, if $r$ was chosen randomly, then with high probability this procedure will find a factorization after a modest number of random $s$ values.


How to prove security of a randomized encryption algorithm? I have designed an random encryption in public key setting. I am convinced about its security guarantee but I need a formal way to prove its robustness. How can I prove the security of this random-public-key-encryption algorithm? Any proof method such as induction-method, proof-by-contradiction-method or anything else?

I am trying to publish this algorithm in a journal paper. This is why I need a formal proof.

What you want to do is the right way. However it's not an easy one.

What you really want to do is to show the following implication:
$$
\newcommand{\hard}{\operatorname{hard}}
\newcommand{\assumption}{\text{assumption}}
\newcommand{\secure}{\operatorname{secure}}
\hard(\assumption_1)\land\ldots\land\hard(\assumption_n)
=\bigwedge_{i=1}^n\hard(\text{assumption}_i)\\
\implies\secure(\text{cryptosystem})$$

for a (hopefully) small number of assumptions which are already well-studied.

The usual intuition for such proofs is a proof-by-reduction, which is a logical contraposition:
$$\neg\secure(\text{cryptosystem})\implies\bigvee_{i=1}^n\neg\hard(\assumption_i)$$
Meaning that you would need to show that breaking the security of your cryptosystem implies that any of your assumptions is not hard.

Of course you first need to find out what "$\hard(\assumption_i)$" and "$\secure(\text{cryptosystem})$" actually mean. The latter is a (preferably) strong security definition, most likely from this list. The former very much depends on the actual assumption at hand and you need to look at the actual, precise definition of said assumption. For example this blog post covers RSA and this one covers the typical DH assumptions.

Now the final and actually hardest part: How to actually make the proof. There's no simple answer to this question. For example you could give game-hopping a look as well as simulation based proofs. You could also look whether proof / verification tools can help you along the way, such as described by Biv here and here. There isn't much more to say on this, except for: Look at the references given, work your way from there through the references they give, continue going through the references until you have an understanding of these proofs and are able to carry out the one you need. It will probably be a hard and / or long journey, but it will pay off.


End to end encrypted web chat app with stored messages in database I am working on a web app with an integrated chat. All chats can only occur between two users - not more, not less.
I am very concerned with security, so I would like to encrypt all chat messages with end to end encryption. My favored protocol so far is the Signal protocol.

However, the problem of web apps is that it's not possible (as far as I know) to reliably store the private key of a user. Also, you can't really save anything locally (i.e. in the local storage of the browser) because the web app can be accessed from everywhere and the user should be able to view all messages as soon as he logs in wherever he might be.

So my solution would be:

User X creates an account in his browser.
A key pair is created and the private key is encrypted symmetrically using the entered password.
The public and the encrypted private key are sent to the server where they are stored in the database.

Then, if a user Y wants to start a chat with X:

Y's message is encrypted in his browser two times:

Once with the public key of user X, stored in the database,
and then with the password of user Y.

Both encrypted version of the messages are transmitted via WebSocket to the server.
The server sends the first version of the message to user X if he is currently logged in. Also, it stores both versions of the message in the database.
The browser of user X decrypts the message(s) received from the server as soon as he is logged in and displays them to the user.

Each time user X logs in and views the chat:

The user logs in and receives the encrypted private key. Using the entered password, the private key is decrypted.
The already existing chat messages are requested from the server.
Locally, the messages are decrypted with the private key.

Is this safe at all?
I think that this would prevent some of the following disadvantages when researching other methods:

The server does not have to decrypt and re-encrypt all messages when a user changes their password.
The browser does not need to generate a new key pair each time a user logs in at a new location.
The messages can be stored long term for both users to be easily read.

One potential vulnerability I thought of would be:

Because there are two versions of the message stored in the database, a potential attacker could have an easier job of brute forcing the original content. Though, this might be prevented by signing both messages with some userspecific value, i.e. the username.

Just keep all user-associated information encrypted using the user's password. Be sure to use a secure password-based key-derivation function (PBKDF2 seems to come to mind but personally I prefer Argon2) because passwords make terrible encryption keys. Here is an example of how it might be done:

User generates random encryption key (master key or MK) on the client-side (not based on a password, actually random)
User generates a key-encryption-key (KEK) from their password
User encrypts MK using the key KEK
User uses MK to encrypt their data, within their browser.

This way, if a user is to change their password they can simply re-encrypt MK with a new KEK. Or, they have the option to change their MK and KEK if they think their MK has been compromised. You don't need anything more, since the encryption does the work. Everything else can be done as if client-side storage is available, since it's secured with MK.
This sounds mostly like what you're doing, but it doesn't sound like you're using a KEK or key-derivation function, both of which should be the case if the system is to be secure and scalable.

A key pair is created and the private key is encrypted symmetrically using the entered password.

Encrypt with MK, not the password

Y's message is encrypted in his browser two times

Because there are two versions of the message stored in the database, a potential attacker could have an easier job of brute forcing the original content. Though, this might be prevented by signing both messages with some userspecific value, i.e. the username

This doesn't affect security, assuming you do it right. Each message should be encrypted with a random IV for this to work. Make sure it's random, and unique to each message. This will double the amount of information you need to encrypt, but anything else is insecure. The IV can be known by the server, without compromising security, and as such, needs not be encrypted.

Keeping "raw" password in browser as a key for symmetric encryption/decryption maybe a concern.

This is correct. Definitely derive the key from the password.

Passwords are limited in length, and may not provide crytographic high strength if used as symmetric key directly. One option could be to derive the key from it

Definitely do this! Use a function specifically designed to derive encryption keys from passwords.

var key = crypto.createCipher('aes-128-cbc', 'secret password');

This is a bad idea (sorry, but it is). AES isn't a key-derivation function. Please don't use AES to derive keys! use PBKDF2 or Argon2; they're specifically made for exactly that purpose.

This approach wont allow server-side search on the chat messages. Client side search can be implemented on a limited text loaded into UI component.

That is correct. However, if I were the one using the service I'd expect that; I'd automatically distrust anything that allowed server-side search.

The server does not have to decrypt and re-encrypt all messages when a user changes their password

This can only be done if you use the MK-KEK scheme I described. I should also add, the client should do the encrypting and re-encrypting, not the server.
Changing the password means you have to at least re-encrypt something. Also, if the MK is compromised you still have to re-encrypt everything. Be ready for that, or risk sacrificing security (which to me is an unforgivable sin).


DES: histogram differences between plaintext and ciphertext Using CrypTool I encrypted a plaintext with "DES CBC" and I genereated the histogram of plaintext and ciphertext.
The histogram shows the relative frequency of each of the characters in the document.

When I did the same with "Caesar" cipher based on online tutorials, it was possible to find the correlation between some characters comparing their frequency that I could see in their histograms.

But that it is not possible for DES. I try to find out why this is not possible. What properties of the DES are responsible for this?

Lookup avalanche effect either in wiki or our tags here. Essentially, the slightest change (any single bit) of the plain text leads to 50% of all the other bits (on average) changing across the full width of DES' 64 bit block size.  This totally obfuscates any correlation between the plain text characters.

"Caesar" cipher doesn't exhibit avalanche being only a substitution. It simply keeps the correlations and encodes them to other letters.


Security of HKDF when part of output is exposed There is a system in which Alice and Bob need to establish a secure communication channel. Their conversation happens via a "public" server whose only purpose is to rely messages between users. This server must never be able to decrypt communications.

With the protocol that Alice and Boo will use, the first time they want to talk, Alice generates a 128-bit key that is able to exchange with Bob in person.

This is the only communication that Alice and Bob can have in a trusted manner (in person) before begin communicating through the server above mentioned.
As stated, this communication is one-way (Alice-to-Bob) and Alice is only able to give bob at most 128 bits of data.

Now, Alice and Bob connect to that server and need to find each other by going in the same "stanza".
Since the only knowledge that Alice and Bob have of each other to meet is that 128-bit key, they expand this key (using HKDF) to create:

A 256-bit AES key for encryption.
A 256-bit HMAC-SHA256 key for authentication.
A 128-bit "stanza-id" that will be advertised publicly.

Since the server allows any client to choose any arbitrary stanza-id on where to sit and wait for messages, Alice and Bob are able to meet each other in the same stanza, and even if someone is able to listen to them, their communication is secure since it is encrypted and authenticated.

My questions are:

Does exposing part of the HKDF output publicly weak the other "private" parts or leak any other information?
Does it make sense to use AES-256 when the key originates from only 128-bits of entropy?
Does allowing any client to chose any arbitrary stanza-id put the server in danger in any way?

In a secure KDF, the output is indistinguishable from random. In particular, all the output bits are independent, so revealing some of the output doesn't give any indication about the other bits.

Hugo Krawczyk's HKDF definition paper proves that HKDF is a secure KDF under some reasonable assumptions on the underlying hash function which SHA-2 is believed to meet (theorem 4).

With a 128-bit root secret, you only get at most 128-bit protection for anything based on derived material, even if you use a stronger algorithm. That's ok: 128-bit is generally considered unbreakable until at least 2030, and it doesn't get any better than unbreakable.

Allowing clients to pick arbitrary stanza-ids doesn't harm the server directly. It's just passing data through. It means that the server won't be able to use stanza-ids to meter communication, so you'll have to rely on some other means to avoid denial of service attacks (if anybody can submit data to your server, someone can upload terabytes that they won't be using, and you have no way to detect that).

Note that even if the server is unable to make a link between Alice and Bob through pure cryptography, it can make informed guesses by observing who uploads and downloads what data when. It'll take more than this part of the protocol to achieve some measure of anonymity.

I recommend using a proper authenticated encryption mode such as GCM, rather than building your own with AES and HMAC. You have less risk of an implementation mistake that way.


Using platform-level RNGs for key derivation with hash functions like BLAKE3? So I've read stack overflow questions like this one. What I'm wondering is a bit more specific though: I'm really liking what I'm seeing with BLAKE3. (I suspect that this hash function is relatively unknown, though that's not surprising given its newness.) This would, however, also apply to BLAKE2 (and maybe BLAKE, I'm not sure). BLAKE3 defines a third mode of operation, derive_key. As the paper indicates, it takes a hardcoded context string and key material and derives a key using that information. My question, to be precise, is this: assume that I am in an embedded system with a BLAKE3 implementation available, and I want to derive a key for encryption/decryption purposes. Would it be safe to use an architecture-level instruction like RDRAND or RDSEED (x86) or RNDR (ARM) to generate this key material, and then derive a key that way?

Would it be safe to use an architecture-level instruction like RDRAND or RDSEED (x86) or RNDR (ARM) to generate this key material, and then derive a key that way?

Would you need to derive the same key twice (for example, you're using the key to encrypt data from Alice to Bob, so both Alice and Bob need to derive the key; or if you're using the encrypt stored data, so you need to derive the key both when you store the data and when you retrieve it)?
If so, then RDRAND won't give the same data twice, hence you won't derive the same key.
If not, that is, you are generating the key only once (and storing it if you need to refer to it later), then it should be safe.  On the other hand, there may be little reason to bother with a key derivation function at all; just invoke RDRAND, and use that as your key...


PBKDF2 when dkLen and hLen have the same size I was reading RFC 2898 and something is not clear to me. When I use PBKDF2 with SHA-256 and I want a derived key with length 32 bytes (the same length as my hash function output), your derived key only exists out 1 block (l = 1) of size hLen = 32 bytes.

This seems trivially, but i want to be very sure! Is this correct?

The output length of the F step of PBKDF, i.e. the T_i each are of the size of your hash function's (or actually: your PRF's) output.

So yes, when the desired output size is as large (or smaller) as the hash function output, we have l = 1 and thus only one call to F(P, S, c, 1).

I suppose this is also the most common way to use PBKDF-2, the extension to longer generated key sizes is only included to make the scheme more generally usable.


Is there such a thing as shortcutable key stretching? I'm curious if there's a cryptographic (or mathematical) technique for key stretching that

allows someone with a secret to quickly derive the final key,
requires a deterministic number of rounds for stretching (ie is not probabilistic) for someone that does not have the secret.

Does such a thing exist?

For context, I think this would be useful for a regular pseudo-atomic information exchange. Two parties would encrypt the information they want to exchange each with a key they derive using a seed and an additional secret, exchange the encrypted info, exchange the seeds, then exchange the additional secret. That way, one party can't simply wait until they've received the other key to send their key - even if they delay the last step, the counter-party can still derive the key (tho it will take more time). And if they delay the second-to-last step, the counter-party will know they're not cooperating.

Let $p$ and $q$ be secret uniform random primes, and define $n = pq$.  Consider $s = 2^{2^t} \bmod n$.

Without knowledge of $p$ or $q$, the best way we know to find $s$ is to start with $2$ and square it $t$ times successively.  We can tune $t$ to force the other party to take arbitrarily many steps.
With knowledge of $p$ and $q$, we can use the shortcut $2^e \equiv 2^{e \bmod \lambda(n)} \pmod n$ by Carmichael's theorem, since $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$; then it only takes one division of $t$ by $\lambda(n)$ and about $\log_2 n$ squarings and multiplications modulo $n$ to compute the answer, no matter what $t$ is.

But suppose you use this protocol.  What happens when one of the parties skips town just before the protocol is done?

  BOB: Hey, Alice, the combination to the box the magic words are in is $2^{2^{t_b}} \bmod n_b$ where $t_b = 1\,000\,000\,000\,000$ and $n_b = \dotsb$.

  ALICE: Great!  The secret to the meaning of life, the universe, and everything is encrypted with the key $2^{2^{t_a}} \bmod n_a$ where $t_a = 3\,141\,159\,265\,359$ and $n_a = \dotsb$.

  BOB: Awesome, thanks!  By the way, $n_b = p_b q_b$ where $p_b = \dotsb$ and $q_b = \dotsb$.

  ALICE: Ha-ha, sucker!  Have fun chasing meaning while I go open your box of magic words!

  BOB: Blast!  It will take my ASIC three hundred years to compute this.

Another approach you could try—which doesn't involve shortcuts—is to have each party reveal the secret bit by bit (or letter by letter) in lock-step:

  ALICE: The first letter of my secret is C.

  BOB: The first letter of my secret is V.

  ALICE: The second letter of my secret is H.

  BOB: The second letter of my secret is L.

  ALICE: The third letter of my secret is U.

  BOB: The third letter of my secret is F.

  ALICE: The fourth letter of my secret is M.

  BOB: The fourth letter of my secret is E.

  ALICE: The fifth letter of my secret is P, spelling out CHUMP, because you've given me enough to guess the rest of your secret by brute force and I ain't given you diddly squat!

The trouble is twofold:

Bob shouldn't have proceeded to divulge any of the secret without a verifiable proof that what Alice gave is actually part of her secret.
The protocol favors whichever party has more computational power—that party can abort the protocol at any time and leave the other one in the dust.


Shamir's Secret Sharing - Impersonating the Dealer I understand that Shamir's Secret sharing has nothing to do with the methods that are used to share and later recover a key.

That means then, the secret is only as secure as the methods used in sharing the key, because I can try to impersonate the dealer.

If the dealer shares their private key in some fashion, but later loses the private key, the dealer needs to contact enough shareholders (k out of N) to reconstruct the key.

If I assume this is done in a naive fashion, e.g. a web request, then anybody can do that.

If we secure the way is done, let's say with a password, then the key is only as secure as the password.

If the list of shareholders is secret, then the it's only as secure as the list of shareholders (where and how it is stored).

If we secure the communications with a private/public key method, then the dealer needs to have a second private key that they can use when they've lost the first one, and the key is only as secure as the second private key. The dealer is trying to secure the first private key by sharing... but then gets a second private key they need to secure. That doesn't make sense.

Is there a way to solve this problem? Or - this is my conclusion - is it that secret sharing is simply not suitable for keeping a key secure?

Yeah, as stated, that's an unsolvable problem.

Basically, if you assume that the dealer loses everything that would let the shareholders (or anyone else) distinguish them from some random stranger, then there's nothing they can do that some random stranger couldn't also do.

The typical real world solution is to let the shareholders identify you by some physical means, such as by your fingerprints, iris patterns, DNA or just general familiarity with your physical appearance and personality.  Such biometric IDs are hard to accidentally lose (especially if there's some redundancy) and even harder for someone else to copy (at least in a way that would fool a careful human inspector; unfortunately automatic checks are often quite a bit easier to trick).


RSA: Detecting period of unconcealed messages Referencing:
Project Euler Problem 182 Clarification

I'm trying to determine the (minimum) period for a given value of $(p, q)$.

For a simple case where $p=19,q=23$ the period of repeating order is 132 (which I assume is from 2x2x3x11, the prime factors of 18 and 22).
It's trivial to explore the number-space of 132 to see where $\gcd(e,\phi)=1$ and $\gcd(e,p-1)=2$ and $\gcd(e,q-1)=2$. Same goes for when $p=1009$ and $q=3643$ and I calculate the period to be 152964.

But what about for larger values for $p$ and $q$, like $p=232919$, $q=233117$?

Given that $\phi = 54296912488$, and the prime factors of $p-1$ are 2, 7, 127, 131 and the prime factors of $q-1$ are 2, 13, 4483 then I calculate the period is 27148456244 (is there any possibility of reducing this number-space?)
Is there any other order/period that can be used to my advantage in order to drastically reduce the number of gcd calcs that I have to perform?

Convention states that $P > Q$.
At best, there are 9 unconcealed messages. I'll refer to these as $U_0$ through $U_8$.
Here are some relationships between these.

\begin{align*}
U_0&=0\\
U_1&=1\\
U_2&=kP, &&\text{where $k=1$ to $Q/2$. Test if unconcealed. Stop once you find one.} \\
U_3&=kQ, &&\text{where $k=1$ to $P/2$ (try $U_2\pm1$ before trying multiples of $Q$).} \\
U_4&=U_2+U_3 \bmod N \\
U_5&=N-U_4 &&\text{(also, $U_6+U_7 \bmod N$)} \\
U_6&=N-U_3 \\
U_7&=N-U_2 \\
U_8&=N-U_1 \\
\end{align*}

Looking at this example, there is no period for unconcealed messages. Also note $e$, $\phi$, and Carmichael values are not needed.

$P=47, Q=23, N=1081$, where $e$ results in 9 unconcealed messages.

\begin{align*}
U_0&=0 \\
U_1&=1, &U_8&=1080, &U_1+U_8&=N \\
U_2&=46, &U_7&=1035, &U_2+U_7&=N \\
U_3&=47, &U_6&=1034, &U_3+U_6&=N \\
U_4&=93,  &U_5&=988, &U_4+U_5&=N \\
\end{align*}

The most you'll need to test is $(P+Q)/2$ and will often be far less. This reduces the number-space you need to search.

For clarity:

$$U_0=N \bmod N, \quad \text{or $0$}$$

The first pair is $U_1=N+1 \bmod N$ and $U_8=N-1 \bmod N$. Their sum equals $N$.

The second pair, $U_2$ and $U_7$ are a multiple of either $P$ or $Q$ and sum $N$. If the is a multiple of $P$, then you only need to search to $Q/2$ as these mirror each other. Once you go beyond $Q/2$ you are testing the same values against the other half of the pair.

Similarly, the third pair, $U_3$ and $U_6$, will be a multiple of the other factor with the same consideration (sum $N$ and test to $P/2$ assuming this is a multiple of $Q$). This would be $Q$ if the second pair were a multiple of $P$, and $P$ if the second pair were a multiple of $Q$. The small numbers which I've tested, $U_3$ is $U_2\pm1$. Which means $U_6$ is also $U_7\pm1$. I don't know why this is, or if this holds for larger numbers. I have yet to code this and test.

The fourth pair, $U_4$ and $U_5$, also sum $N$. This pair is calculated from pair two and three. $U_4=U_2+U_3$, you can append '$\bmod N$' for consistency, but since both are $\mathit{factor}/2$, these will always sum less than $N$. Conversely, $U_5$ is the sum of $U_6$ and $U_7$, both on the high side of $\mathit{factor}/2$ due to their relation of $U_2$ and $U_3$, therefore will sum greater than $N$ and will require '$\bmod N$'.

So, three unconcealed messages are known, $U_0$, $U_1$, and $U_8$. By discovering $U_2$ and $U_3$, the remaining four can be calculated. In the process of discovering $U_2$ and $U_3$, the multiple, $k$, ranges from $1$ to $\mathit{factor}/2$. You can stop once a factor is found because the compliment is calculated. Then test $U_3$ as $U_2\pm1$ before testing multiples of the opposite factor.

When the selection of $e$ results in more than 9 unconcealed messages, these same 9 are always the same, as they are based on $P$ and $Q$.

There are three simple formulas, $U=k*\mathit{factor}+1, U=k*\mathit{factor}, U=k*\mathit{factor}-1$, which demonstrate concisely how and why these 9 relate to each other the way they do. It was an awesome discovery and I'll share in another post.


Deterministically generate a RSA public/private key pair from a passphrase (with sufficient entropy)? Is it possible to deterministically generate public/private RSA key pairs from passphrases?

Would giving the (key generating) algorithm data made from key-stretching the passphrase (instead of a source of random data) be sufficient and strong?

Extra credit:

Is it possible to generate a key pair from one public and one private passphrase, such that the public key can be generated from only the public passphrasse?  (The private key can use both.)

(I'm trying to deal with the difficulties in using RSA keys as pasted/exchanged things.)

Yes, it is possible to deterministically generate public/private RSA key pairs from passphrases. For even passable security, the passphrase must be processed by a key-stretching function, such as Scrypt (or the better known but less recommendable PBKDF2), and salt (at least, user id) must enter the key-stretching function; the output can then be used as the seed material for the RSA key generation. This works for any public-key cryptosystem.

Security is equivalent to what you have in e.g. PGP/GPG when assuming an adversary has access to the private key file protected by the (unknown, key-stretched) passphrase. However, there are drawbacks:

one is giving away the considerable degree of security obtained, in normal practice, by not making the  private key file public; that first line of defense is lost, only the (stretched) passphrase remains;
it is impossible to change the passphrase while keeping the same key and the advantage that only the passphrase is needed;
the key pair generation method should remain static; any change will end up with a different key pair; that precludes periodically increasing the passphrase-stretching parameters to take into account hardware progress (while keeping the same key and the advantage that only the passphrase is needed);
as a consequence, there's a very difficult compromise between security for many years with the same public key, and acceptable usage speed now;
as a minor aside, due to variability of RSA key generation time (at least by standard techniques), some passphrases/keys will require more time than others when deciphering or signing.

No, it is not currently possible that a public key of a traditional public-key cryptosystem (not based on communication with some server) can be (re-)generated from something that a typical human is willing to memorize (perhaps, 80 bit worth of entropy, about 24 digits, or 3 phone numbers), much less from a passphrase a typical human can choose and no other information.

In RSA with $n$-bit modulus, we can reduce the public key to about $n/2$ bits with a good argument that it does not reduce security, or to $n/3$ bits with no argument that it reduces security (see this question), but apparently not much further. Other public-key cryptosystem (like ECDSA) have a more compact public key for equivalent security, but it is still several times above that 80-bit limits, thus impractical to memorize, and even painful to key-in from paper. I have strong doubts that we can ever have a reasonably secure public-key cryptosystem with a public key less than 160 bits.


Where do the constants for SHA-1/2/3 come from? My request is:
I need to know the source of constants (shift constants, IV, or S-Box) for the following algorithms:

SHA-1
SHA-2 (all sizes)
SHA-3

Examples:

BLOWFISH uses the hexadecimal values of PI.
SKEIN uses chosen constants from the output of running RJINDAEL in CTR mode on all zeros nonce and all zeros key and counter starting from 0 to one million.
CHACHA uses statements "expand 32-byte k" and "expand 16-byte k".

Regarding the IVs and round constants of hash functions...

The question for SHA1 and SHA2 families have already been answered. Rotational constants were chosen by the designers to make the hash functions secure (or in the case of SHA1, not secure enough). Derivative hash functions such as SHA-224 and SHA-384 use different initial values which are simply the next primes on the list (9 through 16th). SHA-512/t uses different initial values based on the output of a slightly modified version of SHA-512 processing a short string.

SHA3 is a completely different construction. It has no initial values, the working state is simply all 0 bits. The round constants of SHA3 and Keccak are based on a linear feedback shift register, this takes up much less space in code vs hard coded numbers like those in SHA-2, and very cheap to implement in hardware. The rotational offsets for SHA3 and Keccak are a reordered set of triangular numbers modulo the lane size, which for SHA3 is 64-bits. This is also very cheap in both software and hardware, as it is simply a reordering of bits within the state.


Is DDH hard over this group? I'm new to DDH.
Reading this survey, I noticed that DDH is (believed to be) hard in many groups, but most of them are prime-order groups (the only one that is not is the cyclic subgroup of order $(p-1)(q-1)$ of the group of integers modulo $N = pq$).
My question is about the hardness of DDH in this specific composite-order group:

  Let $q$ be a prime such that $p = 4q+1$ is a prime. Is DDH hard in the subgroup of order $2q$ of $\Bbb Z_{p}^\ast$?

Note about this group: My algebra background is fairly basic and I don't even know if this group is guaranteed to exist, and if so, if it guaranteed to be cyclic.

Is DDH hard in the subgroup of order $2q$ of $\mathbb{Z}_p^*$

No, it is not.

If you define the function $F(x) = x^{q} \bmod p$, then for any $x$ is\n the group of order $2q$, we have $F(x)= 1$ if $x$ is a member of the proper subgroup of order $q$, and $-1$ if it is not.  And, exactly half of the elements will be in that subgroup.

You will always have an even number (either 0 or 2) of $F(g^a)$, $F(g^b)$, $F(g^{ab})$ be -1; if you find that an odd number of $F(g^a)$, $F(g^b)$, $F(g^c)$ be -1, then you have determined that is not a DH triple.

This logic applies to any group that has an order with a small factor.


DSA signature generation I am trying to implement given DSA signature generation instructions in python, there are few instructions that I couldn't understand in step 3 and 4.

Let m be an arbitrary length message. The signature is computed
as follows:

generate k (i.e., k is a random integer in [0, q − 1])
r = g^^k(mod p)
h = SHA3 256(m||r)

What does m||r mean? m is a message length r is also a number so what should be the input of hashlib.sha3_256(input) function? As I see in Python it says input must be a string (converted to byte).
s = α · h + k (mod q)

h is a string returned by sha3_256 so how do I multiply it with α?
The signature for m is the tuple (s, h)

The $\parallel$ notation means concatenation. In this case, take the message $m$ (it's a sequence of bits), encode the value $r$ as a sequence of bits, and hash the sequence of bits that consists in $m$ followed by the encoded $r$.

In the step 4, you have a sequence of bits (hash output) that you must somehow convert back to an integer. This is again a question of encoding, but in the decoding direction this time. The underlying theme here is that you must have some convention that lets you encode integers into bits, and decode bits into integers. From a security point of view, the choice of convention is more or less open, but of course it is part of the algorithm specification: signer and verifier must agree on these details, otherwise the verifier won't accept as valid the signatures produced by the signer.

By the way, this is not DSA. DSA is specified by FIPS 186-4. What you describe is known as Schnorr signatures (there are several variants, e.g. on the order of $m$ and $r$ in the concatenation, or whether $s = \alpha h + k$ or $s = \alpha h - k$; all these variants procure more-or-less equivalent security). Historically, the distinction was important: DSA was defined at a time when Schnorr had patented his scheme, and the definition of DSA was carefully made to avoid that patent. Cryptographically, the difference also matters: the "security picture" of Schnorr signatures is better (we can make security proofs on Schnorr signatures, but we don't know how to do that with DSA; and DSA signatures are malleable, a property which is usually harmless but has allowed replay attacks in Bitcoin in the past).


Montgomery Ladder with affin/projective Coordinates So I'm trying to understand why the montgomery arithmetic is fast and what the montgomery ladder is.

With this Post i understood the basic affin arithmetic and Ladder.

So this is not really faster than arithmetic on common weierstrass equations. In the original Paper from Montgomery, he defined the projective arithmetic for adding and doubling.

My first questions are: Is the projective arithmetic faster because of not having a division? Does the ladder have constant time, because there is not division? Does that mean, that the ladder with affine coordinates don't have constant time? ( My idea is, that division in a field is a multiplication with a inverse. For calculating an inverse you need the euklidiean algorithm. This algorithms is not the fastest and can't be computed in constant time)

Then i was looking into the work of Bernstein. In this Paper and in his  Curve25519 he describes a optimized double and add formula. It looks like this:

When i get it right, you can use the montgomery ladder for affine coordinates with the affine arithmetic and for projective coordinates with the projective coordinates. So Bernstein made the shown graph for the projective montgomery ladder in order to give an optimized implementation, where already computed results are used again. So i tried to write the graph into Pseudocode:

R0 = (0,0)
R1 = (x,y)
x1 =
    for i from m downto 0 do:
        if xi = 0 then:
            x,z,x',z' =  R0[0], R0[1], R1[0], R1[1]
            tmp1, tmp2 = x, x'

            x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

            x',z',x,z = (z * x'), (x * z'), (x * x), (z*z)
            tmp1, tmp2 = x, x'

            x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

            z = z*( tmp1 + ((A-2)/4)*z )
            x' = x' * x'
            z' = z' * z' * x1

            R0[0], R0[1], R1[0], R1[1] = x, z, x' , z'
        else
            x,z,x',z' =  R1[0], R1[1], R0[0], R0[1]
            tmp1, tmp2 = x, x'

            x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

            x',z',x,z = (z * x'), (x * z'), (x * x), (z*z)
            tmp1, tmp2 = x, x'

            x,z,x',z' = (tmp1+z), (tmp1-z), (tmp1+z'), (tmp2-z')

            z = z*( tmp1 + ((A-2)/4)*z )
            x' = x' * x'
            z' = z' * z' * x1

            R0[0], R0[1], R1[0], R1[1] = x',z',x, z
return R0

That brings me to my next questions: Where is the x1 comming from, how is it calculated? I saw in his paper, that x1/z1 = X(Q - Q'), but it remains unclear how to substract those points.

Next question is: Is this peudocode logical correct ( at least everything except the x1)?

I hope this are not too many questions!

Maybe one day someone finds this Post again and has the same questions. To you: I hope you're having a great day!

Questions: The projective Arithmetic is faster, because there are only multiplications, squarings, additions to do. The affine Artihmetic is slower, because it takes a lot of time to compute the division. Especially for the big numbers used in modern cryptographie. BUT: That is not the answer to the constant time ladder. Yes affin coordinates with division can't be computed with constant time, but the reason for the projective ladder is a different. You can tranform different types of elliptic curve into the projective form, but for them you can't always use the montgomery ladder. For a long time ( at least when montgomery published his work ) elliptic curve scalar multiplikation on weierstraß was only possible with double and add algorithms. Those algorithms tranformed the scalar into the binary form and had different operations for 1 and 0. Therefor one could approximate how many 1 and 0 there are. The Montgomery ladder has the same operations for both. So there is no difference in time.
Question: With projective coordinates it is only possible to add/double multiples of the same point. The montgomery ladder starts with a given scalar $n$ and Point $P$. In each step two results are calculates $R0$ and $R1$. The important point here is, that those results are either of the form $(n')R0$, $(n'+1)R1$ or $(n'+1)R0$, $(n')R1$. That means the difference between them is always 1. (When you look at the definition for the projective Arithmetic it is clear what that means). For the ladder this means, that $x1$ is always the x coordinate of the starting Point $P$. Therefore it is always the same and must not be computed!

Note: I still can't say, whether my pseudocode is correct or not.


Common password derivation function for different encryption methods I'm writing a simple encryption/decryption library which has the following requirements:

For key derivation functions, support:

$SHA256 \rightarrow bcrypt$ (since $bcrypt$ limits input passphrase length, hash it using SHA-256 first, then feed output of SHA-256 into bcrypt)
$PBKDF2$

For key derivation functions, allow custom iteration count.
For encryption/decryption support:

AES-256
AES-128
Triple DES

Authenticity using HMAC+SHA256 every $n$ bytes

Since I'm potentially using multiple different symmetric key algorithms for encryption and decryption, I have the following problems:

How do I deal with different output sizes from my KDFs?
How do I deal with different key input requirements from my symmetric key algorithms?

First, consider dropping bcrypt, because of its output limitations. If you are concerned about GPUs and ASICs, there's always scrypt. If you decide to go with bcrypt, you won't have 256-bit security with AES-256 and will need to pad the key somehow or disallow that combination.

I would simply call the KDF with a constant 256-bit output, which matches the blocksize of SHA-256-HMAC if you use that as PBKDF2 PRF (so it's ~ as fast as shorter outputs).
Then you can truncate the input of AES-128 to 128 bits and 3DES to 168 bits, which is what PBKDF2 would do anyway.


Can Poly1305-AES be used with AES-256? I'm reading through Bernstein's The Poly1305-AES message-authentication code.

The MAC is predicated on 16-byte block ciphers like AES and produces 16-byte authentication tags. However, Bernstein does not really discuss the block cipher's key sizes, other than to state its a 32-byte key comprised of a 16-byte key and a second 16-byte string r.

I presume Bernstein selected AES-128 because it met security requirements with the most efficiency (i.e., AES-128 is faster than AES-256 because it uses fewer rounds, among other stated criteria). (Bernstein talks about the selection of other parameters, like r, in the section Design Decisions).

If one desired, could Poly1305-AES be used with AES-256? In this case, a 48-byte key would be used.

Yes, Poly1305-AES can safely be modified to use AES-256 rather than AES-128; but if AES is implemented in software beware of not introducing a timing vulnerability in the implementation.

Change of the cipher in Poly1305-AES is explicitly endorsed; quoting D. J. Bernstein's The Poly1305-AES message-authentication code

  There is nothing special about AES here. One can replace AES with an
  arbitrary keyed function from an arbitrary set of nonces to 16-byte strings. (..)
  Perhaps AES will be broken someday. If that happens, users should switch to Poly1305-AnotherFunction. Poly1305-AnotherFunction provides the same security guarantee relative to the security of AnotherFunction.

The reference implementation of Poly1305-AES in software has AES carefully optimized to reduce cache-induced timing dependencies; beware that whatever AES-256 implementation is used is at least as good from this standpoint. If AES is implemented using AES-NI, in hardware, or otherwise in constant time (e.g. on a CPU without cache), that's a non-issue.

More generally, in any system using AES-128, if we can double the key size, we can safely use AES-256 instead from a theoretical standpoint; and if we can tolerate the slightly slower operation, and do not introduce a vulnerability (in particular by timing of cache misses), that's fine from a practical standpoint.


Deterministic Counter Mode with a PRF. What does evaluate at a point mean? This is from Dan Boneh's Lecture where he talks about operating a PRF (AES, DES) in Deterministic Counter Mode.

Dan Boneh says

What we could do is we could use what's called a deterministic counter mode. So in a deterministic counter mode, basically we build a stream cipher out of the block cipher. So suppose we have a PRF, F. So again you should think of AES when I say that. So AES is also a secure PRF. And what we'll do is, basically, we'll evaluate AES at the point zero, at the point one, at the point two, up to the point L. This will generate a pseudo random pad. And I will XOR that with all the message  blocks and recover the ciphertext as a result. Okay, so really this is just a stream cipher that's built out of a PRF, like AES and triple DES, and it's a simple way to do encryption.

What exactly does he mean by "Evaluating at point 0, point 1" etc?
Does he mean encrypting the numbers 0, 1, 2, etc using AES?
i.e. something like
for (i = 0; i < messagelen; ++i)
    plaintext = PadToBlockLength(i);
    Output(AES-PRF(key, plaintext));

where the Output function generates one unit of the PRG with each call.

Let $E(k,b)$ be the AES encryption of message $b$ with the key $k$ where size of $b$ is 128-bit, the key size can be 128,192,and 256 bits.

What exactly does he mean by "Evaluating at point 0, point 1" etc

Evaluating at point 0 :  $c_0 = E(k,0)$
Evaluating at point 1 :  $c_1 =E(k,1)$
Evaluating at point 2 :  $c_2 = E(k,2)$
and soo on
Evaluating at point $\ell$ : $c_\ell=  E(k,\ell)$

$$c_i = E(k,i)$$ and the encryption is performed as
$$C_i = c_i \oplus m[i]$$

i.e. something like

There is no padding there like the PKCS#5 etc; the input $i$ is considered as a 128-bit binary encoded representation of integer $i$, or one can think of it as a 128-bit counter. We can see it more clearly if we consider the below as hex
00000000000000000000000000000001
00000000000000000000000000000002
00000000000000000000000000000003
00000000000000000000000000000004
..
000000000000000000000000000000FF
..

What is defined here is the CTR mode of operation that is first defined for PRFs and introduced by Whitfield Diffie and Martin Hellman in 1979

Privacy and Authentication: An Introduction to Cryptography as an invited paper on Proceedings of the IEEE, 67 (1979), pp. 397–427.

CTR turns a PRF into a stream cipher, as Snuffle turned into Salsa20 and AES into AES-CTR. Note that although not proved the AES is a candidate for a $PRP \subset PRF$. The CTR mode doesn't require the decryption of AES ( or any block cipher) and this is useful to reduce the area of the software/hardware implementations.


Is there any cryptosystem that works on floating point real number? I see that all cryptosystems are work on finite field. But i consider that have any cryptosystem that works on real number (do not consider the round step and it also can be an estimate cipher)

One of the big problems in using floating-point as part of an encryption algorithm is round-off error.  For more details, look at What Every Computer Scientist Should Know About Floating-Point Arithmetic and Round-off error (Wikipedia).

The basic problem is that in floating-point math, not only does round-off error occur, but you can't depend on different computers doing it consistently.  Here is an example where the same source program gives different results (on the same system) depending on whether x87-based floating point (which stores numbers in a 80-bit format) was used rather than the SSE instructions (which use a more traditional 64-bit double precision float).

So to make a floating-point algorithm work, you would have to find a way of avoiding round-off error, while integers and bitstrings avoid that problem entirely.


Which version of ChaCha is more secure? Which version of ChaCha is more secure?

XChaCha20-Poly1305-IETF

ChaCha20-IETF-Poly1305

ChaCha20-Poly1305

I am looking for 256bit strength for large datasets.

I am having trouble disambiguating the delta between these ciphers available in libSodium.

The only difference between these is the nonce size (and, consequently, the internal counter size). The core function is exactly the same. They all offer the exact same security level if they are used as expected.

The trade-offs are described in the AEAD section of the documentation.

XChaCha20-Poly1305-IETF is the one that has the largest nonce size. This significantly reduces the risk of reuse, since it can be randomly chosen without any practical risk of collision. This can also be leveraged to build nonce misuse-resistant schemes.

Unless you specifically need compatibility with a different implementation that doesn't support the XChaCha20 version, this is the one you want to use in virtually all cases.

XChaCha20-Poly1305-IETF is very likely to become the function used by the high-level API in a future libsodium release. Which means that other variants will not be available any longer in minimal builds.

Since your use case appears to be encrypting large messages, the higher-level secretstream API is a better fit. It uses XChaCha20-Poly1305-IETF internally.


Zero knowledge / proof of knowledge sudoku solution I recently started a coursera course "cryptography 1" provided by Stanford university. In one point when explaining zero proof knowledge the instructor mentions the following:

  Almost any puzzle that you want to prove you have an answer to, you
  can prove it is your knowledge. For example let's say that you have a
  sudoku puzzle which you wanna prove you know the solution to, you can
  prove it to Bob In a way that Bob would learn nothing at all about
  the solution but he would still be conviced that you know the solution
  to it.

I am terribly confused by this. How would one prove that he can solve a sudoku puzzle and prove it to X (in this case Bob) without transmitting the actual solution?

Rough scetch, assuming Bob is standing next to you in the same room:

Prepare cards with the correct numbers on them
Lay down the cards according to the setup, face up
Lay down the remaining cards with the correct solution, face down, so that Bob can't see them.

Now you let Bob choose one column, row or sector.

You pick up the cards in that row, column or sector, still not showing them to Bob (turn around face-up cards if there are any), and start shuffling them.
Hand them to Bob, who can see if the cards have the correct numbers (1-9 in the standard game).

After shuffling, Bob can't see any more which card was in which position, he just knows that the set of cards is the correct one. If the face down solution is correct, this will always work out correctly. If you don't know the actual solution, there is a nonnegligible probability to be caught cheating. The chance for catching cheating is quite low tho, so you need to do many repetitions of this to achieve an overall acceptable probability.

All of the processes can be done cryptographically, e.g. face down cards can realized by commitments, shuffling is known from MPC, mix nets, etc.

Edit:
Alternative solution from this blog:
Apply a permutation to the numbers, then you don't need shuffling. However, then you need to prove that the solution actually fits the setup of fixed numbers under that permutation. Therefore, Victor can also choose to see the permuted original puzzle.


Is $\operatorname{negl}_1(n)-\operatorname{negl}_2(n) \leq \operatorname{negl}_3(n)$? Is this statement $\operatorname{negl}_1(n)-\operatorname{negl}_2(n)\leq \operatorname{negl}_3(n)$  true for some negligible function $\operatorname{negl}_3$ and security parameter $n$?

$\newcommand{\negl}{\operatorname{negl}}$
\begin{align}
\negl_1(n)-\negl_2(n)&\leq \left|\negl_1(n)-\negl_2(n)\right|\\
&\leq\left|\negl_1(n)+\negl_2(n)\right|\\
&=\negl_1(n)+\negl_2(n)\\
&\leq \negl_3(n)
\end{align}

where the last statement uses the fact that the sum of two negligible functions is negligible and the rest uses the fact that $\negl_1(n)\geq0$ and $\negl_2(n)\geq0$. For a proof of the last inequality, see this lecture on one-way functions and negligble functions (PDF).


Why does the prover in an interactive proof run in exponential time with the space of the computation? I'm currently trying to gain an understanding of verifiable computation and the strengths and weaknesses of past approaches.

In particular, I've been watching the following YouTube video which talks about interactive proofs as a way of verifying knowledge of a computation. On the slide appearing during time 11:55, it mentions that the prover requires exponential time in the space of the computation. Could anyone explain how this is the case?

I'm also confused as to the statement which says that every deterministic computation has an interactive proof.

I've tried reading the papers below but can't seem to find a clear explanation of these results. Any help would be much appreciated!

References:

  Lund, Carsten, et al. "Algebraic methods for interactive proof
  systems." Journal of the ACM (JACM) 39.4 (1992): 859-868.

  Shamir, Adi. "Ip= pspace." Journal of the ACM (JACM) 39.4 (1992):
  869-877.

The whole point of verifiable computation is to allow the verifier to verify that the computation was performed correctly without performing the computation himself. Since as usual we associate "polynomial-time" with "efficiently computable", if the computation takes poly time there is no point in using verifiable computation, since the verifier can just as well perform the computation himself.

In proof systems in general, if the verifier can determine by himself the truth of the statement in question, there is no need for a prover at all.


Is it possible to change the generator without knowing the private key used? For example, prover sends P = xG and verifier somehow sends back P = xH without learning x.

Is this possible?

For example, prover sends P = xG and verifier somehow sends back P = xH without learning x.

Yes; if the verify knows that $H = yG$, he just computes $P' = yP = xyG = xH$


Rolling your own crypto I know this is usually frowned upon, but supposing you were to roll your own encryption cipher (completely on your own or with a small group of friends, with no peer review possible), what could you do to make your custom algorithm as safe as possible (or rather, to keep the danger of using it to a minimum)? Similarly, what would you do for something like a hash function to make the probability of it having some trivial collision or preimage attack as low as possible?

I understand that there would be no way to approach the security of algorithms like AES, and I have no plans to use custom algorithms for anything important, but I thought it would be informative to think of what some best practices would be for rolling your own cryptosystem if you were to do so.

what could you do to make your custom algorithm as safe as possible

Try to re-use existing algorithms and research to the extent possible.

For instance, suppose you are designing a block cipher (for some reason), and you need some source of non-linearity. Some researchers have already gone to the trouble of finding s-boxes with optimal cryptanalytic stats and minimal implementation costs. There are analogous results for linear layers as well. If you incorporate the results of these works into your design, you can rest assured that they will probably not be the weakest links in your design.

At a higher level, you could also simply re-purpose an existing primitive such as ChaCha and make a hash function out of it (like BLAKE). Or you could re-purpose an existing hash function into a (inefficient) stream cipher, like many others have done/tried to do already.

You (or someone with the same question) might say:

  "But wait, if I do those things then I'm not really coming up with something of my own!"

I think it is safe to say: Symmetric cryptography is pretty much a solved problem by this point.*

You can play around with it if you want, but don't expect to come up with anything (good) that hasn't been done already.

A note about "security"

You need to define your threat model before you can conclude what is/is not good enough in regards to security.

If your only goal is to keep your messages confidential from your grandparents, then you can probably get away with a pretty low quality design (unless your grandpa happens to be Adi Shamir or someone similar of course).

If your goal is to keep your messages safe from nation-state level actors with billions of dollars for their budget and hundreds (or thousands) of cryptographers and mathematicians at their disposal, as well as good old fashioned thugs, then you should probably think twice about the expectations of your design.

If this is your threat model, this is where you need to really stick to pre-existing and battle-hardened constructions. An "oops" in your design could cost you or one of your friends/users dearly.

Note

A secure design and a secure implementation are not the same thing. Coming up with a design that is not broken is only half the battle - you also need a way to implement the design in a way that can't be exploited, and this is a non-trivial subject. Just knowing how to program does not mean that you can create a secure implementation of an algorithm.

Finally

If you read all of that and are still interested in doing it, please remember one thing:

Don't advertise your construction for others to use (outside of your friends who you have of course already informed that it is your own home-rolled construction and could break at a moments notice with no warning... right?).

If you set up a website preaching the virtues of your algorithm, the only people who would use your construction are people who don't know any better. This would be taking advantage of peoples ignorance at the expense of their safety for no good reason. If you did something like that in real life as opposed to cyber space, you would probably go to jail.

Advertising your design will probably just put you on a list of snake oil salesman and destroy your own reputation.

*Take my word for what it's worth, I'm just someone that likes cryptography.


Given a message and signature, find a public key that makes the signature valid (ECDSA) This question is a variant on Given a message and signature, find a public key that makes the signature valid, which discusses the analogous question for RSA.  It was suggested to me by this post over on Bitcoin.SE.

Suppose we are given an ECDSA signature $S$, a message $M_1$, and a public key $P_1$, such that $S$ is a valid signature of $M_1$ with $P_1$.    Let $M_2$ be another message.  Is it known whether we can feasibly find another public key $P_2$ such that the same $S$ is also a valid signature of $M_2$ with $P_2$?

Is there a general name for this kind of an attack (on a general signature algorithm)?

What would be the practical implications of such an attack?  I can't think of any obvious way to use it to cause mischief, but I may just not be creative enough.

(Apologies if this is well-known or if my terminology or notation is bad.  I am a mathematician but not a cryptographer.)

Edit: Thanks to Ricky Demer for the link to the paper by Pornin and Stern (see comment below).  In their terminology, if I have it right, this attack is called a second key construction, and a vulnerable signature algorithm is said to lack destructive exclusive ownership.  They also describe a way that an attacker could use this to produce a fake revocation of a victim's X.509 certificate.

Yes. We can easily generate the malicious public key as in DSS case.
The following attack was proposed in Section 4.5 of Blake-Wilson and Menezes: Unknown Key-Share Attacks on the Station-to-Station (STS) Protocol (PKC 1999).

Let $(G,q,n,P)$ be the ECDSA parameters, where $n$ is the order of the group $G$ over the elliptic curve and $P$ is a generator of $G$.

Let $P_1 = d_1 P$ be the public key, let $M_1$ be the message, and let $S_1 = (s_1, r_1)$ be the signature as you noted.

Since $S_1$ is a valid signature under the public key $P_1$, it satisfies the following equaitons.
$$ s_1 k_1 \equiv e_1 + d_1 r_1 \pmod{n},$$
where $e_1$ is a digest of the message $M_1$, and $r_1 \in \mathbb{Z}_n$ is a $x$-coordinate of $k_1 P$ modulo $n$.

How to construct a malicious public key

Let $M_2$ be the target message.
We now virtually compute a malicious secret key $d_2$ as
$$ d_2 = r_1^{-1} (s_1 k_1 - e_2) \bmod{n}, $$
where $e_2$ is a digest of the message $M_2$.
We then compute a malicious public key $P_2 = d_2 P$, which is
$$ r_1^{-1} (s_1 k_1 - e_2) P = r_1^{-1} (e_1 + d_1 r_1 - e_2) P = r_1^{-1}(e_1 - e_2)P + P_1$$.

Validity of the public key $P_2$.

The public key $P_2$ makes the message $M_2$ and the signature $S_1 = (s_1, r_1)$ valid.
Let us verify the validity of them.

$r_1$ and $s_1$ is in the range $[1,n-1]$, because the signature $S_1$ is valid.
Let $X = u_1 P + u_2 P_2$, where $u_1 = e_2 s_1^{-1} \bmod{n}$ and $u_2 = r_1 s_1^{-1} \bmod{n}$.
By the construction of $P_2$, we have $X = (u_1 + u_2 d_2) P = s_1^{-1} (e_2 + r_1 d_2) P = s_1^{-1} (s_1 k_1) P = k_1 P$.
Therefore, $r_1$ is the $x$-coordinate of $X$.

How to prevent this attack

It is easy to prevent this attack.
We just use a digest $e' = \mathrm{Hash}(pk,M)$ instead of $e = \mathrm{Hash}(M)$.


MacOS doesn't support PRNG reseeding? While researching the topic of random number generation, especially practical aspects of using TRNG devices on different platforms, I found this code in MacOS kernel sources.

int
write_random(void* buffer, u_int numbytes)
{
#if 0
    int     retval = 0;
    prngContextp    pp;

    lck_mtx_lock(gPRNGMutex);

    pp = current_prng_context();

    if (ccdrbg_reseed(prng_infop(pp), pp->statep,
              bytesToInput, rdBuffer, 0, NULL) != 0)
        retval = EIO;

    lck_mtx_unlock(gPRNGMutex);
    return retval;
#else
#pragma  unused(buffer, numbytes)
    return 0;
#endif

Unless I'm wrong, this code snippet means that MacOS's random number generator cannot ever be manually reseeded by writing random data to /dev/random.

Is there some good reason for not allowing user-level reseeding in an operating system's random number generator?

Or maybe there are some other ways to do it? (Using securityd somehow?)

I can only guess at Apple's specific reason for this. But a good reason for not allowing user-level reseeding is explained in a post by D.J. Bernstein here.

Consider two secure sources of entropy $x, y$, and a malicious source $z$:

  Generate a random $r$.
  Try computing $H(x,y,r)$.
  If $H(x,y,r)$ doesn't start with bits 0000, go back to step 1.
  Output $r$ as $z$.

For some crypto applications (i.e. DSA and ECDSA), being able to consistently predict as few as 4 bits of randomness could lead to a complete break (in the case of (EC)DSA, the recovery of the secret key).

In this case, allowing user-level reseeding is precisely what could allow this kind of attack, since it would be the last source added.

Like he says, there doesn't appear to be a good reason to be adding new entropy to the PRNG all the time, since many cryptographic applications (e.g. EdDSA) show it is perfectly possible to deterministically expand 256 bits of quality randomness into an unending stream of secure randomness. Needing to add entropy just indicates your PRNG has been compromised at some point in the past and everything you've done since should be considered utterly broken. Instead, generating high quality entropy once and keeping it safe is a much better idea.

It seems Apple has taken that approach.


Can the key-generation algorithm always be uniform? Assume that the encryption uses $n$-bit keys to encrypt $l(n)$-length messages.

If a symmetric key encryption scheme is defined as $\Pi_{1} = ( \mathrm{Enc}, \mathrm{Dec} )$, then for every $x_{0}, x_{1} \in \{0,1\}^{l(n)}$,
$$ \left\vert \Pr\left[ A (\mathrm{Enc}_{U_{n}}(x_{0})) = 1\right] - \Pr\left[ A (\mathrm{Enc}_{U_{n}}(x_{1})) = 1\right] \right\vert < \varepsilon(n) $$
if it is computational secure.

And if a symmetric key encryption scheme is defined as $\Pi_{2} = ( \mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec} )$, then for every $x_{0}, x_{1} \in \{0,1\}^{l(n)}$,
$$ \left\vert \Pr\left[\mathrm{Gen}(1^{n})=k; A (\mathrm{Enc}_{k}(x_{0})) = 1\right] - \Pr\left[\mathrm{Gen}(1^{n})=k; A (\mathrm{Enc}_{k}(x_{1})) = 1\right] \right\vert < \varepsilon(n) $$
if it is computational secure.

The definition of security is different because the definition of the encryption  is different.
Generally, we do not require that the distribution of $\mathrm{Gen}$ must be uniform.
But it seems that the uniform distribution is always the best.
So, if $\Pi_{2}$ is a computational secure scheme, I want to know whether there exists a PPT algorithm $\mathrm{Gen}'$ which is uniform such that
$$ \left\vert \Pr\left[\mathrm{Gen}'(1^{n})=k; A (\mathrm{Enc}_{k}(x_{0})) = 1\right] - \Pr\left[\mathrm{Gen}'(1^{n})=k; A (\mathrm{Enc}_{k}(x_{1})) = 1\right] \right\vert < \varepsilon(n) $$

For any symmetric encryption scheme, it is not a loss of generality to assume that the key is uniformly distributed: you can let the key be the random coins of the key generation algorithm $\mathcal G$, and incorporate the deterministic part of $\mathcal G$ (i.e., how it generates the key from its random coins) into the encryption and decryption algorithms.

For asymmetric encryption schemes, the same applies to the private key.


What is Group in Diffie-Hellman? I understand how Diffie-Hellman key-exchange works. Mainly, two parties agrees in a prime $p$ and a generator $g$. Then one party selects its private exponenet $x$, computes its public value $g^x \bmod p$. Then, sends it to the second party. The second party chooses a private exponent $y$, then, computes its public value, $g^y \bmod p$ and sends it to the first party. Then, both parties, compute $g^{xy}$ which is the shared secret.

However, in some protocols descriptions, like TLS 1.3, I find them say the client sends "hello message includes Diffie-Hellman public values for the client's preferred groups". What is "group" refers to??

However, in some protocols descriptions, like TLS 1.3, I find them say
  the client sends "hello message includes Diffie-Hellman public values
  for the client's preferred groups". What is "group" refers to??

The term group is a mathematical concept that guarantees that a specific operation doesn't leave a set, that it is associative, that there is a neutral element and that there's an inverse element for each element.

Diffie-Hellman generally operates in such groups.
Just view it like this: Your set is defined by $p$, e.g. for all integers $x$ in the group $0\leq x <p$. You then take an element $g$ from it and apply the group operation (multiplication modulo $p$) a certain number of times to it (whatever your exponent tells you).

Now every choice of $p$ describes its own group and additionally you can choose groups with an entirely different structure such as the points of elliptic curves over prime fields (which makes this ECDH)


Is there a difference between password and key? I encrypt data with this command:

openssl aes-256-cbc -a -salt -in C:\Users\User\secrets.txt -out C:\Users\User\secrets.txt.encs

The program then asks that I...

enter aes-256-cbc encryption password:

Is the encryption password the same as the key? Where is the password or key stored?

Passwords or pass phrases are basically a human equivalent of keys used by algorithms on computers. However, because of that passwords also carry a lot of burden that make them unsuitable as keys:

they are generally much less random than they symmetric key counterparts, because humans are quite incapable as random number generators;
they may be dynamically sized, which makes them unsuitable for many cryptographic algorithms;
they often use a specific set of characters (al alphabet) of their own;
they can be converted to bytes in many ways, if just because there are many character encodings;
the chances of reuse are rather high, so the leaking one password may influence security of many systems.

Generally cryptographers use a PBKDF or password hash to create a statically sized, random byte array from a password. This byte array can then be used as a key, or it can be used to authenticate a person on e.g. a webservice.

These PBKDF's strengthen or stretch the security of the password by a certain work factor. This work factor is usually represented by an iteration count or by a value that is converted into an iteration count (bcrypt uses a work factor which is exponential).

Furthermore, they require a salt to avoid that the same password will create the same hash, even on multiple systems. Because of this rainbow table attacks can be avoided.

Other configuration parameters such as deliberate use of more memory to avoid attacks by specialized hardware or GPU based systems may also be present. See e.g. scrypt. Another common configuration parameter is to allow multiple threads to calculate a single password; it doesn't seem used much.

One configuration parameter that is often missing because it is simply implied is the character encoding. Quite often initial operation to convert characters to bytes is the cause of interoperability issues. Some PBKDF's are also limited to the amount of input bytes (e.g. some bcrypt implementations limit to 72 bits, which can be problem for passphrases).

OpenSSL uses its own PBKDF called EVP_BytesToKey. It uses a rather insecure iteration count of 1, which means that no real strengthening is performed. Furthermore, it also uses a salt, which is stored in the positions 8..15 of the ciphertext, preceded by a magic value "Salted__" in ASCII (take a look at the head of your ciphertext!). You may have to decode the base 64 first though (or compare against U2FsdGVkX1 at the start, most of Salted__ encoded).

The salt is generated during encryption, and with the iteration count it is able to derive a key, which is used to encrypt your plaintext. During decryption the salt is read so it is able to derive the same key - but only if you give it the correct password of course. Once the key is calculated again it can decrypt the ciphertext.

Newer versions have an option to use PBKDF2 instead. This algorithm doesn't disallow hackers to use specialized hardware, but it is at least more secure than the original EVP_BytesToKey with an iteration count of 1.

Neither the password or key is stored with the ciphertext. The password is supplied by the user, the key is derived from that password and the salt.

Note that the ciphertext allows an attacker to perform a so called offline attack, where all computing resources can be used on the ciphertext to try and get to the password by guessing it (using dictionary attacks and such). This is different from web services that can e.g. include a timeout between tries or only allow a certain number of guesses - as long as the password hash is kept secret.

A much more secure way of encrypting files is to use a trusted public key of the receiver. Then the receiver can use their private key to decrypt the ciphertext. Commonly this is used in a hybrid cryptosystem that uses both asymmetric cryptography and symmetric cryptography. However, it does require that the public key can be trusted, so you need a Public Key Infrastructure of some kind to trust the keys. This is what e.g. PGP uses for file encryption.

Often a password may still be used, but that's just to decrypt the private key, and the private key is usually kept on the system of the user, so it isn't available to adversaries.


Constructing a block-cipher from a hash function It is possible to use a hash function to construct a block cipher with a structure similar to DES? Because a hash function is one way and a block cipher must be reversible (to decrypt), how is it possible?

It is possible to build a block cipher out of a great many things. If you want to use a hash function, the classic trick is to follow a Feistel structure, which is, incidentally, the same kind of structure than what DES uses.

The schematics on the Wikipedia page are quite clear; you would use the hash function for the "F" part, which combines one (sub)key and one half of the current block, to produce a value which is to be XORed with the other half of the current block. The beauty of the scheme is that the "F" function is always invoked in the same direction, both for encryption and for decryption. Therefore, it can be a one-way function, like a hash function.

Luby and Rackoff have demonstrated in 1988 that the Feistel scheme offers remarkable security with as little as four rounds, provided that the "F" function is "perfect" and that the cipher block size is big enough (to get the standard "128-bit security" out of the Luby-Rackoff proof, you need 256-bit blocks).

Of course, any concrete hash function cannot be really "perfect" (see for instance this answer) and there are a lot of subtle details which can destroy the security of the best thought cipher structure. As usual, you are strongly advised not to build your own crypto (unless you are quite clear with yourself that you do it for learning and not to actually protect any data of value).

Also, if you build such a cipher, you will probably notice that the resulting  performance is disappointing. With a secure hash function like SHA-256, you could expect an encryption bandwidth roughly 20 times lower than what AES would get you.


How do I prove that this PRNG is easily distinguished from a random sequence of numbers (modulo m)? I was studying Crypto, and this question came up. Using a PRG like the multiplicative congruence generator:

$b_{i+1} = a \cdot b_i \mod m$

How do I prove that the output of this PRG, or any PRG's whatsoever is easily distinguished from a random sequence of numbers?

Well, this is essentially homework (it wasn't assigned, however you are attempting to learn from it), and so I won't give you an explicit answer; instead, I'll try to point you in a direction where you can figure out the answer yourself.

First of all, how would you solve this if you were given the values $a$ and $m$?

Once you have answered that, let us assume that you were given the output of such a sequence, and also given the value of $m$.  How would you recover the value $a$?

Now comes the hard part, let us assume that you were given the output of such a sequence, but did not know either $a$ or $m$; how would you recover the value $m$?

Hint on the last question: let us assume we were given three consecutive values $b_1, b_2, b_3$ with $b_2 = a b_1 \bmod m$, $b_3 = a^2 b_1 \bmod m$; how can we combine the values $b_1, b_2, b_3$ to come up with some value which is a multiple of $m$?  (Hint: consider $b_2^2$ and $b_1b_3$)?  How can we use that to recover $m$?

Last question: let us assume that the sequence we were given was not generated by such a generator; what happens when we attempt to recover $m$ using the above procedure?


decrypt a saml 2.0 response having aes 128 and rsa I need to decrypt a saml 2.0 response. But, the response object has reference to aes 128 and rsa algorithms, and I am having hard time in finding a way to decrypt.

Below is the structure of the response (replacing the sensitive data with some random values)

<samlp:Response xmlns:samlp="urn:oasis:names:tc:SAML:2.0:protocol" Destination="" ID="_12345" InResponseTo="" IssueInstant="2015-01-01T10:00:00.000Z" Version="2.0">
<saml:EncryptedAssertion xmlns:saml="urn:oasis:names:tc:SAML:2.0:assertion">
<xenc:EncryptedData xmlns:xenc="http://www.w3.org/2001/04/xmlenc#" Id="12333" Type="http://www.w3.org/2001/04/xmlenc#Element">
    <xenc:EncryptionMethod Algorithm="http://www.w3.org/2001/04/xmlenc#aes128-cbc" xmlns:xenc="http://www.w3.org/2001/04/xmlenc#"/>
    <ds:KeyInfo xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
        <ds:RetrievalMethod Type="http://www.w3.org/2001/04/xmlenc#EncryptedKey" URI="#12567"/>
    </ds:KeyInfo>
    <xenc:CipherData xmlns:xenc="http://www.w3.org/2001/04/xmlenc#">
        <xenc:CipherValue xmlns:xenc="http://www.w3.org/2001/04/xmlenc#">xxxxxxxxxxx</xenc:CipherValue>
    </xenc:CipherData>
</xenc:EncryptedData>
<xenc:EncryptedKey xmlns:xenc="http://www.w3.org/2001/04/xmlenc#" Id="12567">
    <xenc:EncryptionMethod Algorithm="http://www.w3.org/2001/04/xmlenc#rsa-oaep-mgf1p" xmlns:xenc="http://www.w3.org/2001/04/xmlenc#">
        <ds:DigestMethod xmlns:ds="http://www.w3.org/2000/09/xmldsig#" Algorithm="http://www.w3.org/2000/09/xmldsig#sha1"/>
    </xenc:EncryptionMethod>
    <ds:KeyInfo xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
        <ds:KeyValue>
            <ds:RSAKeyValue>
                <ds:Modulus>xxxxxxxxxx</ds:Modulus>
                <ds:Exponent>xxxxxxxx</ds:Exponent>
            </ds:RSAKeyValue>
        </ds:KeyValue>
    </ds:KeyInfo>
    <xenc:CipherData xmlns:xenc="http://www.w3.org/2001/04/xmlenc#">
        <xenc:CipherValue xmlns:xenc="http://www.w3.org/2001/04/xmlenc#">xxxxxxx</xenc:CipherValue>
    </xenc:CipherData>
    <xenc:ReferenceList>
        <xenc:DataReference URI="#12333"/>
    </xenc:ReferenceList>
</xenc:EncryptedKey>
</saml:EncryptedAssertion>
</samlp:Response>

Now, how should I proceed with this response and the private key, I have.

I am able to decrypt the response successfully on a online tool https://www.samltool.com/decrypt.php, but I couldn't get the internals, which I need.

For a definitive answer, you really should see the documentation for the data format you're dealing with, but just quickly looking at the XML response, it would seem that you're dealing with a hybrid encryption scheme.

That is, your encrypted message consists of two parts:

The actual data (in xenc:EncryptedData), encrypted using AES-CBC with a single-use per-message key.
The AES key used to encrypt the data, itself encrypted (in xenc:EncryptedKey) with RSA-OAEP.

The main reason for using this kind of hybrid encryption, instead of directly encrypting the data directly with RSA, is that public-key encryption algorithms like RSA tend to be rather slow, increase the message length considerably, and generally be poorly suited for encrypting long message.  They work just fine for encrypting AES keys (which are just random bitstrings 16 / 32 bytes long), though.  So we use AES to encrypt the message (which is fast and only adds a few bytes to the message length), and then encrypt the AES key with RSA so that the intended recipient can decrypt it.


Meaning of Signature hash algorithm field in certificate I'd like to understand what is the meaning of this field, especially considering that when calling a crypto library to sign data the digest method is specified by the caller.
For example, this simple C# code:

RSACryptoServiceProvider rcsp = certs[0].PrivateKey as RSACryptoServiceProvider;
rcsp.SignData(data, "SHA256");

Why would I even specify the algorithm if it's dictated by the certificate? And what is the meaning of the resulting signature in the above code, if say, the signature hash algorithm in the certificate is sha1 and not sha256?

A typical X.509 certificate is the combination of data (including a public key $Pub_B$), and of a signature $Sig_A$ of that data, to be verified with an unrelated public key $Pub_A$. In order for the verifier to know which hash to use when verifying $Sig_A$, there is use for a field in said data specifying the hash used by $Sig_A$, and that's the purpose of signatureAlgorithm in said data. As RFC 3279 puts it:

  Certificates and CRLs conforming to RFC 3280 may be signed with any public key signature algorithm.  The certificate or CRL indicates the algorithm through an algorithm identifier which appears in the signatureAlgorithm field within the Certificate or CertificateList.

The signatures that will be verified with $Pub_B$ (produced with the corresponding private key by the certificate holder) use a hash (in your case, SHA-256) that may be different from the one used by $Pub_A$.

The signatureAlgorithm field remains useful after the signature $Sig_A$ is verified, since the trust we can have in $Pub_B$, and in anything signed using $Pub_B$, depends on how much we trust that hash.

Note: typical security "proofs" for digital signatures silently assume that a single hash is used in conjunction with a given key, and that the verifier knows which. It would therefore make a lot of sense that a certificate introduces $Pub_B$ only on the condition that it used to verify signatures in conjunction with a specified hash, or/and that by default that hash defaults to what was used in the certificate and is indicated by signatureAlgorithm; and I'm ready to bet that some PKIs using the X.509 certificate format do this.