Is Triple DES still considered safe to use? What it says on the tin. Is it still used in things like TLS?

Well, yes and no.

Triple DES using 3 different keys is still considered secure because there are no known attack which completely break its security to a point where it is feasible nowadays to crack it.

The Triple DES algorithm provides around 112 bits of security against bruteforce attacks (when taking into account the meet-in-the-middle attack).

For reference, the insane computation power used to find the first SHA1 collision is estimated at a bit more than $2^{63}$ operations. So we still have a security margin of $2^{49}$, which is plenty, but still far less than other standards such as AES.

Triple DES with 3 different keys is still recommended by NIST as per their latest recommendation in NIST SP 800-57.

Triple DES is also the de facto fall-back algorithm for PGP: that is the algorithm all OpenPGP compliant software must implement and use if no other commonly supported algorithm is advertised in the public key of the recipient.

However, Triple DES has a really "small" blocksize with only 64 bits, which led to attack such as Sweet32 against TLS session which allows to break the security of the system thanks to "block collision". This attack led to the removal of Triple DES from the DEFAULT cipher list in the 1.1.0 release of OpenSSL. The attack can also be mitigated by rekeying after a given amount of encrypted data.

As a consequence of that, Triple DES was still in the TLS1.2 standard, but has not made it into the TLS1.3 one.

So in the end, Triple DES is still considered secure if you just want to encrypt something with it, but if you are running a protocol based on it, then you should be worrying about its small blocksize leading to the Sweet32 attack.


ANSI X9.31 AES pseudocode or algorithm explanation I want to write a program that will generate random data by using ANSI X9.31 with AES 128 bit, however I could find the standart only with cryptographic notation, and I did not understand it clearly.

I = ede *K(DT)
R = ede *K(I XOR V)
V = ede*K(R Xor I)

Could you explain me how the algorithms works or suggest me any document to understand it, I tried to understand from the notation but I could not. Thank you in advanced.

Lets go through the steps in detail:

I = ede*K(DT)

K is a long term secret key; that's a random value which is the key of X9.31; it's selected somehow (X9.31 doesn't specify how), and the security of the random numbers depends on it.  Because you are using AES, this would be a random 128 bit value.

When it says 'ede*K(X)', what X9.31 means is 'take the value X, and send it through the block cipher operation (in the encrypt direction).  X9.31 calls it ede because it was written in terms of 3DES (which is done by doing 3 DES operations, in ede mode); for you, you'd just replace it with a single AES encryption operation.

DT is the current date/time (which is updated for every iteration); for you, this would be a 128 bit value, and the format you select for how to express the current time doesn't matter.

The result is placed into a temporary location (called I)

R = ede*K(I XOR V)

V is the X9.31 current state (which also needs to be kept secret); for you, this is a 128 bit value.

In this step, you take the current state V, exclusive or that with the temp variable I generated in the previous step, send that though AES.

R is the 128 bits of output that X9.31 generates this iteration.

V = ede*K(R Xor I)

Here, you take the two values generated in the previous two steps, exclusive or them together, send them through AES; that's the updated X9.31 state you'll use for the next iteration.

And, remember, when you've done this, R contains the 128 random bits that you asked for...


Group membership with unique anonymous claims Is it possible to accomplish the following scheme?

There is a Server (S) and many clients.

Each client enrolls with S, exposing its real identity; S saves the real identity information in its database and executes some keys/identifiers exchange with each client (could be something like DHE or RSA).

Then, someone sends to S a claim such that S would be able to tell that this claim comes from one of the enrolled clients, but not being able to identify from which one (inability similar to factoring large prime numbers). At the same time S should be able to save it and only accept 2 more claims from the remaining clients (i.e. the client that have sent a claim can't send it again).

No client should have such information that, if leaked, could invalidate the entire scheme. In other words, any exposure of the identifier of a single client should only put in danger the ability of this client to make its claim.

A case: 3 clients (X, Y and Z) enroll with S.
X makes a claim to S.
S verifies that it comes from one of the clients and saves it, notifying the client that the claim was accepted. S does NOT know that the claim came from X. At this point, S only knows that 2 of the 3 claims remain.
Z makes its claim. S verifies and accepts it.
At this point S knows that only 1 claim remains.
X sends its claim again. S finds that it was already claimed and rejects it.
Y sends it claim. S verifies and accepts it.
At this point, S knows that all the claims were made.

A paper was published in 2015 describing a scheme called Anonize to do just that.

It appears to be constructed around a specially designed Non-Interactive Zero-Knowledge Proof of Knowledge (NIZKPoK) protocol used by clients.

First, a registration is made, whereby a client sends a commitment to a seed of a pseudo-random function. Sent back to it by the Server is the Server's signature on that commitment and the client's id, which becomes that client's master token. Then the client uses the seed to generate a single-use token. Finally, to submit a response the client has to prove by NIZK that it knows some master token, a survey conductor's signature authorizing some client to go through the survey, and that it indeed computed the single-use token by the seed it knows.

It's notable that the scheme actually makes it possible to conduct multiple ad-hoc surveys on a single server, without giving the server's operator an opportunity to track clients across multiple surveys. That is achieved by using a survey id, which is different for every survey, to generate single use tokens. A client can, on the other hand, only generate one single-use token for each survey id, which means it will only be able to submit one answer.

A usable online implementation can be found here and the development reference implementation is hosted over here.


Is the additive discrete Logarithm problem always easy in Fields? While thinking about additive DH key exchanges, I somehow had the idea that additive DH key exchange may always be easy to break, if we are in a field.

So here's (directly) the question:
In any finite field, is the additive discrete logarithm and / or the computational diffie-hellman problem always easy?

Here's some more info on the details:

It can safely be assumed that doing addition and multiplication is fast
The additive discrete logarithm problem in a field $(\mathbb F,+,\cdot)$ is to find the smallest $k\in\mathbb Z^+$ such that such that $Q=k\odot P$ holds for given $Q,P\in\mathbb F$, where $\odot$ denotes repeated addition of an element to itself k-times (as usual).
If solving these problems isn't always easy, I'd also be interested whether there are certain properties of the field that would make it easy.

I will call the field elements "points" (as an analogy with elliptic curves). We can thus add points together and multiply points together. We can also multiply a point with an integer with a double-and-add algorithm (which will be reasonably efficient), and, similarly, raise a point to some integer power with a square-and-multiply algorithm.

Your additive Diffie-Hellman thus looks like this:

There is a conventional base point $G$.
The two parties select random integers $a$ and $b$ respectively, and compute $aG$ and $bG$ (point $G$ multiplied by an integer), that they send to each other.
They then both compute the common secret $a(bG) = b(aG) = abG$.

The attacker's goal is to find that secret.

Now if the field's order is a known integer $q$ then the attacker has it easy:

$$ (aG)(bG)(G^{q-2}) = abG^q = abG $$

Note that while this breaks Diffie-Hellman in that specific context, this does not mean that the attacker can break Discrete Logarithm per se.

If the field order is not known, then things become more interesting. What the equation above basically says is that the attacker, by multiplying the observed points $aG$ and $bG$, gets $abG^2$, and he wants $abG$, so what he needs is to multiply that value by $1/G$. So the problem really is: if the field order is not known, then can the attacker compute the inverse of the base point?

If $\mathbb{F}$ is a field, then its order $q = p^f$ for a prime $p$ and an integer $f$; $p$ is the field characteristic. For any point $X$ in $\mathbb{F}$, we have $pX = 0$. Thus, the additive order of $G$ is necessarily $p$ (the integers $a$ and $b$ are really integers modulo $p$). For the DH problem to be interesting, we must thus assume that $p$ is relatively large (and therefore odd). Correspondingly, $f$ must be rather small, otherwise the field elements will be unwieldy (very large in RAM). For instance, if $p$ is at least 200 bits in length (for "100-bit security" in DH) and field elements fit in 10000 bits when encoded, then $f$ can be no more than 50.

Therefore, if the group additive order ($p$) is known, then the attacker can exhaustively try successive values of $f$ (starting from 1), each time assuming $q = p^f$ and then trying to compute the inverse of $G$ as $1/G = G^{q-2}$.

If $p$ is not known either, then we are in a mythical "generic field" which is like the "generic group" but with two operations, and then I think that DH in the additive group would be fairly safe. The only problem here is that there is no proof that a generic field can exist at all (just like the generic group, because it would imply all sorts of things such as $P \neq NP$), and I have no idea how to build a plausible candidate. For generic groups, elliptic curves are one of our best approximations, and yet we know more about them than just having an addition on them (indeed, we can compute curve orders with Schoof's algorithm).

Summary: to make the additive DH safe, you would need at least your finite field to be such that its order and its characteristic (which is the additive order of your DH group) are totally unknown, and that seems to be a lot to ask for.


How can cryptographic signatures be somehow linked to a physical signature? A few days ago, I was asked to sign an online document over DocuSign as well as on SignEasy, any the signature were accepted just by a physical signature sent over email or on the app. They did not even ask me to generate a private key whose public key I should upload to their website. So, I felt that the process quite fake and superficial; it just satisfies the naive users. But these apps are quite famous all around.

So, I feel that I think that I am missing out something somewhere. Can you please explain how the physical signatures in these apps are linked to the cryptographic digital signatures?

The short answer is that there's no link between your physical signature and any cryptographic signature. Indeed, from the high-level description of how DocuSign works and their security manifesto there's no reason to believe that any cryptography goes into the signature process itself.

Note that “signature” is an overloaded word. In this post, I will refer to three different concepts that can be called “signature”:

Your physical signature — a scrawling on paper.
A cryptographic signature which mathematically authenticates a message as having been validated by the owner of a key. (There are actually two meanings here: the process of generating a signed message from a key and a bare message, and the bytes that encode the authenticity information in the signed message. But this distinction won't matter in important ways here.)
A validation assertion: a statement that a message has been approved by a certain party.

Physical signatures play a dual role.

They're often used as an authentication factor, because they're supposedly hard to reproduce. But as an authentication factor, they're very broken: not only they're not that hard to reproduce in a way that will fool most people, but mostly because in most cases they can easily be copied and grafted onto a different document. With a scanned signature, grafting it onto any document is trivial.
Physical signatures are also used as a validation assertion. Signing a legal document indicates that you agree to abide by it. Historically, this is the reason they've been used on contracts — even people who couldn't read had the contract read to them and then made a cross at the bottom to signify that they accepted it.

Uploading your physical signature to DocuSign's servers doesn't provide any security. Anybody could find some document that you signed and upload your signature. What it does is partly to provide an illusion of security (we need to demonstrate visible security measures, so let's do something visible and say it's for security), and partly to add a bit of friction and ceremony so that you can't later claim “oh, I must have clicked by mistake, I know nothing about this”. Because your signature is personal to you, you can't claim that it was uploaded by mistake — it had to be you or someone with the intent to commit fraud.

With or without your signature, what DocuSign can attest is:

There is someone with access to an account which has your name and other personal information attached to it. Hopefully they verify that this person has (or at least has had) access to the email account attached to the DocuSign account.
That person made a conscious decision to validate a certain document at a certain time.

Still no crypto so far, except for the trivial (in engineering terms) aspect of using TLS to communicate with their servers.

What can cryptography bring to the table? At this point, nothing, really. DocuSign may well generate a cryptographic key that's specific to your account, and produce a version of the document that's cryptographically signed with your key. That would be a validation assertion for the document on your behalf. They don't need cryptography for that, though: they could put up a web page on their server that states “Rahul approved this document”, and it would serve just as well.

Where cryptography adds something is that a cryptographic signature remains valid in any context. A web page that states “Rahul approved this document” is only useful if you access it on DocuSign's website, because anybody could write that on their own website and it wouldn't have any importance. On the other hand, nobody but the holder of the private key can produce a cryptographically signed document, so the authenticity of that document can be verified offline.

It would be sufficient for that purpose for DocuSign to have a single key and use it to sign all documents. The downside of this approach is that if the key was ever leaked or used in an unauthorized way, it would throw suspicion on all of DocuSign's validation assertion. Using separate keys per user allows the keys to be repudiated separately. For example, if your account is breached because someone hijacked your browser, you could arrange to repudiate signatures made with your key after the breach, which would be a lot less disruptive than repudiating signatures made by all DocuSign customers.

If DocuSign does use a cryptographic signature, it isn't part of the security of the validation assertion, and nothing ties it to your physical signature other than the integrity of your account information on DocuSign's servers. This is the same thing that guarantees the relation between you (via your account, and in particular via your account's credentials) and the validation assertions on your behalf.

You'll note that DocuSign's security page includes a lot of hype, assertions about encryption (which does make sense to improve data confidentiality in case backups are stolen), and assertions about physical security (which makes sense as well, since a breach of their servers would compromise the system) and availability, as well as assertions about following religious regulatory processes. Nothing firm about signing.

As long as the signing key is on DocuSign's servers, the advantage of cryptography is to make the validation assertions easier to use, not to make them harder to forge (i.e. no added security). What if the signing key was only held only on your client? That would reduce the trust that you need to put in DocuSign, since they would not be able to generate arbitrary signatures as you. You would still have to worry about the security of your client environment(s). That would also have practical disadvantages because people use multiple client machines, don't back them up, etc. DocuSign's approach requires no technical competence from the user and no setup on the client side. People who are technical enough to manage signing keys are probably using PGP already anyway.


Length of fields in an RSA CRT Key In a 2048 bit RSA key. Are $P, Q$, exponent $P$, exponent $Q$, and the coefficient guaranteed to be half of the length of the modulus (128 bytes)?

No, it is not guaranteed that in a 2048-bit RSA key, the prime factors $p$ and $q$ of the modulus are exactly half of the length of the modulus or 128 octets; much less so for $d_p$, $d_q$, and $q_\text{inv}$ .

In particular, PKCS#1v2.2 allows almost total freedom on size of $p$ and $q$ (and even allows more than two prime factors for the public modulus). $p$ and $q$ being of exactly equal size however follows from requirements mandated by some common standards, in particular FIPS 186-4, which requires $p$ and $q$ to be in the interval $(2^{1023.5},2^{1024})$ for a 2048-bit modulus.  This can be traced to its ancestor on RSA matters, ANSI X9.31 (1998).

While having $p$ and $q$ of exactly half the modulus is definitely common, there are implementations around which generate $p$ and $q$ of different size, and even standards like ETSI TS 102 176-1 with recommendation that clearly allow that, and have been interpreted as favoring it:

  $p$ and $q$ should have roughly the same length, e.g. set a range such as $0,1 < | \log_2p - \log_2q | < 30$;

Even if $p$ and $q$ are exactly 1024-bit, this does not insure that $d_p$, $d_q$, and $q_\text{inv}$ are exactly 1024-bit or 128-octet. They are often slightly smaller: the high order bits of $q_\text{inv}$ behave about as if $q_\text{inv}$ was random in interval $(0,p)$, thus $q_\text{inv}<2^{1016}$ with probability I guess at least $1/256$ (I welcome a proof or refutation of the estimate, or/and a better one).


I will give the hint:

It is a simple Mathematics rule, given $cp, e$, and $n$ we have this relation:

$(k \cdot p)^e \equiv cp \bmod n$, then we can write this modular relation as;

$k^e \cdot p^e = cp + l\cdot n$, for some $l \in \mathbb{Z}$

$p$ divides $n$ that we already know, and from the equality, $p$ also divides the $np$

Rest left to the op.


IPsec : transmission of Initialization Vector I am currently carrying scholar research about IPsec protocol, and I have a question regarding the  IP Encapsulating Security Payload (ESP). Is the initialization vector of operation mode transmitted in clear in the message ESP Payload ? If it is transmitted in clear, why is it not a security issue ?

Yes, the initialization vector is transmitted in the clear as first part of the ESP payload data (see RFC 4303, section 2, and the RFCs that define the use of specific algorithm with ESP, e.g. RFC 3602, section 3 for AES-CBC, or RFC 4106, section 3 for AES-GCM).

The security of the encryption and integrity protection does not depend on the IV being kept secret. Its primary use is that of a nonce to ensure encrypting the same data with the same key does not result in the same ciphertext.

Some algorithms require that the IV is random/unpredictable (e.g. AES-CBC) but in many modern combined mode algorithms (e.g. AES-GCM or ChaCha20/Poly1305) it just must not repeat and can simply be a counter.

Under certain conditions it might not even be necessary to transmit the IV, for instance, because it can be derived from other information, like the sequence number in ESP. Therefore, there is currently an internet draft under discussion that proposes to omit the IV for certain algorithms (e.g. AES-GCM) and instead just use the (extended) sequence number, which is what's generally already used anyway, it's just transmitted twice in each message.


OTP sequence uniqueness Is it possible to use Time-based One Time Password (TOTP) algorithms to generate tokens from multiple channels (where a channel is defined as a "user" using a certain shared key $K_c$ for channel $c$), and in so doing identify the channel itself from the OTP?

My overall objectives are to:

Generate hash outputs that will never "collide" provide the inputs to such hash function never collide.
Identify from the hash output (the OTP) what the "channel" was that created it, and whether it is a valid OTP. This is trivial for a single channel generating OTP's, but you need an "authenticator" for every channel. I want one server side authenticator for multiple channels/users and be able to derive from the OTP itself what the channel/user is.

My current approach:

Suppose two OTP's were generated with the same time sequence constant $i_0$, and shared secret keys $K_1$ and $K_2$ respectively. Let $A$ and $B$ be the OTP's:
$$\begin{align*}
  A &= \text{HMAC-SHA-1}(K_1, i_0) \\
  B &= \text{HMAC-SHA-1}(K_2, i_0) \\
\end{align*}$$
Would it be possible on the server side during validation to establish without the shadow of a doubt (mathematically speaking) that $A$ is "linked" to channel 1 ($K_1$), and $B$ to channel 2? In other words, every OTP generated using $K_1$ will be different to those OTP's generated using $K_2$ regardless of the truncation of the 160-bit output of HMAC. I believe this is the equivalent of enquiring as to uniqueness of the output of a hash function given unique inputs.

If this happens, and the two "sequences" are different, can their difference be quantified in terms of say a Hamming distance?

Yes, it is possible.  You described how in your question.  I'm not sure what your remaining problem is.  You can think of this as two totally different, independent logical "users" -- or as two different OTP sequences -- with both of them assigned to the same person, using a different one for each channel.  If the OTP scheme is secure, then your approach will be secure too.

The difficult part will be the usability aspects: to convince the user to make to use the proper OTP sequence for the channel they are using.

Also, OTPs are not secure against man-in-the-middle attacks, so they are not a complete solution.

Lastly, one tip for how to get better answers here.  Try describing what you are trying to achieve (what your requirements are) and ask for how to achieve it.  You might get answers or approaches that you hadn't anticipated.


RSA private key format for Mega I've been trying to reverse engineer Mega's (mega.co.nz) API calls. And stopped on the step where client needs to decrypt session id with provided RSA key. I can get key data, but I have no idea how to convert this data into actual key.

Here is my Base64 encoded private key:

BACLkf9qj1yTiX+Jrc7nlp8GMbTh9XnksdQgImr1kRazEsWy28hgOOqjPrsUTe0HtG7UKJzltzBd
1cDQI40qWmmCfsRmKiwNJazfCpDgI21LMveudU9O5djvqgGz8YNVVaOhg//IFAppnb6NHlY51qnP
tEJef47K/2rWMFXUZ8DjrQQA7TTQIUYutrF83GidNT2Od1d+v5hrcCLKzjBYbUIIX1ntI3gFmJyu
TnWL/x5ftzlPhADqdjnmHP1R0MmUheE2EngZvh7H8GumpPnuxhbS7zWAMFHRsagrw8rN4pWtnH1Q
9sZ3mmFTuVvqz547cc2d++7Od7s/hUGZvZEKBQgD4McH/i2kzsuiWCLsyJ74PcQTcQnkZeHsV53T
6s4pAUV9yyfz0VYu+84W1SKclSnhAkZNOFDz56oG7BQZqkP4uJoX6Uf3woikjDdGEYMh1nAJj5KR
G+8WhrvUftSCOMJdgfoFpZZGAIZfvrBjRaevvceh10YzNb8l+fd3ucF9v9IPj3/XMMoWNltDm7YC
gA1PZj6aU3hum47PZu2oQnsCtSER004lwHC28rHgJP2QVl22W7A7hd7/Tn/MMYXmhC8sKu6cVVew
rx0T3yBVmpILpQ2MRFHHwucXBQLPfvgxiC/c1Pnr1GqZf6FgpZSSbUhLkkfpchRyQyzhNaA5NhsN
V2+PCCEEAJTTXts5/Emt/84BEzXC5gg7o0kdR0Z3NxnkLTILpY0IxhnRA6wxO4pDRbsqc85DzSnO
obTWb2tOkw/AdpEzcH3HCPNaKjMuCMHyItv69426NqMVSruqHniNxafCNeHGTofYsKky05Wiv+G0
DWOBnGYf2A+sLAgoGFGBZ53QaI90LS0tLS0tLS0=

From what I understand, it consists of four parts(big integers): p, q, d, u.
I know that to get generate private key we need modulus(p*q) and private exponent (d)

So I'm wondering, is there standard private key format for this key, or they just using some internal encoding?

The format is not an official standard, but it is pretty straight forward. There are indeed 4 fields, in order $p$, $q$, $d$ and $u$ (I'm not quite sure what the function of the $u$ is?, it's not the CRT representation that is common in standards).

First decode the base64: it starts with 0x04 0x00 0x8b 0x91 0xff 0x6a 0x8f 0x5c..

Every number is encoded as a big-endian 2 byte number that denotes the number of bits
(So here 0x400 = 1024), so we then know the number of bytes (so here 0x80 bytes) that then follows and this is just a bigendian number ($p$). After these bytes we get the second length field (0x400 again) followed by 0x80 bytes (for $q$), a length 0x7fe = 2046 bits so 0x100 bytes that encode $d$ (it makes sense that this should be roughly twice the number of bits of $p$ and $q$, as it is of order $(p-1)(q-1)$) and the last $u$ is again 0x400 = 1024 bits, and after this number we get 0x2d = '-' characters as padding.

Normally these private keys are ASN.1-encoded (e.g. PEM format), and Microsoft has its own format in Windows, etc. Many such encodings are just a decorated version of the length followed by data of that length format, so this is pretty easy to figure out.

Take a bignum library (I use GMP, normally) and try to convert the bytes to numbers and check primality etc etc. to try to verify this.


Winternitz Signature in standard model I am studying the Winternitz signature and I describe its algorithms in the next

W-OTS Key Generation. Select the parameter $w\geq 2$ that is the bit size of the partitions of the message to be signed. Compute the number of  partitions

$$t_1 = \Big \lceil \dfrac{r}{w} \Big\rceil,$$
and parameter
$$t_2 = \Bigg\lceil \dfrac{\lfloor \log_2 t_1 \rfloor + 1 + w}{w}\Bigg\rceil,$$
The signature key is $X=(x_0, x_1 \cdots, x_{t-1}) \in \{0,1\}^{r,t}$, where the bit-strings $x_i$ with $0 \leq i \leq t-1$  are randomly chosen. The verification key $Y$ is computed by applying   ${\mathcal{H}}$ $2^w-1$ times in each bit-string $x_i$ of the signature key, i.e. $Y=(y_{0},\cdots, y_{t-1})$ with $y_i = {\mathcal{H}}^{2^w-1}(x_i)$.

W-OTS Signature Generation. Compute the digest $d$ of message $M$ to be signed using $g$, i.e., $g(M) = d = (d_0, \cdots, d_{r-1})$. Add zeros to $d$ until it is divisible by $w$. The partition of $d$ into $t_1$ $w$-sized parts is
$$d = b_0|| b_1|| \cdots || b_{t_1-1}.$$
Note that each element $b_i$ can be transformed into base-$10$  representation and identified with integers $\{0,\cdots, 2^w-1\}$.

Calculate the checksum
$$c=\sum_{i=0}^{t_1-1} 2^w - b_i.$$
The maximum number of bits representing $c$ in binary base is $\lfloor \log_2 t_1 \rfloor + w + 1 $. Indeed, note that $c = t_1 2^w - \sum_{i=0}^{t_1-1}b_i \leq t_1 2^w$ and the number of bits required to represent $t_1 2^w$ is $\lfloor \log_2 t_1 2^w \rfloor + 1 = \lfloor \log_2 t_1\rfloor + w + 1.$

Similarly, split the binary representation of $c$ into $t_2$ $w$-sized parts, i.e.,
$$c = c_0|| c_1|| \cdots || c_{t_2-1}.$$
Finally, computing the signature as
$$\sigma_{\text{W-OTS}} = (\sigma_0,\cdots,\sigma_{t-1})=({\mathcal{H}}^{b_0}(x_0),\cdots,{\mathcal{H}}^{b_{t_1-1}}(x_{t_1-1}),{\mathcal{H}}^{c_0}(x_{t_1}),\cdots, {\mathcal{H}}^{c_{t_2-1}}(x_{t-1})).$$

W-OTS Verification. To verify the signature $\sigma_{\text{W-OTS}}$ of the message $M$, compute the values $b_i$ and $c_i$ in the same way as above described, then compute
$$y'=({\mathcal{H}}^{2^w-1-b_0}(\sigma_0),\cdots,{\mathcal{H}}^{{2^w-1-b_{t_1-1}}}(\sigma_{t_1-1}),{\mathcal{H}}^{2^w-1-c_0}(\sigma_{t_1}),\cdots,{\mathcal{H}}^{2^w-1-c_{t_2-1}}(\sigma_{t-1})),$$
 and compare $y'$ with $Y$. The signature is valid only if $y'_i=y_i$,  $\forall i$. \

I need to understand why this present resistence against adaptative chosen message attack. According my knowledge the adaptative chosen message attack works as follow: an attacker can choose a message on which he learns a signature. Afterwards that attacker can choose the message he wants to forge a signature for. This is called the standard model for secure signatures.

My question is why winternitz signature is secure in the standard model?  I make this question because using the fact that

"an attacker can choose a message on which he learns a signature"

an attacker can choose the message 00000..0000 and then He learn $\mathcal{H}(x_i)$ for $i \leq t_1$. With these value he can obtain all next values of the form $\mathcal{H}^v(x_i)$, that is he can forge partially any signature because each $\sigma_i$ his obtained using that form.

If he gets the signature for the message 00000..00000, then the checksum will be $t_1 2^w$.  For any other message, the checksum will be smaller, and hence the there will be at least one digit $i$ within the checksum for which the $c_i$ digit with value $v$ for the signed message will be larger than the corresponding digit for the new message.  The attacker does not know the $\mathcal{H}^{v-1}(x_{i+t_1})$ preimage for that digit, and hence he is unable to forge the signature.

That is the idea behind Winternitz; for any two messages $M_0$ and $M_1$, then either there will be a digit within $M_1$ which is smaller than the corresponding digit within $M_0$, or there will be a digit within the checksum for $M_1$ which is smaller than the corresponding digit within the checksum of $M_0$


Codes of "SAS und Chiffrierdienst" The german site "SAS und Chiffrierdienst der DDR"
http://scz.bplaced.net
has some interesting content under point 11.3 in the category "manuelle Verfahren" I found ciphers named from A to D. But I think none of these are secure besides security trough obscurity or am I wrong?

When looking at it it looked quite similar to mondern cryptographíc algorithms relying on a secret key and do some "magic" on the plain text to get the ciphertext.
So, on first thought I'd say that these codes follow the rule that it solely relies on the secrecy of a key (in the example on the page you linked it's SCHULPFORTA DEGEN) and not the secrecy of the algorithm (which is the contrary of "security by obscurity").
I can't give analysises about the strongness of an algorithm by myself but because David Kahn's "Codebreakers" is mentioned and I have this book sitting in my shelf next to my computer, I can cite from there:

Such an encipherment virtually obliterates ciphertext repetitions. Even if an exact 18-letter plaintext group recurs, it must begin at exactly the same point in the encipherment equation to produce a ciphertext repetition - and there is only one chance in 18 of this happening. More importantly, a polygraphic encipherment of this magnitude is possible only with a Hill transformation. The more than 40 quintillion 18-letter groups, printed 100 to each side of a page with their ciphertext equivalents, would fill a codebook thicker than the distance from the sun to Pluto.
[...]
The cryptology of today is saturated with mathematical operations, mathematical methods, mathematical thinking. In practice, it has become virtually a branch of applied mathematics. Its sophistication, its range, and its power have grown far beyond the imaginings of the most imaginative cryptologist in Yardley's Black Chamber. And in this evolution, Lester Hill was a prime mover.

BTW: By "today" Kahn is speaking about the 60s/70s, the book was publshed 1967.
Edit: As promised I had a look at C1 and C2.
At first glance at C1 I thoght the same but there is a bit more to it than "security by obscurity". C1 uses a key and one of five filling methods. The key not only sets up the substitution table but is also used to specify the order in which to write down the blocks of cipher elements after filling the key-table.
So an attacker who wants to do statistical analysis to break the key needs to guess the used filling method, the length of the key and the order of letters in which they appear in the key. A brute force attack today might not take that long with todays computing power but for the 50s that's another story.
C2 on the other hand doesn't look robust even after second glance. There are only four substution tables (all of which leaves a cipher that is vulnerable to statistic attacks) and a fixed filling method, so by knowing about this algorithm, breaking a cipher shouldn't be hard.
But even C2 might have it's use because in the Cold War (and any other time that is ;-) you sometime want your enemy to "break" a code in order to feed false information. The information in a deciphered message looks more authentic than a plain message you find on a postcard.
Also, it might also be suitable for messages where the value of the information decreases very fast. E.g. if I use C2 as cipher to send a buying order to my broker and it keeps other trading parties from reading that information until the order is fulfilled (and the information can then be found in the order book anyway) this cipher (which can be calculated manually quite fast) might still be suitable.


Attacking AES using Round 1 output I was reading the paper Differential Scan Attack on AES with X-tolerant and X-masked Test Response Compactor and I have a question in the section Differential Scan Attack on AES.

What I understand is that they precomputed the distribution of Hamming distance for the input difference 1. It is observed that the Hamming distance values of 9, 12, 23 and 24 correspond to unique output vectors.

So as an attack you try various input vectors with difference 1 and when the output vectors have a Hamming distance corresponding to one of these values you have hit the jackpot because you know what input vectors (to the S-box) produce these unique output vectors. As an example, they have mentioned the Hamming distance 9 and they say that the only possible inputs for the S-box are either 0xE2 or 0xE3.

What I am unable to figure out is how they were able to calculate the values 0xE2 and 0xE3. The best way I can think of is by trying all possible values. This may work in this case because the output vectors have a unique Hamming distance, but I doubt it would work in other cases (say for output vectors with Hamming distance 5).

I want to know if there is a smarter way to figure out these values?

Thanks to @kelalaka for pointing me in the right direction.

Let's say you're interested in finding all input pairs $(b^{i}_1, b^{i}_2)$ to the S-box for the input difference $k$ which generate some Hamming distance $l$. Here's how you do it :

  Generate all input pairs such that $b^{i}_2 = b^{i}_1 \oplus k$
  Find out the corresponding output pairs $(f^{i}_1, f^{i}_2)$ and the Hamming distance between these pairs $l_j$.
  Collect all the input pairs $(b^{i}_1, b^{i}_2)$ for the Hamming distance $l$


Storing passwords in a publicly available database I have a public database where users need to store configuration files. The file can contain passwords. Everyone can read config files but only the server can read passwords in them.

In the browser, when a user wants to add a password to the the config file:

User hash the password using bcrypt
User encrypts the hashed string with public key A
User adds the encrypted string to the config file and saves it to the database

A third party server will then connect to the database, this server knows the private key for A. This server verifies if some plaintext password match with the encrypted hash.
Other users see the config file, but they can't see what passwords are in it.

Some precision :

I don't care if another user edits the encrypted password, and I don't care who edits the password, so I don't think I need to sign anything.
It's really a public database, like a mysql instance without any security.
I do the hashing on the client in case the private key gets stolen. It will take a long time to reverse the hash for all passwords.

It seems secure to me. Is it? Is there a simpler way?

It's generally not a good idea to store passwords of any kind in a database that's not secure, let alone a database that's intended to be publicly available.

  Is it secure?

If you don't care about tampering and wrong entries in the database then I guess this setup is okay.

Bcrypt already incorporates a salt to prevent rainbow attacks, so all passwords should have a different hash. Since you then encrypt the hash with the public key of an asymmetric encryption algorithm it should actually be secure. To try and brute-force a password in the database you would first have to brute-force the asymmetric encryption, which is infeasible on any time-scale.

  Is there a simpler way?

Yes, implement security-conventions (secure database, etc.), no need to reinvent the wheel.


How safe is it to derive MAC key from a hashed password? Imagine I have a blob that I want to encrypt-then-MAC. Now, what I can realistically ask my users for (out of UX considerations) is just an encryption password. Naturally, I bcrypt original password and use bcrypted value as an encryption key. Using the same key for MAC purposes seems risky to me, so I reckoned I'd hash my already hashed encryption key (with bcrypt or with a less expensive algorithm) and use that as a MAC key.

Is this OK to do or do I need to have some other derivation procedure?

As mikeazo notes, PBKDF2 supports the generation of arbitrary amounts of key data.  It accomplishes this simply by appending a running counter to the salt and rerunning the key derivation process to generate new output blocks, so there's no obvious reason why you couldn't apply the same construction to bcrypt.

The scrypt KDF also supports arbitrary-length output, which is not surprising, since it's based on PBKDF2.

Ps. In PBKDF2, each block of the output is computed independently using the full iterated key derivation process.  This has the disadvantage that the CPU time needed to run the KDF scales linearly with the desired output length, whereas the work of an attacker who only needs one of the output blocks doesn't.  (This is not a far-fetched scenario: for example, if you generate two output blocks and use one of them as the encryption key and the other as the MAC key, an attacker only needs to generate the latter to check whether he guessed the right password.)

Given this, it would seem better to generate only one output block with PBKDF2 (using a correspondingly larger iteration count) and then use a lighter-weight KDF (or even PBKDF2 itself with a low iteration count) to expand the output to the desired length.  Of course, given that this seems like such an obvious thing to do, one might wonder why PBKDF2 wasn't specified that way to begin with.

Interestingly, this also seems to be more or less how scrypt uses PBKDF2.  Specifically, scrypt invokes PBKDF2 twice, both times with an iteration count of 1: first to expand the passphrase into input for the memory-hard mixing function SMix (on which the hardness of scrypt is actually based), and again to hash the output of SMix into the desired amount of key material.


IV Security Clarification After doing lots of reading on SO and other websites relating to AES cryptography, I am trying to understand the security issues surrounding IV's.

There seems to be a lot of confusion and contradiction surrounding this subject.

Many say it is safe to publish the IV as it is not a secret whilst others say it should be kept safe AND a secret, as this translates to the starting point for the AES encryption engine using CBC. Without the IV, the decryption of the cipher block will corrupt, so by default shouldn't this add security by keeping it a secret?

Could somebody please help me understand, finally, what the official standpoint is regarding the IV so I don't release my cryptography software with a huge gaping hole in it.

The way I see it, if the IV is the initialiser for the AES engine, surely if a cryptanalyst knows this it will give him a starting point for attacking the cipher text? On the same note, if the IV was kept a secret the cipher text would be even harder to attack as every encryption of a given string (or file) using an IV would produce a completely different cipher block and no 'starting point' is known.

Keeping the (initial) IV secret only adds security for the first block of your cipher text. The IV for the second block is by definition the first cipher text block, and so on. So if we would have the key but not the initial IV, we could decrypt the whole ciphertext except the first block. So it doesn't add much security, but it does add "management", as you do need to communicate the initial IV to any party you wish to be able to decrypt.

So normally the IV is just prepended to the cipher text and not kept a secret. This is no problem as long as the IV is random and non-predictable for every message or file we encrypt with that key. CBC in this mode has a standard security proof (for privacy only, of course, as we do not have integrity checking).

Another option is to have an implicit IV that depends on key material (that the recipient should know anyway to be able to decrypt), using hashes or other pseudorandom functions. This is done in some standards. This saves the 16 (if that is the block size) bytes expansion for explicitly prepending it. It adds some complexity, and expansion is not really an issue these days for things like file encryption. I would avoid it.


Finding hash almost-collisions A few months ago, XKCD posted a challenge to find a plaintext which hashed (using Skein 1024 1024) to a specified value. Inputs were scored based on the hamming distance between the hash of the specified input and the desired hash.

The top scorer, from Carnegie Mellon, found a plaintext whose hash matched all but 384 bits of the desired hash.

I also tried competing in the contest. I used brute force and just hash many sequential values and submitted the best one I could find. I didn't come close at all. As I expected, it was easy to drop the first few bits and get it down to the mid 400s, but each improvement was harder than the one before.

Is there a better way than brute force? When I was competing, I figured that the Skein hash function seemed pretty secure and that I wouldn't be able to find any weakness to speed up the process. Now I'm doubting that the winner could score so well with brute force, even with immense amounts of computing power.

Since the output of the configuration of Skein is 1024 bits, we would expect to get 512 bits correct just by random hashing. So the question is, what is the probability of getting 640 bits correct? From that we can figure out how long it would take for that to occur.

There are ${1024 \choose 640}\approx 4.16\cdot 10^{292}\approx 2^{972}$ ways this can happen out of $2^{1024}$ different outputs. If we assume the probability of each output is $1/2^{1024}$, then the probability of getting one of those outputs with 640 correct bits is approximately $2^{972}/2^{1024}=1/2^{52}$. So, perform $2^{51}$ hash function calls and you have a $.5$ probability of getting one of those outputs. That sort of work factor should be do able with lots of hardware (supercomputer, GPUs, etc) in 24 hours. As Paulo said, the problem is embarrassingly parallelizable.


A timestamping authority (digital notary) Does there currently exist a free online service that accepts a file, hashes it, takes an authoritatively chosen timestamp (from one or more time services), signs these and sends this signed message back? E.g. a digital notary, but only with regards to the timestamp and not the validity of the content as legal notaries might be obligated to guarantee.

Such a service might have an extremely simple API: Simply wget http://service/<checksum> and receive a signed message containing one or more timestamps and the checksum. The emphasis would be on the type of authority who might make such a service.

Edit: Although the original question did not emphasise the following, the Bitcoin-based timestamping services provided below do not rely on one authority, but rather the entire Bitcoin network. They can be seen as tamper-proof and verifiable without the help of the service that helped you sign it!

If you search on "timestamp", "timestamping", and "notary" on Crypto.SE and Security.SE, you'll find lots of references.  I've collected a number of timestamping services that were mentioned in one of those places; this should provide a number of companies and online services you can check out:

http://www.proofofexistence.com/
https://www.btproof.com/
https://www.universign.eu/en/
http://www.guardtime.com/
http://securo.it/
http://www.cryptostamp.net/
http://www.itconsult.co.uk/stamper.htm
https://www.globalsign.com/timestamp-service/

I cannot vouch for or endorse any of those.

See, for instance, the following questions on this site, and the following other resources:

https://security.stackexchange.com/q/19184/971
https://security.stackexchange.com/q/43995/971
How are timestamps verified?
Signature and Timestamp for Long Term Document Archival Question
Timestamping services authorities, utilizing Linked, hybrid and other than PKI schemes
https://security.stackexchange.com/q/24458/971
https://en.wikipedia.org/wiki/Trusted_timestamping
http://tools.ietf.org/html/rfc3161
https://security.stackexchange.com/q/32493/971
https://security.stackexchange.com/q/47289/971

Happy reading!


Where to obtain a common/weak password list (black list)? The NIST 800-63B publication specifies recommendations regarding memorized secrets (passwords)
https://pages.nist.gov/800-63-3/sp800-63b.html#memsecretver
specifically section "5.1.1 Memorized Secrets"

When processing requests to establish and change memorized secrets, verifiers SHALL compare the prospective secrets against a list that contains values known to be commonly-used, expected, or compromised.

and Appendix A. A.3 Complexity

it is recommended that passwords chosen by users be compared against a “black list” of unacceptable passwords.

Where should the Verifier get such list?
How and how often this black list is supposed to be updated?
If NIST doesn't provide such list, how can I be sure that the list downloaded from some source is nearly acceptable for use?

Well, you could just google it!  This is the top 100,000 broken passwords from the UK's National Cyber Security Centre (GCHQ).  It's probably trustworthy. Top password is 123456. Probably shouldn't use it then. That article is dated 21 April 2019, which is a while ago. Not sure when updates will happen, but again, more googling...
Your note could also refer to an internal list of compromises only known to a particular organisation. Companies try not to publicise such breaches if possible/legal, but clearly they happen so lists could be compiled.


Mitigating the damage when a signing key is stolen Let's say we have a server whose job is to sign documents using a private key. Let's say that there's a bug in the software and the private key gets stolen. I'm interested in mechanisms to mitigate the damage.

One thing you could do is have the server throw out keys as it goes.  Instead of giving a the server a single private key, you'd give it a sequence of private keys. The node signs doc1 with key1, doc2 with key2, etc. When it's done with a key, it throws out the key completely, so that key can't be stolen any more. There must be some mechanism to procedurally generate the sequence of keys, but I don't know the name of the technique to google it. Anybody know what this is called?

Are there any other cool techniques that can be used to protect the private keys?

I found a paper called "A Forward-Secure Digital Signature Scheme." I think I'm on the right track.

I'm still interested in the second part of my question, though: is there anything I can do besides forward secure digital signatures?

A standard solution is to have keys with limited validity keys and a separate, possibly offline long term key signing key. The signing server holds only one key, so even a total comprise of the server won't reveal future keys.
Before the active key expires, the server gets a new key signed by the master key and starts using it.
We also use certificate revocation lists. If we suspect a key has been compromised before the end of it's validity we not only switch to a new key we publish a revocation of the previous key publicly signed by the leaked key or master key. Verifiers can check this list before trusting a signature.

This setup works rather well with https protecting communications. But is less suitable for signing docyments where you will want document signatures to remain valid for a long time. Even after a key expires or is revoked.
Blockchain works welll here and relies on hash functions rather than assymetric ciphers. If you publish a chain of hashes of everything signed with it's time stamp it is difficult to back date a signature as it isn't in the chain. Making many copies of this around the internet or even use an existing blockchain is one way to make such records tamper resistant. You could simply sign the tip of the chain with current active key. And allow an interactive verifier to get high confidence on old documents because you essentially keep resigning everything you signed in the past.


Would it be better to use HKDF or SCrypt for deriving a child key? Okay so I'm trying to derive a child public key from an EC public key. I've come up with a couple ideas and now I'd like to know which is more secure.

Mp: The master key pair, this includes a private key (denoted Mpri) and an extended public key (denoted Mpub, more on this in a second).

i: Some kind of input from the user, it may or may not be random / high entropy.

P: RIPEMD160 hash of i.

Now there's a CKD (child key derivation) function that will return 512 bits (either from HMAC-SHA512 or SCrypt). The first 256 bits will be the key while the latter 256 bits will be the chain code (denoted as C). The total 512 bits is the extended public key.

I could use HMAC-SHA512(Key = C, Data = P), or I could use SCrypt(Password = P, Salt = C, N = 2^16, p = 1, dLen = 512), or SCrypt(Password = P || c, Salt = null, N = 2^16, p = 1, dLen = 512) to derive the new key from the previous.

There might be multiple child keys for one parent (think multiple leaves per branch) so the value of C might not change while the value of i (and P) does.

Which is the most secure? Would providing other values of N and p make SCrypt a better choice than HMAC-SHA512; if so, what are those values and which SCrypt option is the better of the two? Does the possibility of SCrypt having a repeated salt / no salt make HMAC-SHA512 a better choice?

SCrypt is a Password Based Key Derivation Function or PBKDF. In general you don't need such a function if your input is already a key. In that case you need a Key Based Key Derivation Function - a KBKDF.

Currently the best KBKDF is probably HKDF. This can take a key (e.g. the public key), info (e.g. $i$ or the hash over $i$) and possibly a salt. As it is based on HMAC, there is little need to perform any hashing in advance (so using a specific encoding of $i$ would suffice).

For key material where the bits are fully random you may also just use HKDF-Expand (the first part of HKDF, HKDF-Extract just compresses the random bits in the key material in case they are not well distributed).


Set membership check between untrusted parties There are two parties who don't trust each other mutually, say A and B. A has a large set of strings. B has a string and needs to check if this is contained in A's set or not. B does not want to reveal the string to A and neither does A want to reveal all the strings in the set to B. But still, B should know the answer to her membership question from A.

Is there any existing encryption scheme that helps me do this. Please direct me in the right direction.

There is a simple and elegant solution with the additive variant of the ElGamal encryption scheme. I'll first describe the most naive version, and then discuss a bit some improvements.

First, A (who holds a database of size $N$ that is assumed to be over some group $\mathbb{Z}_p$) computes a degree $N$ polynomial whose $N$ roots are the elements of its database, in normal form. Think now of the $N+1$ coefficients $(a_0, \cdots, a_N)$ (in $\mathbb{Z}_p$) of this polynomial as the database stored by A.

B has an input $x \in \mathbb{Z}_p$. He sets up an ElGamal encryption scheme with message space $\mathbb{Z}_p$ (the message is encrypted in the exponent: $E(m;r) = (g^r, h^rg^m)$ where $(g,h)$ is the public key, and the secret key is $s$ such that $g^s = h$).

B computes encryptions $(c_1, \cdots, c_N)$ of $(x, x^2 \bmod p, \cdots, x^{N} \bmod p)$ and send them all to A. A can compute homomorphically from $(c_1, \cdots, c_N)$ an encryption of $a_0 + \sum_{i=1}^N a_i x^i \bmod p$. The latter is either $0$ (if x is in A's database) or some other value. A picks a random element $r$ from $\mathbb{Z}_p$ and homomorphically multiply this encryption by $r$. He sends back an encryption of $r(a_0 + \sum_{i=1}^N a_i x^i) \bmod p$ to B. The latter checks whether this encrypts $0$ or not (no need for efficient decryption, so the use of the additive ElGamal is not a problem here). If it's 0, his element is in A's database, otherwise it is'nt.

The problem of this method is that it requires sending $N$ ciphertext, which can be large. A slightly more involved solution is to let B send instead encryptions of $(x^1, \cdots, x^{\sqrt{N}})$ and of $(x^{\sqrt{N}}, x^{2\sqrt{N}}, \cdots, x^{N})$, a total of $2\sqrt{N}$ ciphertexts. The server now computes the coefficients of the degree $N$ polynomial whose roots are the elements of his database, written in the following form:
$P(X) = \sum_{i = 1}^{\sqrt{N}} F_i(X)\cdot X^{i{\sqrt{N}}}$, where each $F_i(X)$ is a degree-${\sqrt{N}}$ polynomial with coefficients $(a_{ij})_j$. From the ciphertexts sent by B, A can homomorphically compute encryptions of $F_i(x)$ for each $i$. Then, he generates ${\sqrt{N}}$ random masks $r_i$, and returns encryptions of $F_i(x) + r_i$ together with an encryption of $\sum_i r_i X^{i{\sqrt{N}}}$, homomorphically computed from the ciphertexts he revealed from Bob.

From the $F_i(x) + r_i$ and $\sum_i r_i X^{i{\sqrt{N}}}$, Bob can recover $P(x)$, and nothing more (this can be formally proven). The total communication was reduced to $3\sqrt{N}+1$ ciphertexts. However, I think one must now have efficient decryption for this to work, hence another scheme (e.g. the Paillier scheme) must be used.

If the encryption scheme allows to perform one multiplication in addition to many sums (there are simple schemes doing that under the LWE assumption), then this can be reduced to $O(N^{1/3})$.

I know that considerably more involved techniques allow to reduce that to as small as $O(\log N)$, but I think they are just theoretical works, not really practically relevant as of today. I do not claim that any of the solutions I discussed is the optimal one it terms of practical efficiency, I do not have a detailed knowledge of a state of the art. They are just simple solutions that come to my mind.


Why can a symmetric encryption algorithm be considered a pseudo-random number generation algorithm? I have a question from my teacher: "Why can a symmetric encryption algorithm be considered a pseudo-random number generation algorithm?

Can anyone explain it to me?

And sorry if my english is not good!

Here are two standard (and equivalent) definitions of confidentiality in symmetric encryption. If Alice sends Bob a message and Eve manages to see it in transit, Eve cannot (without an unreasonable amount of computation):

Learn any fact about the plaintext other than possibly its length (semantic security);
Tell the ciphertext apart from random data of the same length (ciphertext indistinguishability).

The latter criterion indirectly answers to your question. One way to implement a pseudorandom number generator is just to encrypt arbitrary inputs—say, encrypt the all zeroes string and use the ciphertexts as the pseudorandom output.

This also works in the opposite direction—if you have a secure pseudorandom generator, you can build a secure cipher out of it (called a stream cipher) by XORing its output with the messages. So in that sense, encrypting messages confidentially and generating secure pseudorandom numbers are equivalent problems.


AES-GCM Disadvantage What is the disadvantage of AES-GCM mode for authenticated encryption? Why does the CAESAR competition say that it’s one of the goals to find an AE scheme that offers an advantage over AES-GCM? What advantage they are talking about?

AES-GCM has the following problems:

In the case of nonce reuse both integrity and confidentiality properties are violated. If the same nonce is used twice, an adversary can create forged ciphertexts easily.
When short tags are used, it is rather easy to produce message forgeries. For instance, if the tag is 32 bits, then after $2^{16}$ forgery attempts and $2^{16}$ encryptions of chosen plaintexts (also of length $2^{16}$), a forged ciphertext can be produced. Creation of forgeries can be instantaneous when enough forgeries have been found.
GCM security proof has a flaw. It has been repaired recently, but the new security bounds are far worse for nonces not 12 bytes long;
GCM implementations are vulnerable to timing attacks if they do not use special AES instructions. The vulnerability remains even if the AES itself is implemented in constant-time. Constant-time implementations of GCM exist, but they are rather slow.
GCM restricts the message length to 68 GBytes, which might be undesirable in the future. The total amount of data allowed to encrypt on a single key is limited by $2^{64}$ blocks, but this number decreases if long nonces are allowed.
Reasonably fast implementations of GCM require specific lookup tables, which do not fit into fast memory (L1 cache or similar) on some architectures.
GCM is vulnerable against cycling attacks; bad values of the internal $H$ key, which can be pre-calculated for specific AES key values, can negatively impact security.


Using salted hash as password for easy memorization without reuse? I had an idea earlier:
Secure passwords are a) long, and b) unpredictable. A hash is both of these. Would it be safe to reuse a key between sites, and include the site's name as a salt? For example:

SHA256("kFnU7Ra%P1_stackexchange")
SHA256("kFnU7Ra%P1_google")

And so on. As long as nobody discovers your key, it seems better than password reuse.

This is better than password reuse, but still not cryptographically strong, for it is vulnerable to (extensive) brute-force search of the relatively short key (your 11-character kFnU7Ra%P1_, which is optimistically worth 66 bit of entropy) for someone who knows the salt (your stackexchange) and a password. As a theoretical aside, although we know no practical attack if the key was longer, we have no strong argument that there is not.

Critical: each user should have a different salt for each site, thus you really should add the user's name in the salt.

If you want the key to remains short, what you want is a key derivation function purposely slowed-down for use with a short key. That could be scrypt, bcrypt, or PBKDF2. It brings you vastly improved, and parameterizable resistance to that attack.

If the key can be long and high-entropy, you could use HMAC-SHA256, with the salt as the message.

Also, a minor, tractable problem is that hashes, KDFs, and MACs, produce arbitrary bytes, some of which are not acceptable in a password by many sites. You need a post-processing to turn that into something acceptable, but the rules vary from site to site: different minimum and maximum length, different (and occasionally incompatible) caveats on the required or prohibited presence of certain special characters.

Note: the idea, and the variations suggested, are well known.

Update: using a 21-character string with each character chosen at random among a set of $64=2^6$ gives you $126=21\cdot6$ bits of entropy, which is ample even if you use a non-slowed-down KDF, or MAC, rather than scrypt/bcrypt/PBKDF2.

It is an entirely different thing if you are using a 21-character string that Joe User can choose. A significant fraction of Joes will choose terrible keys, and be unsafe. A compromise is something like diceware, that Joes can not choose (or can only choose among a few hundred random choices), but can be asked to memorize (he will likely write it down or store it in a "secret" clear text file; also, some Joes will forget the key, loose the paper, or/and accidentally destroy the file). In this way, you can hope to pack 48 bits of entropy in 21 characters. I would recommend a longer string that can be memorized over a shorter that can not, see the obligatory XKCD cartoon. Combined with scrypt or even the lesser bcrypt, and settings resulting in 0.2 second of CPU work per use, this is good enough for most uses: if an attacker manages to be $2^5$ times more efficient than the legitimate Joe, the expected work per attack is still $2^{48-5-1}\cdot 0.2$ CPU.second, that is $>130.000$ CPU.year; and sizable RAM (resp. some, little) for each CPU during the whole attack time, if scrypt (resp. bcrypt, PBKDF2) is used; for scrypt, RAM is where a lot of the investment cost of the attacker would be.


Determining the degree of freedom for a chi-squared test on a strict avalanche criterion matrix I have read that the degree of freedom is calculated by subtracting 1 from the number of states a random variable can be in. I am performing a goodness of fit test on a 64*32 strict avalanche criterion matrix where the expected frequency of any a[i,j] is 50000 and the observed frequency can lie between [0,100000].What I am confused about is that how do I calculate the degree of freedom? Since the observed value might range from 0-100000, will my degree of freedom be equal to (100000-1)? Please advise.

you have $n=64\times 32$ random variables so your degrees of freedom should be $n-1=2047.$


Winternitz Parameter in WOTS+ and XMSS What is the parameter for? I read that in XMSS it is a member of the set {4, 16} but what does it exactly mean? I also read that the bigger the w parameter, the shorter the signatures but the keygen, sign and vrfy become slower. How do I pick an optimal w parameter? Is it the height of merkle tree?

This paper answers your question most succinctly:

The size of a Winternitz signature is roughly $mn/w$ bits and signing roughly requires $2^wm/w$
hash operations, where $m$ is the bit length of the hash value to be signed, $n$ is the output length of
the hash function used in the scheme, and $w$ is the Winternitz parameter determining the tradeoff between signature size and signature generation time.

The reference paper here goes into detail on how the parameter $w$ is used in various algorithms.  Per the paper:

The parameter $w$ can be chosen from the set {4, 16}.
A larger value of $w$ results in shorter signatures but slower overall
signing operations; it has little effect on security.  Choices of $w$
are limited to the values 4 and 16 since these values yield optimal
trade-offs and easy implementation.

An example of the parameter being used is in Algorithm 5: WOTS_sign - Generating a signature from a private key and a message.
Section 2.2 of this paper goes into further detail about time-memory tradeoff.
Additionally section 4 goes into further depth with performance comparisons of different parameters.


Proof that MACing a hash of the message is also a secure MAC I found a theorem that says:

Let $MAC = (S,V)$ be a MAC for short messages over $(K,M,T)$.
Let $H: M^{big} → M$.
Define $MAC^{big} = (S^{big},V^{big})$ over $(K,M^{big},T)$ as:
$S^{big}(k,m) = S(k,H(m))$ and $V^{big}(k,m,t) = V(k,H(m),t)$.

Theorem: If $MAC$ is a secure mac and $H$ is a collision-resistant hash function then $MAC^{big}$ is a secure MAC.

But I have not found the proof. How can we prove this fact?

The generic model for a MAC is the following: the attacker is given access to a block box which implements the $S$ function with a key $k$ that the attacker does not know of. The attacker is allowed to make $q$ requests to the box on messages that he can choose arbitrarily. The goal of the attacker is to make a forgery, i.e. produce values $m$ and $t$ such that $V(k,m,t) = \mathbf{true}$ but $m$ is distinct from all the $q$ messages sent as requests. In other words, the attacker obtains $q+1$ valid message+MAC pairs from only $q$ requests.

Now, suppose that a forgery is possible on $S^{big}$. This means that the attacker can send $m_1$, $m_2$,... $m_q$ to the box implementing $S^{big}$, obtain $t_1$, $t_2$,... $t_q$, and somehow compute $m$ and $t$ where $m$ is distinct from all the $m_i$, and $V^{big}(k,m,t) = \mathbf{true}$. Then look at $H(m)$ and compare it to all the $H(m_i)$; exactly one of the two following must hold:

If $H(m) = H(m_i)$ for some $i$, then, by construction, the attacker found a collision on $H$.
If $H(m) \ne H(m_i)$ for all $i$, then the attacker implicitly made $q$ requests to $S$ (for all $H(m_i)$) and then computed $m$, which means that $H(m)$ and $t$ are such that $V(k,H(m),t) = \mathbf{true}$. The attacker then succeeded at a forgery attack on $S$: he computed a pair containing a short message ($H(m)$) and a token $t$ which are accepted by $V$, and yet at no point was that exact $H(m)$ sent to the box implementing $S$.

It follows that if $S$ is strong against forgeries and $H$ is collision-resistant, then $S^{big}$ must also be strong against forgeries.


Are hardware encryption chips safer than their software counterparts for desktop apps? Wouldn't accessing the hardware encryption chip be safer than relying on an encryption library?

My question is prompted as a response to @SqueamishOssifrage replying on the "Properly securing a private key for remote storage" post, item #6 (I don't have enough points to reply to their comment).

Quote:

  it takes a lot of effort to audit your software stack well enough to guarantee it is reliably using the hardware AES support on all
  platforms that may be of interest to you.

If my desktop application is signed, wouldn't it be safer to use the chip?

Clarification based on answer received

yeah I'm basically looking for a secure solution to storing private keys. Your point #2, storing the key in the chip where the key never sees the light of day seems like the obvious solution. Thinking through what to do for potential problems (supporting different chips, a new vulnerability being found, etc.) makes that impractical for a small-time developer. At this point, implementing a software solution where keys perhaps are signed by multiple remote servers seems the way to go (you may compromise one remote server but can you compromise them all?). If there's a better design pattern than that, I would be interested in pursuing that. As it is, I don't trust a software implementation on a single computer to do it.

‘Hardware encryption chips’ could mean a couple different things: it could mean

hardware that simply computes cryptographic operations with keys fed in by software, like Intel's AES-NI CPU instructions; or
hardware that stores keys and computes cryptographic operations in them with defensive measures to prevent anyone from ever extracting the keys, like a YubiKey USB device or an HSM.

What I was addressing in the earlier post was only the first type.

If you can take advantage of your CPU's (say) AES and GHASH hardware, then it is probably faster and less vulnerable to timing side channel attacks than software AES.

But it's a lot of engineering work to audit the entire software stack in all instantiations that might arise to ensure that you really are taking advantage of the hardware—because,

for compatibility, software stacks usually have software fallbacks; and
for performance except in sensible software like BearSSL, software fallbacks are usually faster but leaky by default; and
timing side channels are usually silent meaning you won't ever notice the problem until someone on the other side of the planet steals your money through a leak in your Bitcoin wallet software.

Of course, you can get almost the same performance and essentially the same side channel resistance just by using ChaCha and Poly1305 instead, and then you don't have to do all that engineering and auditing work because the widely available ChaCha and Poly1305 software tends to resist timing side channels already, and you get a better security margin because ChaCha is a better design, and your software will be usable securely on a wider variety of platforms.

So, if you're choosing a cipher for a new protocol, then this argument favors ChaCha or XSalsa20 and Poly1305 over AES-GCM in order to avoid needing hardware for fast security.  But if you're choosing an implementation when your protocol has already chosen AES-GCM, then it's safer to use AES-NI or similar to compute it if you can.

As for hardware devices that store keys, well, it's great if you can do that because then malicious apps on your phone/laptop/exobrain/advertisementIVdrip can't steal the keys.

But it also means someone can't just use your awesome app with a one-click install from the app store; instead they may have to carry around a physical device, or you may have to deal with vagaries of platforms like TPM in laptops and SE in iPhones and so on.

So it's more engineering work and usability hurdles.  Which may be worth the security benefit!  It's up to you as an engineer to make informed decisions about these tradeoffs, using particular information about your intended audience, usage, etc.


Is it possible to calculate the 'skeleton key' for DUAL_EC_DRBG? What would it take? According to Bruce Schneier the constants used in the spec of DUAL_EC_DRBG may be related to a secret set of numbers, that could function as a master key for encryption using on this random number generator:

This is how it works: There are a bunch of constants -- fixed numbers -- in the standard used to define the algorithm's elliptic curve. These constants are listed in Appendix A of the NIST publication, but nowhere is it explained where they came from.
What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random-number generator after collecting just 32 bytes of its output. To put that in real terms, you only need to monitor one TLS internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG.

source
Is it possible to calculate these secret numbers given these constants? What would it take to calculate them?

I've found this attack to be poorly documented, all-in-all. Below is a technical explanation of the matter, or one can skip to the conclusion if uninterested in the details.

Dual_EC_DRBG

First, let me give a short description of Dual_EC_DRBG using the notation of Shumow and Ferguson (see the presentation). As a preliminary, we are working with some prime-order elliptic curve, and we have two points $P$ and $Q$ on that curve. Since the group is prime-order, both $P$ and $Q$ are generators.

Since we'll be working with integers ultimately, we need a way to "convert" a point on the curve into an integer. For that purpose, we will define $\varphi(x, y) = x$, i.e., we just use the $x$-coordinate of the point.

In any round $i$, we have a starting state $s_i$. Next, we compute $$r_i = \varphi(s_i P)$$ where $s_i P$ denotes repeated point addition:
$$s_i P = \underbrace{ P + P + \dots + P.}_{s_i \text{ times}}$$
This $r_i$ will be used to (1) generate the output and (2) update the state of the generator.

The output of round $i$ is
$$t_i = \operatorname{LSB}_{\mathrm{bitlen}-16}(\varphi(r_i Q)).$$
The attacker will be working with these values. Here, $\operatorname{LSB}$ means "least significant bits," so we chop off 16 bits before we output.

The state of the next round is defined by $$s_{i+1} = \varphi(r_i P).$$

The Attack

Since $P$ is a generator, there is some integer $e$ such that $P = eQ$. Suppose we know this $e$.

Given any output $t_i$, we know all but sixteen bits of the value $\varphi(r_i Q)$. We can generate all possible combinations of those missing sixteen bits, which leaves us with $2^{16} = 65536$ possible values — one of which is $\varphi(r_i Q)$, the "real" output. Since all $(x,y)$ points on an elliptic curve satisfy the equation $y^2 = x^3 + ax + b$, if we are given some $x$-coordinate, we can solve the quadratic to obtain two possible $y$ values. That is, if we have $2^{16}$ values that might be $\varphi(r_i Q)$, we can use each of those values in the previous equation, and thus obtain $2 \cdot 2^{16} = 2^{17}$ values, one of which is the real $r_i Q$.

What happens if we have $r_i Q$? Since we're assuming we know the $e$ such that $P = eQ$, we can simply multiply $r_i Q$ by $e$ to get:
$$e(r_i Q) = r_i (e Q) = r_i P.$$
Recall that the state of the next round is defined to be
$$s_{i+1} = \varphi(r_i P).$$
So if you know the $e$ such that $P = eQ$, you can predict all future states of the generator, which means you can predict all future outputs of the generator.

How do we determine which of the $2^{17}$ values is $r_i Q$? Simple: we try to predict the next round's output, using the above attack, for multiple rounds. When one value fails to predict the next state, it is obviously not the real $r_i Q$, and so it can be thrown out. This process eliminates all but the real $r_i Q$. Shumow and Ferguson found that approximately 32 bytes of output was sufficient for this attack to succeed.

Conclusion

Your question:

  Is it possible to calculate these secret numbers given these constants? What would it take to calculate them?

It is possible, but not feasible.

The secret integer $e$ (where $P = eQ$) is the necessary value to find. Computing this $e$ from scratch (with arbitrary $P,Q$) requires solving an instance of the discrete logarithm problem in the elliptic curve: $e = \log_Q P$. At present, it is considered computationally infeasible to compute the discrete log in this case.

However, if you are the one picking the point $Q$, you can select a random integer $d$ (to use Shumow and Ferguson's notation again) and set $Q = d P$. Then $e = d^{-1}$, which is quite easy to compute.

Thus: unless you are the one who picked the point $Q$, you have basically no hope of finding $e$. On the other hand, if you did pick $Q$, then you could have very easily picked $Q$ such that you know $e$. This is pretty much the textbook definition of a backdoor, I think.

Note that two problems in tandem cause this attack: first, if we had picked a better way of integer-izing an elliptic curve point (a better $\varphi$), it wouldn't be possible to use $\varphi(r_i Q)$ to find $r_i Q$. Second, since we only chopped off sixteen bits before output, it is easy to brute-force test all missing sixteen bits. If we had chopped off more bits, the attack would maybe have been thwarted.


XOR or add in one time pads? Is there any difference in adding the plain text and key vs using xor instead(apart from the performance improvements)?

There is no security difference; there are a handful of practical ones:

With xor, you can have the same code to do encryption and decryption
With xor, you don't have to pick a 'word size'; a larger CPU can handle 4 or 8 bytes at a time, while a microcontroller can handle 1 byte at a time, without changing the ciphertext
With xor, you don't have to worry about endianness (which you would if you, say, added words modulo $2^{32}$

While these are all minor differences, they all point towards xor being slightly better from a practical standpoint


What key length has to be send to a recipient when using a stream cipher? I was being argued that stream cipher's key that is the length of the message must be sent to the destination for them to be able to decrypt the message.

My point is: don't you only have to send the seed of the PRG let's say the 128 bits key for RC4 128 and then the destination can recreate the full length key from the 128 bits you sent them. Am I correct or wrong?

I think what you have here is a confusion about terminology. Here's standard terminology:

Keystream: The thing that's the length of the message that you XOR with the message. Must remain secret; should really not be sent to the other person (if you do, may as well just use a OTP). This is not the key, and is not referred to as such.
Key: That secret information that both parties must know before they can communicate. Must remain secret; does not, in general, suffice to determine the keystream. This is the only secret information that you generally should share before doing the encryption.
Initial state: I'm not sure if this is actually a formal term, but this refers to the initial state of the CSPRNG that makes up the stream cipher. Always depends on key; may or may not actually include the key (RC4's initial state is constructed using the key, but the key itself isn't part of it -- rather, there's an algorithm that starts with a fixed state and mixes in the key before starting the main CSPRNG). Also often depends on other parameters; RC4 just takes one input, but with Salsa20 you have key, nonce, and a fixed component in it (you also have a stream position component there, but that's because Salsa20 does 512 bits at a time, so the stream position is because you initialize the CSPRNG many times in a message). You generally don't send this; you don't care what the initial state is, that's an internal detail of the algorithm. All you send is the information the algorithm needs to construct it, some of which is secret.

Also, since I used the term:

Nonce: A number used only once; in this case, it's a stream-specific number that is never, ever, ever reused with the same key, and is used to allow multiple messages to be sent with the same key. Also called the IV in some cases. With RC4, it's just part of the "key" the cipher expects, and the secret key is the rest of the "key" the cipher expects; in other stream ciphers, this is explicitly part of the algorithm. However, when using RC4 with a nonce (e.g. in WEP), the key is different from the key fed into the RC4 algorithm itself; it's still just the secret part (i.e. if you have RC4-128, with a 32-bit nonce, you're feeding 128 bits into the RC4 algorithm but your key is just 96 bits). Nonces are not secret.

To communicate, you need to send the key in secret, and whatever nonce material you're using for that message (this can be in the clear). You don't send keystream, and don't send internal state.


Using RSA public key as private key and vice-versa I am writing an application that involves checking to see if data has been created by me. I do this by encrypting the data with the private key on my server, and then decrypting it using the public key on the client. If the result matches the hashed version of the message then I know it came from me. However, I'm using RSA and so that means I have to flip the keys since I know you can't encrypt with a private key.

Here is how I am generating my keys:

private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=2048,
    backend=default_backend()
)

public_key = private_key.public_key()

pem = private_key.private_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PrivateFormat.PKCS8,
    encryption_algorithm=serialization.NoEncryption()
)

with open('private_key.pem', 'wb') as f:
    f.write(pem)

pem = public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo
)

with open('public_key.pem', 'wb') as f:
    f.write(pem)

However, here private_key is my public key and public_key is my private key. Is there something I need to change? I've heard public keys are generally smaller but I don't understand enough of the settings to tell if they're symmetric or not.

Any advice would be appreciated.

Thanks.

EDIT: They are definitely not symmetric. As suspected, my public key is much shorter. How do I reverse this?

EDIT2: How about signing/verifying instead?

Server:

from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.asymmetric import padding
import base64
import uuid
import hashlib

message_id = uuid.uuid1()
with open("private_key.pem", "rb") as key_file:
    private_key = serialization.load_pem_private_key(
        key_file.read(),
        password=None,
        backend=default_backend()
    )
message = bytes(hashlib.sha3_256((str(message_id) + str(valid)).encode("utf-8")).hexdigest(), "utf-8")
encrypted_data = private_key.sign(
    message,
    padding.PSS(
        mgf=padding.MGF1(hashes.SHA3_256()),
        salt_length=padding.PSS.MAX_LENGTH
        ),
    hashes.SHA3_256()
)
encrypted_data = str(base64.b64encode(encrypted_data), "utf-8")

Client:

from cryptography.hazmat.primitives import serialization, hashes
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.exceptions import InvalidSignature
import hashlib
import base64

encrypted = response["encrypted"]
message_id = response["message_id"]
valid = response["valid"]
with open("public_key.pem", "rb") as key_file:
    public_key = serialization.load_pem_public_key(
        key_file.read(),
        backend=default_backend()
    )
message = bytes(hashlib.sha3_256((str(message_id) + str(valid)).encode("utf-8")).hexdigest(), "utf-8")
encrypted = base64.b64decode(encrypted)
try:
    public_key.verify(
        encrypted,
        message,
        padding.PSS(
            mgf=padding.MGF1(hashes.SHA3_256()),
            salt_length=padding.PSS.MAX_LENGTH
        ),
        hashes.SHA3_256()
    )
    print("Yes")
except InvalidSignature:
    print("No")

I am writing an application that involves checking to see if data has been created by me.

That's known as verifying data that was signed. It is good practice.

  I do this by encrypting the data with the private key on my server, and then decrypting it using the public key on the client.

That's where it gets wrong. The server must sign with the private key, and then the client must verify the signature with the public key. In RSA there are commonalities between sign and decrypt (both include the private-key operation $x\mapsto y=x^d\bmod N$), and between verify and encrypt (both include the public-key operation $y\mapsto x=y^e\bmod N$), but there also are important differences. For this reason, well-designed APIs, and knowledgeable advisers, won't let you encrypt with the private key. Don't even try. Ever. Forget about it.

Since the API includes PSS, which is a signature padding, it most likely includes primitives to sign with RSASSA-PSS. We are not a code review site, thus I won't try to find where. But my reading of hazmat is that primitives in that area are not meant for direct use, I would look elsewhere.

Edit: I do not immediately see an issue with the code as it now stands, except for naming tag and variable encrypted, which I guess are for a signature. But then I do not know this API, and we are not a code review site.


Why would Diffie-Hellman Group 21 be 521 bits rather than 512? Diffie-Hellman groups tend to increment in key sizes as you'd expect up until group 21. Any idea why the key size is 521 rather than 512? I haven't been able to find an answer at all.

"Group 21" was originally used by IKE to refer to a specific elliptic curve group, which happens to use $2^{521}-1$ as the prime modulus.

Your question is "why did they use $2^{521}-1$ is their prime, rather than a prime closer to $2^{512}$?

Well, it turns out that using $2^{521}-1$ is more efficient than a slightly smaller prime.  Most of the time implementing elliptic curve operations turns out to be performing modular multiplications, that is, given $a$ and $b$, compute $a \times b \bmod p$.  There are some tricks we can use for $p = 2^{521} - 1$ that aren't available for $p \approx 2^{512}$ (specifically because of the special form of $p^{521}-1$ as a Mersenne prime); and so they just took advantage of it.

There are no similar Mersenne prime circa $2^{256}$ or $2^{384}$, and so a similar trick was not available for the smaller Elliptic Curve groups.


Some Questions about salts I am an amateur teaching myself, so please don't expect too much professional knowledge. I have some things that are not clear to me about salts.

For example I wondered if a "too strong" salt could weaken a crypto hash.

If you got an hash algo and you take a password of only one digit and then you fill the rest of the string with a salt til the maximum length of the hash is reached; example: the hash has 128 bit, the pass has 4bit (one ascii char) and the salt has 124 bit and salt and pass are merged together; Would the extreamly strong salt weaken the hash? If the hash got iterated (rehashed)  with the same salt lets say 100-200 times how much of the final result would be "corrupted" by the salt?
Why does a salt need to be long in file encryption?

This question is not related to Databases with thousands of hashed passes for obvious reasons. I saw people suggestiong a min. slat of 128 bits (32 digits!)

Let's say you have a 20 GB veracrypt container ore some stuff like that (does not matter as long as it is only one file). And you want to protect from rainbow tables and precomputation attacks, then why not use a 1 charakter long salt? I mean nobody will generate a RT for a single hash so 1 digit salt = problem solved right? (as long as there are not multiple files).
Why does a salt need to be true random?

Would it not be enough if the salt is pseudo random? It is not even a secret value, so does it have to be random? If it was pseudo random like lets say time in milliseconds then why is that not safe enough? even if the attacker would know the pttern of how the salts where generated, he would not have any advantage right? Like abcd1, abcd2, abcd3, abcd4. Why would that knowledge be an advantage?

a salt cannot "weaken" a password in any way
long salts make pre-computation of rainbow tables completely infeasible, across all machines using that application worldwide. Basically, by choosing a random 16-byte salt you're basically ensuring that your password hash is unique worldwide no matter the password
Pseudo-random values are preferred to ensure global (or at least system-wide) uniqueness of the hash (as described in #2 above). These bytes should come from a CSPRNG ("true randomness" isn't required). Using predictable salts such as time stamps can allow an attacker to create rainbow tables for subsets of the passwords in use.

Finally, traditional salted hash constructions (such as SHA256(salt||password)) are insufficient for modern password storage. You should use a memory-hard, purpose-built password hashing function like Argon2 or scrypt. These also take salts as inputs, so the same logic applies as above.


Is it possible to combine two hash functions in such a way that cracking the constructed hash would require cracking the constituent hashes? Suppose A is some arbitrary hash function, for example BCrypt or MD5. And B be some other arbitrary hash function, maybe SHA256 or SCrypt.
Let passwordHashedWithA = A(password) and  passwordHashedWithB = B(password).
If an attacker is given just passwordHashedWithA and finds a pA such that:
passwordHashedWithA == A(pA)
Then the attacker has performed a successful preimage attack on A.
I want to know if it is theoretically possible to construct a hash function C out of two arbitrary hash functions A and B, such that for any A and B, performing a successful preimage attack on C would require performing a preimage attack on both A and B. The question can be extended to build C from N arbitrary hash functions.
I strongly suspect that this is theoretically impossible; it seems like a free lunch. But I cannot begin to think how to prove it.
If such a thing does exist then it would be incredibly useful: we could combine old, proven hashes like BCrypt with slightly newer and fancier hashes like SCrypt, such that we have the best of both worlds. Like I said - sounds too much like a free lunch.
I am asking this from a theoretical perspective, I'm aware that BCrypt or SCrypt are probably good enough for most production systems.
I'm looking for a proof that this is impossible, or a construction of C that provides these properties.
Examples of C that don't work
Suppose we try C(password) = A(password) + B(password) where + is just concatenation of the hashes.
The result of this is obviously a weaker hash: we can preimage C by finding the original password by cracking  A or B.
If we try C(password) = A(B(password)), this initially looks stronger but you really can't say much about C without looking at the specifics of A and B. For example if A was a completely useless hash that always returned a constant string, the strengths in B would be irrelevant, and any string would be a preimage of C.

Suppose we try C(password) = A(password) + B(password) where + is just concatenation of the hashes.
The result of this is obviously a weaker hash: we can preimage C by finding the original password by cracking  A or B.

This is incorrect with the standard notion of preimage resistance.
Because there are many more possible inputs to a hash function than outputs, there are necessarily collisions. Even if $A$ allows you to find a preimage, that is not necessarily a preimage for $B$. For random inputs and unrelated hashes, it very likely is not.
In practical applications this is quite a bit more messy. For example, if you take $A$ to be the truncate function (to e.g. 256 bits, zero-padded), it lets you find a preimage for the concatenated hash if the input is short enough. For the vast majority of possible inputs it does not directly give you a preimage, but that is cold comfort if hashing e.g. typical passwords.

If you want a provably robust combiner, you could look into the thesis linked from an answer to the previous question: Anja Lehmann: "On the security of hash function combiners" (pdf). It offers good combiners that are unfortunately rather complex.
For a simpler combiner, you could use XOR like TLS does. You do not get a nice proof from only the preimage resistance of the hash, but it is provably PRF if either of the two password hashes is PRF (and they are independent). That is a practical choice that is probably good enough if you take care to use different hashes.


Question about the Playfair cipher The task:

The Playfair cipher with $I = J, X$  added into two same letters and
the key keep distance.

The plaintext:

CORONAVIRUS SPREADS FAST

The whitespaces in plaintext and key are to be discarded.

not sure what they mean by I = J, X
The table

I am not quite sure what they are asking for. I know that you usally remove letter J and replace it by I,   But now it says * I = J,X" what does he mean by that?
This is what I've written as "coronavirus spreads fast"
CO RO NA VI RU SX SP RE AD SF AS TX

It means any instances of double letters in encryption are split up by injecting a letter x (as well as the usual I = J).
In other words read the instructions as

I=J
X added into two same letters
Key KEEP DISTANCE


Could we break MD5 entirely in the future? Even of today MD5 is (sadly) still heavily used in some applications. Even big tools like ApacheMD5. But even today there are more then enough MD5 hashes which are still not cracked.
According to Wikipedia, the strongest attack at time of writing this seems to be a preimage attack against MD5 which was published in April 2009, was published that breaks MD5's preimage resistance. This attack is only theoretical, with a computational complexity of $2^{123.4}$ for full preimage.
But in the future with Quantum computers, could we get all known plaintext for MD5 (or make them collide)? And would anyone who has a quantum computer even take the effort to do so ?

If you follow the reference for the alleged preimage attack on MD5, you will see that although the time cost is $2^{123.4}$ steps, the memory cost is $2^{45} \times 11$ words of memory, which has a far higher area*time cost than a smart attacker would use—a smart attacker would fit 32 CPU cores or MD5 circuits in parallel into much less die area and get an answer faster, in $2^{123}$ time.  So that attack gives no reason to treat MD5's preimage resistance as below its advertised level.

But the advertised level—the best preimage resistance that can be provided by a 128-bit hash—is not very high.  A smart attacker will do even better: a smart attacker will attack many targets at once with a parallel brute force machine using rainbow tables, and find one preimage among $n$ target hashes on a machine parallelized $n^2$ ways with probability $p$ at the area*time cost of about $2^{128}p/n$ evaluations of MD5—much cheaper than the cost of about $2^{128}p$ for an attack on a single target, and in the time for $2^{128}p/n^3$ sequential evaluations of the MD5.  This is not an attack on MD5 in particular; this is a generic attack on any 128-bit hash.  Could this happen in practice?  It's within the realm of human feasibility, even for a preimage that is not an easily guessable passphrase.

With an array of $k$ quantum computers large enough to run Grover's algorithm, you could find a single MD5 preimage with probability $p$ in about $2^{64}\sqrt{p/k}$ time.  Whether this will ever be cheaper than the standard generic classical parallel brute force attack depends on how cheaply quantum computers capable of running Grover can be built and powered—at the moment, they do not exist at all.  (Studying the quantum multi-target story is left as an exercise for the reader.)

That doesn't necessarily mean you would find the original input strings—unless you know something about the distribution of the original input strings and restrict your search to that, you might find gibberish that happens to have the same hash as the original input strings.  (In fact, merely knowing an MD5 hash—a 128-bit string—doesn't mean there ever was an ‘original input string’.  Here's an example: 914c24484128dfe05c3060632ee16e3f.  Maybe you can find a preimage for that, but I just pulled it out of /dev/urandom.)  So it would mostly be useful mainly for either (a) filling in very short unknown high-entropy details of large documents the rest of which you know, or (b) inventing substitute strings that will have the same hash and that are useful only in active attacks on systems still using MD5 as a proxy for identity.

As for computing collisions—finding pairs of messages $m_0 \ne m_1$ with $\operatorname{MD5}(m_0) = \operatorname{MD5}(m_1)$, with no control over what the common hash value might come out to be—you don't need a quantum computer to do that.  It's practically a parlor trick at this point, costing under a million MD5 computations to make fresh ones, to say nothing of extending existing collisions into longer ones which costs no computation at all.


Is this transposition cipher information-theoretically secure for 1 message? Given:

$m = \{0,1\}^{n}$; a plaintext message of length $n$ encoded in binary

$k = randomshuffle([0, 1, ..., 2n-1])$; A secret key consisting out of unique numbers between 0 and $2n-1$ in a true random order. The key is only used once and preshared between sender and receiver.
We create $t = m||NOT(m)$; a temporary variable with the original message plus the inverse of the original message. (The intention here is to make the number of 1's and 0's equal)
We transpose $t$ using key $k$ as indices to create the ciphertext $c$.

For example, the key 5-4-3-2-1-0 would reverse the order of the bits of $t$.

Full example:

Given: m = 010 and k = 5-4-1-3-0-2
We append the inverse of 010 (which is 101): t = 010101
We tranpose t using k. The resulting ciphertext: c = 101100

To decrypt the ciphertext you would simply reverse the transposition using your key and drop the second half of the message.

Is this scheme unbreakable?

For a scheme to be information-theoretically secure, you need that $$\Pr[M=m\mid C=c]=\Pr[M=m\mid C=c^\prime]$$ for all $c,c^\prime$ (that is, any ciphertext has the same probability $M=m$, so the ciphertext doesn't change the probability $M=m$).

Let's suppose we have a $c$ and a $c^\prime$. Both of them have the same number of ones and zeroes, because both are half ones and half zeroes. That means there's a permutation that takes $c$ to $c^\prime$ (in fact, there are a lot of them, but pick one); call it $\sigma$. We want to show that the number of permutations taking $c$ to some $t_0$ is the same as the number taking $c^\prime$ to $t_0$.

We can convert a permutation $\pi$ taking $c$ to $t_0$ into a permutation $\pi\sigma^{-1}$ taking $c^\prime$ to $t_0$: $\pi\sigma^{-1}(c^\prime)=\pi(c)=t_0$. Likewise, if $\pi^\prime$ takes $c^\prime$ to $t_0$, then $\pi^\prime\sigma$ takes $c$ to $t_0$. Also, $\pi\sigma\sigma^{-1}=\pi\sigma^{-1}\sigma=\pi$, so the functions are inverses. So, there are exactly the same number of permutations taking $c$ to $t_0$ as taking $c^\prime$ to $t_0$, so $$\Pr[T=t_0\mid C=c]=\Pr[T=t_0\mid C=c^\prime]$$ for all $c,c^\prime,t_0$.

Lastly, we know that $\Pr[M=m]$ is the sum of the probability that $T=t$ for all $t$ which have $m$ as their first half. Since all these probabilities are independent of the ciphertext, so is $\Pr[M=m]$. This applies whether or not you consider that $\Pr[T=t]$ is zero if $t$'s first half and second half aren't bitwise inverses; no matter what, it doesn't depend on the ciphertext, and neither does $\Pr[M=m]$. So, this scheme is information-theoretically secure.