What is the best hash for HMAC? Long question but I am starting to lose sight of all the HASH algo's there are.

I know SHAKE128 and 256 are part of the SHA-3 standard but is the SHA3 standard officially released yet? i can only find a draft of the publication, does this mean it's not official and therefor not proven to be secure?

I have not found a proper SHAKE128 or 256 c implementation which is why i'm wondering if they should be used yet, because if they were good I'd think there'd be a lot of example code for them.

I know SHA-1 has a theoretical attack which comes close to being practical and obviously MD5 is broken which is why i would like to keep away from those.

Then SHA-2 remains but SHA-2 contains sha 224, 256, 386 and 512. I've tested these (and whirlpool and Tiger) on my test device and this was the speed:

HMAC        bytes   speed μs
Sha1        64      746
            128     857
Sha224      64      918
            128     1066
Sha256      64      918
            128     1066
Sha384      64      2395
            128     2840
Sha512      64      2400
            128     2840
Sha512_224  64      2390
            128     2835
Sha512_356  64      2390
            128     2835
MD5         64      308
            128     345
Whirlpool   64      5630
            128     6420
Tiger       64      832
            128     952

So MD5 is fastest followed by SHA-1 but those i would like to evade. Now Tiger is the 3th fastest followed by SHA 224 and 256.

I do know that having an insecure HASH does not necessarily mean your HMAC is insecure but still, I always lock my car even though no one has the key.

So the question: what is the best hash to use, obviously it needs to be relatively fast and by my standards sha-512 isn't fast (enough).

I know SHAKE128 and 256 are part of the SHA-3 standard but is the SHA3 standard officially released yet? i can only find a draft of the publication, does this mean it's not official and therefor not proven to be secure?

No, SHA-3 has not been formally approved.  On the other hand, what do you mean "not proved to be secure"?  Do you really thing that NIST approves only things that are "proven"?  In practice, we have only a handful of things that are "proven" (OTP, secure sharing); while NIST certainly tries to vet what they place on the approved list, they have no proof.

In any case, from your questions, it appears that you are interested in speed.  Now, SHA-3 is actually slower in software than SHA-2 (what SHA-3 excells at is if you can implement it with hardware gates); hence it would appear to be the wrong direction for you.

  What is the best hash to use, obviously it needs to be relatively fast and by my standards sha-512 isn't fast

Well, before I get into that, I would like to point out that your HMAC implementation can likely be improved.

In HMAC, as you know, we use the key to generate an IPAD and an OPAD; we then compute $a = Hash(IPAD | Message)$, and then compute $b = Hash(OPAD | a)$, and $b$ is the result of the HMAC.

Now, IPAD and OPAD are sized to be precisely 1 Merkle-Damgaard block of the hash function; hence one thing you can do is you can compute the initial hash compression function evaluation $Compress(IV, IPAD)$ and store that intermediate state; similarly, you can compute the initial hash compression function evaluation $Compress(IV, OPAD)$ and store that.

Then, to compute $a = Hash(IPAD | Message)$, you can restore the initiate state for that, and just compute the hash over the message (just using the precomputed evaluation as the IV, and adjusting the final padding to account for the longer message); similarly, you can use the same trick when computing $Hash(OPAD | a)$.

This allows you to compute HMAC using two fewer hash compression operations over the naive method.  Now, if you are computing the HMAC only once for a key, or if you are computing HMAC over a huge message, this doesn't help much.  However, if you are computing HMACs over a number of tiny messages, this helps a lot.

I suspect you aren't using this optimization, because if you were, the time differential between 64 bytes messages and 128 byte messages would be considerably larger.

Implementing this may have the time taken to HMAC a 64 byte message on SHA256 by 40% (3 hash compression operations rather than 5).

Now, as for the "best hash"; well, if you want to stick with NIST approved operations, the fastest alternative is HMAC-SHA1 (which is FIPS approved still); if you don't care for that, well, the best you have is HMAC-SHA256.


Does any operating system offer full system encryption, including RAM and SWAP? I‘ve been looking around and did my research but I could not find any information if any operating system exists which would be able to encrypt all data, including RAM and the SWAP partition, to protects things while the OS is up-and-running.  I found infos about disk encryption, file encryption, and much more, but I seem to have a hard time to find infos related to a “complete system being protected by the operating system”.

Simpler said: I’ld like to know if it’s possible to protect a computer system with such an OS so that – when anyone steals the hard disk of a webserver while it’s running – the thieve can’t decrypt the data.

Is there something like a fully encrypted OS, or is that impossible for some reason(s)? If, which reason(s) would that be?

Yes and no.

Let's go through the requirements you have step-by-step:

  So if anyone steals the hard disk [...] he cannot decrypt the data.

That is widely supported in modern operating systems and called full-disk-encryption (FDE). On Windows you'd use something like Bitlocker for this task and on Linux something like dm-crypt should do the trick. Note however that this would require entering a passphrase every, single time you boot the server up.

  I mean all it's encrypted, also [...] the swap

Any decent full-disk encryption system hooks itself into the driver stack and encrypts everything going through this stack shortly before the drive is actually invoked to write, thus, as the swap is a normally written onto the drive, it will be encrypted as well by most full-disk-encryption programs.

  I mean all it's encrypted, also the RAM [...]

This is where things get tricky and the answer becomes "no".
You can encrypt data in RAM, as it's just data and the algorithms don't care where the data resides. However this would also mean leaving the key in RAM, which makes this kinda pointless. BUT, there's Intel SGX and AMD's upcoming memory encryption techniques (PDF whitepaper). They both consider the OS an adversary and thus offer protection against him, even in RAM. So with a combination of standard encryption and SGX based encryption, you could get large parts of the RAM only holding encrypted content, but SGX also needs external management and because of that you can't encrypt everything in RAM (for now), as long as you don't put an encryption chip in between your CPU and the RAM. Also note: As these technologies are very recent, there isn't many products that use them right now, especially since Intel requires a business contract with SGX production-users.

"Encrypt everything" sounds nice in theory, but isn't practicable. There are trade-offs to be made. Full-disk-encryption will protect you against attackers stealing your physical disks and reading their contents and RAM-protection can at most defend against attackers who get root access and / or physically steal and try to read-out the RAM (note that RAM doesn't hold data for a long time), but the technology isn't there (yet).


What's the utility of the last two messages of Needham Schroeder Symmetric key protocol The protocol works like this

But I can't understand what's the utility of message 4 and 5, what do they protect from?
They do not protect from replay attack if Ks gets compromised because B won't be aware anyway of its freshness.
Wikipedia says that Bob sends Alice a nonce to show that he has the key, and Alice sends back a modification of it to show that she has the key too.
Isn't it obvious that she has the key if she sent it to Bob previously?
Or is it just a sort of acknowledge (which kind of surprise me because it would be the first time I see it in these protocols)

Messages 4 and 5 are meant to protect the recipient B from a replay attack. It is a basic challenge response mechanism. Otherwise an attacker could just replay previous messages and have the very same interaction with B again. That is bad, if e.g. the message is just "increase some counter", or another message that has a lasting effect or changes a state.

This doesn't protect from a compromised Alice or if the trusted party is compromised. It only protects from an attacker controlling the network.

More explicitly: Eve has a copy of a past interaction between Alice and Bob. She has message 3, but it is encrypted and she can't extract the content. But she is able to send that same message to Bob. If Bob doesn't have a full record of every interaction in the past (and checks against all those records), he thinks it's a new one. If Eve just replays every message originally sent by Alice, Bob would have no way to detect it isn't really Alice sending those messages. Of course the interaction could be adaptive, and Bob then notices a difference, but the protocol should also work with non-adaptive messages.


Deriving 2 keys using HKDF I have an encryption scheme that uses a 256-bit master key, from which 2 separate keys (one for AES-256-CTR encryption and one for a HMAC-SHA256) are derived using HKDF. However, I'm not sure exactly how to utilize HKDF without screwing it up, so straight to my concerns:

Is it safe to just use SHA-512 as the hashing algorithm to get a 512-bit output and split it in 2?
I know that using salt is not mandatory, but does using it actually improve security?
I know this might be a dumb idea, but still ... can the salt be the IV used for encryption?

Although the answer is already accepted, I'll add an answer with a different look on things.

It's safe, but that's not what HKDF-expand should be used for. The idea of HKDF-expand is to call it twice, once for each key, using the info element to distinguish between the two (e.g. info could be an ASCII encoding of the key name). Note that HKDF should have a relatively short running time.
Although it is not required, it is best to use a salt. So unless there is some important reason not to, use a salt. For KBKDF's a salt is unusual, but the authors seem to think it is important; see the quote underneath this answer.
You could, however I would urge you to independently generate it using HKDF-expand, see answer (1).

Quote for part #2 (see 3.1 of the RFC):

  We stress, however, that the use of salt adds significantly to the
     strength of HKDF, ensuring independence between different uses of the
     hash function, supporting "source-independent" extraction, and
     strengthening the analytical results that back the HKDF design.


Request for review: known plaintext mitigation by rotation and xor encoding When using structured data inside a plaintext (such as gzip headers, xml, etc.) they generate known plaintext which may be useful in cracking the ciphertext.

So I had these two ideas on how to make this known structure less useful to attackers while preserving the value to those with valid decryption keys:

First, if we prepend zero use a random xor, when decrypting we can remove the first value and xor the remainder of the text by that value it may make decrypting the ciphertext somewhat more difficult as the known plaintext is somewhat varied.

The second idea is to just rotate the start of the message by a random amount putting the known plaintext at a random place in the block (obviously less useful with streams). By prepending the coded plaintext with the offset with the original message can easily be recovered without introducing a known plaintext as the offset is a random number).

Further these two methods can be combined. Obviously these would add no cryptographic value to texts without known substrings and are completely useless without being paired with a real cipher.

The question is how useful would they be in mitigating a known plaintext attack?

For a secure cipher, the best attack is a brute-force key search: Iterate through all keys and try decryption until you find one where the result fits.

Having known plaintext in known blocks of the message helps, because then we need to only decrypt one block for most keys.

With your method, one might need to decrypt enough blocks to be able to undo the transformation ... this makes it a bit harder, but only by a small constant factor (depending on the number of blocks needed, at most the whole message will need to be decrypted).

As usually the key sizes for ciphers considered secure (like anything $\geq 128$ bit for a symmetric cipher) are anyways out of reach for brute-forcing even with known plaintext, your method doesn't help in practice.

With a non-secure cipher, or one with a too small key size, this could help to increase the costs (or time) of cracking for an attacker significantly, for example from using 5 million \$ hardware to 50 million \$ (in the same time), or from 5 hours to 50 hours (using the same hardware), assuming that in average 10 blocks instead of one needs to be tried.
But then, you are better of using a secure algorithm with a sufficiently big key size than trying arbitrary modifications of the plaintext combined with an insecure cipher.


How to compare two datasets „anonymously”? Ok, I hope this question makes some sense because I am not so sure how to word it any differently… Imagine the following situation:

There are 10 defined colors (blue, orange, yellow etc.)
There are 2 Persons and each of them has 1 favorite, secrete color
The 2 persons don't know each other's favorite color, however, they
want to know if they share the same

My question: How can they do a comparison without exposing their own favorite color to the other person (or to anyone else!) in case they do not match?

Or, to explain the problem with other words: Person A should only know the favorite color of Person B if they share the same. Hence, the result of the comparison must only be True or False.

My first thought was: Every person could simply create a hash of their favorite color using the same hash algorithm (MD5, SHA etc.) and then they can compare the hashes. But obviously, that doesn't work, because it’s easy to find out which hash belongs to which color.

Is there a solution for such a use case? Any help would be highly appreciated.

That sort of thing is known as multi-party computation, and you

should use a Socialist Millionaire Protocol for your particular instance.


Since it gives negative power, how is rcon(0) calculated in AES? I'm trying to calculate Rijndael key schedule "Rcon" values manually. I know how to calculate each value with the equation rcon(i) = x^(i-1) mod x^8 + x^4 + x^3 + x^1 + 1, for example:

recon(10) = x^(10-1) mod x^8 + x^4 + x^3 + x^1 + 1
x^(9) mod (x^8 + x^4 + x^3 + x^1 + 1)
=> x^5 + x^4 + x^2 + x
=> 0011 0110
=> 0x36 (10th number in RCON Table)

But if i equals to 0 then

rcon(0) = x^(-1) mod x^8 + x^4 + x^3 + x^1 + 1

According to "Wikipedia: Rijndael key schedule ~ Rcon", the first value in Rcon table is 0x8d, which most probably is the value for rcon[0]. I would like to know how it is calculated.

I know how to calculate the mod on paper and this is exactly how I calculated the 0x36 above. But since the power of x is -1 in this case, I am stuck with it. How is rcon[0] calculated in AES?

See my previous answer here regarding rcon calculation:

Rijndael: explanation of Rcon on Wikipedia?

It is essentially caulcated by division of 0x01 within the finite field.

The most important thing about rcon(0) is that there is no round 0, and thus you will never actually use it in any calculation. Also take note of my comment that the Wikipedia page is not completely correct. I will probably edit the page if someone else does not get to it first.


How to calculate the redundancy of a language I originally asked this question on the information security stack exchange but I think it's better suited here.

I'm trying to calculating the unicity distance for a cipher applied to a language I wrote and I'm having trouble understanding the concept of redundancy in a language.

From this book

  The redundancy of a language severely reduces the amount of information conveyed with each character and the rate of a language is defined as the average number of bits of information contained in each character of a message, i.e. $\frac{H(X)}{N}$ where $N$ is the number of characters in the message.

You need to generate a frequency table for a language to calculate $H(X)$ but an accurate frequency table requires a long message. Won't this cause all redundancies to tend towards 0 since $N$ can be arbitrarily long? How exactly is the redundancy for English, 1 to 1.5 given by this book, calculated? What value of $N$ do they use?

Not really, for example if your language has $m$ letters, and the letters are independent identically distributed then $H(X)=H(X_1,\ldots,X_N)=N H(X_1)$ where $H(X_1)$ is is the entropy of the single letter distribution $(p(1),\ldots,p(m)),$ where $P[X_k=u]=P[X_1=u]=p(u)$ for any $k\geq 1.$

This is because for independent random variables
$$
H(X_1,\ldots,X_n)=
$$
$$
=H(X_1)+H(X_2|X_1)+H(X_3|X_1 X_2)+\cdots+H(X_N|X_1X_2\cdots X_{N-1})=
$$
$$
=H(X_1)+H(X_2)+\cdots+H(X_N).
$$

So $X$ in that statement refers to the sequence of $N$ characters.

If your language is first order markov then
$$
H(X_1,\ldots,X_n)=
$$
$$
=H(X_1)+H(X_2|X_1)+H(X_3|X_1 X_2)+\cdots+H(X_N|X_1X_2\cdots X_{N-1})=
$$
$$
=H(X_1)+H(X_2|X_1)+H(X_3|X_2)+\cdots+H(X_N|X_{N-1})\geq (N-1)H(M).
$$
where $H(M)$ is the entropy of the Markov chain, i.e.,
$$
H(M)=\sum_{s\in S} \mu_s H(X_{n+1}|X_n=s)
$$
where $\mu_s$ is the steady state probability of being in the state $s$. Of course we need to assume a stationary Markov chain here.

See Shannon's classical paper Prediction and Entropy of Printed English (here )for a number of ways of calculating the entropy.


Given a linear block-cipher,how can an attacker decrypt any plaintext value encrypted,using 128 chosen ciphertexts Given the linear block cipher $\operatorname{LinearCipher}(k, p) = c$

$$\operatorname{LinearCipher}(k, p_1 \oplus p_2) = \operatorname{LinearCipher}(k, p_1) \oplus \operatorname{LinearCipher}(k, p_2)$$

where $k$ and $p$ are 128-bits.

If an attacker uses a chosen-cipher-text attack, how can they decrypt any plaintext by choosing 128 ciphertexts?

I'm not exactly sure in which direction I have to think. I believe decryption will also be linear since in linear algebra the inverse of a linear function is also linear. The fact that the attacker can choose 128 ciphertexts hints at maybe revealing the key 1-bit at a time. Any hints and suggestions would be helpful.

You already got the answer by yourself.

As a linear cipher with 128 bit, it can be described by a 128x128 matrix over GF(2). To break the cipher is to find that matrix. But that's easy: column k is the decryption of the k'th standard basis, i.e. the vector (0,0,0,...1,...,0,0,0) , with the 1 on the k'th place.

Example:
Decrypt(0001) = 1101
Decrypt(0010) = 0001
Decrypt(0100) = 1010
Decrypt(1000) = 1111

This gives the matrix M:
1011
1001
0011
1101

Now lets say the cipher text is $c= (1111)^T$

The decryption of c is $M*c = (1001)^T$


How truncated timestamps are used? Consider the following setting: We have a sender $\textbf{A}$ and a receiver $\textbf{B}$. The sender $\textbf{A}$ a wants to send a message $M$ through a channel where each message to $\textbf{B}$ can be up to 8 bytes. Due to the limited size each message can have Truncated Timestamping (TTS) is used.

I am asking myself what possibilities $\textbf{B}$ has in order the check the correctness of the received TTS (this clearly depends on the way the TTS is build, so my question also includes how this is done in practice).

The trivial way would be the cut of the first m bits of the Timestamp and to compare this bits at the receiver end.

how this is done in practice

You always can change "starting point" for timestamp.

This site says that current timestamp is 1529950851 seconds since Jan 01 1970. (UTC). Count seconds from some reference point $T_{ref}$, e.g. $$T_{current} + T_{ref} = T_{real}$$

Depending on the available timestamp size, you can setup different schemes. Lets say, you have 2 bytes for timestamp:

Remember current timestamp $T_{ref}$ at both sides, $A$ and $B$, it must be equal.
In $2^{16}$ seconds, update $T_{ref}$ on both sides, simply adding $2^{16}$

$$T_{ref} = T_{ref} + 2^{16}$$

This scheme is not reliable, and will fail after long period of time, because of clock skew. To mitigate this issue, you need to sync $T_{ref}$ of both $A$ and $B$ periodically.


finding the basis of a kernel in a lattice Given a parity check matrix $A$ we define the $q$-ary lattice
$$\Lambda(A) = \{x \in \mathbb Z^m\;:\;Ax\equiv0\pmod q\}$$
How to find the basis of the lattice and how to find its hermite normal form?

Let ${\bf A}$ be a $n\times m$ matrix with $n|m$ and rank $n$. Write down ${\bf A}$ as $m/n$ blocks of $m\times m$ matrices as follows:
$${\bf A}=\left[{\bf A}_1|\cdots|{\bf A}_{m/n}\right].$$
If ${\bf x}\in\Lambda({\bf A})$, then
$${\bf 0}={\bf A}{\bf x} = \sum_{i=1}^{m/n}{\bf A}_i{\bf x}_i,\pmod{q}$$
where ${\bf x} = \left[{\bf x}_1^T|\cdots|{\bf x}_{m/n}^T\right]^T$.
Without loss of generality, suppose that ${\bf A}_1$ is invertible. hence the above equation can be written as:
$${\bf x}_1=\sum_{j=2}^{m/n}{\bf B}_j{\bf x}_j,\pmod{q}$$
where ${\bf B}_j = -{\bf A}_1{\bf A}_j$, for $2\leq j \leq m/n$.
Using the above equation and by replacing a standard basis as ${\bf x}_j$, $2\leq j \leq m/n$, one can find ${\bf x}_1$, which fully  describes the lattice $\Lambda({\bf A})$.


Realize a MAC using a Pseudo-random function? Given a pseudo-random function and assuming that we do not have any other tools,
How can we construct a MAC?

I believe this can be done. Would like to know if there is more than one way of doing this.

If you have a PRF (with larger input than output), you can use it as compression function in a Merkle-Damgård structure, yielding a hash function which you can subsequently turn into a MAC with HMAC. Indeed, the security proof of HMAC relies on indistinguishability of the compression function from a PRF.

There are still an awful lot of details, though. And the PRF assumption is quite strong.


Can adding bad entropy to good entropy, make a system insecure? For example,

If I needed to generate a random number. I use a good source of entropy to generate r.

Then I add values a, b and c whom are generated from bad entropy such that new entropy = r + a + b + c

How would the overall entropy look like?

The plus sign means to add and not concatenate. I believe that if we concatenated, then this would lead to an overall bad entropy because if we assume that each a,b,c,r each contribute 64 bits to 256 bits of entropy. We would in reality only have 64 bits of good entropy from r. This is my intuition with concatenation.

If you have a variable with maximal entropy, and you combine it with an independent variable with less entropy using Xor or modular addition you will still have maximal entropy.

If you have two independent variables with low entropy and you combine them in the above fashion the result will be a variable with more entropy than either the original ones

If however the variables are correlated all bets are off. Even combining two maximal entropy variables may result in 0 entropy (constant variable ) when adding/xoring them.


What's the principle to design the functionality under UC framework? Though I can get the basic idea of UC Framework, namely let the environment cannot distinguish the real protocol with the real adversary and the functionality with the simulator, I am still puzzled in details:

What's the principle to design the functionality, if it aims to a new scene that Canetti hasn't treated? Are the ability to corrupt parties (by some unknown methods) required to be written into the functionality? What else (except the normal functions) should be written into it?
It is required that the simulator must successfully deal with any adversary. So how to 'predict' the behavior of adversaries if there are some abilities of adversaries which are not listed in the functionality?
What will happen if I write an only seem-to-be-right functionality?
Why do real protocols mostly ignore the message type field (as new-session, test-password, ...) used in functionalities?
Does the environment gives some inputs to the simulator? Does the simulator need to simulate any non-corrupted parties? What information can be got by simulator?
In the real world, who controls the non-corrupted parties?
In the hybrid worlds, who controls the non-corrupted parties? Are they the worlds that exist both simulators and adversaries? Who else exists in those worlds?

What's the principle to design the functionality, if it aims to a new scene that Canetti hasn't treated? Are the ability to corrupt parties (by some unknown methods) required to be written into the functionality? What else (except the normal functions) should be written into it?

Basically, you can design the ideal functionality as you wish. The functionality does not consider corruption, because it is the ideal version. In order to make it more clear, you can consider the functionality as a trusted third party, which takes all the necessary input from all parties, computes the result and outputs it to those parties who should receive it.

  It is required that the simulator must successfully deal with any adversary. So how to 'predict' the behavior of adversaries if there are some abilities of adversaries which are not listed in the functionality?

UC is one of the strongest framework to proof security, because it does not give the adversary explicitly any power. In fact, in UC proofs the real world adversary is mostly just a dummy adversary, who just forwards any message it receives to the environment.

What happens is that you give the simulator some advantage (otherwise it would never work) e.g being able to choose the CRS, extract witnesses, etc.. And then you have to proof that the environment can't distinguish between real and ideal.

  What will happen if I write an only seem-to-be-right functionality?

Well, you prove that the protocol is a secure zealization of your functionality. If the functionality is "wrong" (not what you intended actually), then you have nothing.

  Why do real protocols mostly ignore the message type field (as new-session, test-password, ...) used in functionalities?

An example for that would be great, as it is not really clear what you mean. Sometimes, session IDs, etc. are omitted because they just blow up the length of the descriptions/proofs, making it unnecessary complex to follow.

  Does the environment gives some inputs to the simulator? Does the simulator need to simulate any non-corrupted parties? What information can be got by simulator?

Simulators replace corrupted parties. If the environment can give some input to a normal party and it is corrupted, the simulator has to do exactly the same in the ideal world. The difference is: In the ideal world, all parties and the simulator can only communicate with the functionality and the environment.

  In the real world, who controls the non-corrupted parties?

What does "control" mean? Parties are just independent Turing machines, which process some input and then have some output. Therefore, they don't have any input on their own, and they are activated by the environment, usually after the environment gave them some correct input.

  In the hybrid worlds, who controls the non-corrupted parties? Are they the worlds that exist both simulators and adversaries? Who else exists in those worlds?

Not really. A hybrid argument is, that you have some other functionality $F_{other}$, which is realized by $\Pi_{other}$ (in the UC framework). And then you actually use $\Pi_{other}$ in the real world, while using $F_{other}$ in the ideal world (both where they belong). Since they are already proven indistinguishable for the environment, you can use them for your own proof in their respective worlds. Basically, this is just the composability  of the UC framework.

For some further reading:
The UC approach: an application view


Modelling broadcast functionality in Universally Composable Framework I'm studying the UC framework by Canetti. While I understand the basic idea, there are still a lot of details that I need to work through.

One thing that's puzzling me is how to achieve concurrency under the UC execution mode. For example, in many distributed algorithms, a machine may broadcast a message and then every receiver may do some computation on the message. The result of the computation may be broadcasted again.

The paper says

  In order to simplify the process of determining the next ITI to be activated, we allow an ITI to execute at most a single external-write instruction per activation.

In that case, how does one capture a broadcast functionality, both as an ideal functionality as well as a real protocol?

UC broadcast can be defined by a functionality $\mathcal{F}_{\textrm{BC}}$, which upon receiving a message $x$ from party $P_i$, sends $(x, P_i)$ to all parties and the adversary.

This is formally given in, e.g. Section 3.2 of a paper by Goldwasser and Lindell. However, many higher-level protocols use broadcast without explicitly specifying the functionality, because it is so straightforward.

That paper also contains the following, very simple echo-broadcast protocol for any $t < n$ corruptions:

$P_i$ sends $x$ to all other parties
Every other party re-sends $x$ to everybody else and checks that they received the same values.
If any value is inconsistent, abort. Otherwise, output $x$.

This is secure in a slightly weaker model, where a corrupt party may force some honest parties to abort; however, any honest party who does not abort will learn the correct output.


Time locked cryptography using Bitcoin difficulty param and/or smart contract? Outcome:  Create a message with a count down timer.  Once a top level password is entered, a countdown timer starts.  Once timer expires, the message is decrypted.

Known methods:  Proof of work.  User has to use computing power to decrypt the message.

Problem:  The computer power will change in the future.  I want relatively accurate time lock, now & years from now.

Are these possible solutions…?

Proof of work time lock tied to Bitcoin difficulty:  Bitcoin has a reactive difficulty parameter that will reflect current state of processing technology.

Is there anyway to use the Bitcoin difficulty parameter as to make a time locking message with a relatively accurate time lock time, now & in the future?

Smart contract based:  A smart contract, that once a first layer password is input, a count down timer starts, based on a time now oracle of some kind.  Once expired, the second layer message is decrypted.

A) Are any of these possible?

B) Are there any other existing solutions that would get the desired outcome currently?

**Removing serial hashing burden, but still getting the same benefit: **
When top level password is entered, BTC current block is noted.  When BTC block reaches current block + X, 2nd layer message is decrypted.

Possible?

Those are indeed the main known solutions. Note that your solution A has been explored in the cryptographic community, this paper is an example of a theoretical work on the subject, but I think there are others, more practical proposals for using the blockchain as a timer (it was discussed at length in a slightly different context in this recent paper).

Note 1: as far as I know, no such method has yet been evaluated and experimented in practice, yet alone deployed.

Note 2: a small correction to your first item, "proof of work": actually, a proof of work does not suffice here. This is because if the work involved is parallelizable, meaning the work can be divided across many CPUs, then there is no guarantee about the time it takes to complete the task - did the opponent use 1 CPU and time T, or T CPUs and time 1?

The right solution is to use proofs of sequential work, which demonstrate that the prover has executed T steps of a problem which is conjectured to be impossible to parallelize. Many examples exist, based mainly on the conjectured hardness to parallelize modular squaring (given a random $r$ and a modulus $n$, compute $r^{2^T} \bmod n$, where $n$ is an hard-to-factor RSA modulus). Many recent papers have worked on related constructions, e.g. look up "proof of sequential work" or "verifiable delay function".

A byproduct of using proofs of sequential work is that the work cannot be sped up with more CPUs, so the right user will just use a single CPU dedicated to solving it, which makes the work required somewhat less cumbersome (no need to have thousands of computers "farming" the proof).


Definition of Cascade for Blockciphers I have seen that given blockciphers $F,G : \mathcal{K} \times \mathcal{M} \to \mathcal{M}$, their cascade $F \circ G$ is defined to be $F \circ G : \mathcal{K}^2 \times \mathcal{M} \times \mathcal{M}$ via $(F \circ G)_{(K,K')}(M) = G_{K'}(F_K(M))$. My question is why it's done this way around, not the other order?

In "standard life" (see Wiki article), if I have two functions $f,g : X \to X$, then $(f \circ g)(x) = f(g(x))$. However above, writing $f = F_K$ and $g = G_{K'}$, we have, in essence, $(f \circ g)(m) = g(f(m))$.

I understand that it's just a formal convention, but it seems strange to pick the formal convention which is (or rather, appears to me to be) counter to the previously established convention.

Incidentally, I saw this notation in Hoang-Morris-Rogaway, twice on page 6.

It's at the authors discretion. See the footnote in the book (below). Also Wikipedia makes it clear.

:


Best practise for encryption in a password manager I'm trying to make a password manager for Windows installed computers, and after researching the best ways to encrypt the passwords in the database (I'm new to cryptography) I think I've come up with a good way to do it, but I'm still not sure.
How the key is made when the user first opens the program:

The user inputs the master password, the password that will unlock the password database.
A random salt of 16 bytes and the master password will be put through a KDF (PBKDF2 using SHA512) to derive a key $k$.  $$k = \operatorname{PBKDF2-SHA-512}(password, salt)$$

How the database is encrypted:

Using the $k$, the database is encrypted using AES 256 bit CBC. $$ c = \operatorname{AES-CBC}(k,IV, database)$$

The $IV$ and the encrypted database $c$ are then encoded to base64 before store.

Where and how the database, salt (for the key $k$) and the $IV$ (for AES) are stored:

The salt, $IV$ and encrypted database will be dumped into a python dictionary, and written to a txt file e.g. {"salt": "T\x96\x829\xed\...", "iv": "00/JOAIsHs9XtB5acawBhA==", "database": "TE4nhDRTJ+JW..."}

The decrypted database file is then deleted and overwritten with random encrypted data multiple times to properly wipe it.

This txt file is then encrypted with AES 256 bit CBC, the key is 32 random bytes which is then hidden somewhere on the computer (could this part be skipped?).

I would prefer if no external devices would have to be used to store the second encryption key.
Also, every time the database is decrypted, and then encrypted back again when the user is done, a new key with a different salt is produced, and a new IV for encryption is produced.
Is this how it's supposed to be done? Or am I completely wrong?

If the key is derived from the password there is no reason to store it anywhere.
The main problem in your outline is not the cryptography.
You are explicitly writing the passwords to disk. This is a really bad idea. The deletion may not happen at all, e.g powe failure. Even if it does on a modern hard drive it is really hard to overwrite data it won't actually be written to the same place and thus traces of previous data may remain.
A secure implementation will not only avoid writing to disk it would explicitly request from the OS to not swap out the sensitive memory parts. The OS may allow you to do this for only a small piece of memory. If the password DB is large decrypting the whole thing may be problematic and you should consider only decrypting the part you want but that causes a behaviour change you may or not want.
You may want an authentication if you worry about someone mangling your db.
You didn't mention IV selection, needs to be from a strong random source and replaced everytime you change anything and need to reencrypt.


What are recommended, general strategies to start block-cipher design and/or analysis? I (and many others for that matter) have always been fascinated by the inner workings of the modern building block of cryptography: block ciphers.

Now, the ressources on the "black art" of design and analysis of these ciphers are sparse; especially for the entry level. Available information like the Schneier guide seems to be somewhat outdated (due to its age).

What's the general consensus of the “best” (read: recommended) strategy to start designing and/or analyzing modern cryptographical block ciphers?

Nota bene: Think of this as a general, wiki-alike question – for learning purposes only. (Besides that, this Q&A would represent a place we can point people to when alike algorithm design questions arise.)

In order to design and analyze a cipher, we have to establish what a cipher is supposed to accomplish. Put simply, we would like to be able to transform information in such a way that only those who are authorized may perform or invert the transformation. We can refer to this transformation as "encryption". Unauthorized parties may exist that should not be able to obtain any information protected by the encryption method, despite the fact that they can/will try to do so, if given the opportunity. This applies even if the work that would be involved is a large, nontrivial amount. We can refer to unauthorized parties as adversaries.

Ideally, we would like the mutual information required by the authorized parties to be minimal, and for it to be obtainable with some level of convenience. If it were not for these two extremely practical aspects, the One Time Pad  would be literally unbeatable, with information-theoretic security, implementation simplicity, and maximum efficiency (just a single addition per character!). A OTP is not a block cipher, but it makes for a good reference point to measure against.

Unfortunately, one time pads require the key material be as long as the information to be enciphered, and prepared ahead of time by the authorized parties. This violates our two practical desires listed above, so we must design other algorithms that can re-use a much smaller key.

One temptation is to keep the encryption algorithm itself secret. Unfortunately, keeping an algorithm secret implies that all users of the algorithm know the secret to encrypting/decrypting. As the number of users that know the secret increases, so does the likelihood that the secret will become compromised by adversaries. This would fail the original design goal, and only does marginally better then the OTP in terms of practicality and the size of the secret to be protected.

This leads to the third, most successful option: Using a publicly known algorithm that concentrates the required secrecy into a key that is used by the algorithm.

Whatever method is used to encrypt, the information may be subject to attack by adversaries. The job of encryption is to resist this attack, and keep the information protected. This means a few things:

Since modern ciphers use a key to authorize parties to perform the transformation, the goal of an adversary is to obtain the key

Obtaining the key implies the ability to encrypt plaintexts and decrypt ciphertexts, violating the original design goal of the cipher

Similar to how a lock on a door uses a key
You just have to protect the key, not prevent anyone from knowing there is a lock
The key is reusable, and has a very long lifespan.
The key should be relatively small - 128 to 256 bits is common

The key must remain secure even if the adversary:

Possesses vast amounts of ciphertext
Knows the plaintext contents of a message, and the corresponding ciphertexts for each message
Can trick an authorized party into encrypting/decrypting messages for the adversary

Choose messages to encrypt or decrypt at will.
Can adapt or modify future encryption/decryption queries in response to past queries.

Most of the complexity of a modern cipher comes from the attempt at protecting the key, and by extension, the plaintext. Designing a cipher with a reusable key will require an understanding of the ways that the cipher and key can be attacked. In order to design a cipher, you must learn to think like the adversary, and study how ciphers are broken.

Standard attacks

There are a handful of generic attack methods that any new cipher must protect against: brute force search, differential cryptanalysis, and linear cryptanalysis.

Brute force search means that the adversary simply guesses all possible combinations of key values, until the correct key is found

Has a worst case time complexity of $2^N$, where $N$ is the width of the key in bits

time complexity is only accurate if the key is uniformly random
64 bits is considered too low for modern computers
128 bits is considered secure for now
256 bits is considered secure forever, even in the face of futuristic quantum computers

Differential cryptanalysis exploits the probability that a particular difference ($\Delta_1$) between inputs ($t_1$ and $t_1'$) will be propagate to a particular output difference ($\Delta_2$)

By testing all the possible input differences, it is possible to return probabilities to have some output differences. A couple of specific differences $\Delta_1$ and $\Delta_2$ is called a differential and noted ($\Delta_1 \Rightarrow \Delta_2$).
The more likely that a given differential ($\Delta \Rightarrow \Delta'$) holds, the more effectively this behavior can be exploited against the cipher
A relatively simple tutorial with code can be found here
The original paper by Biham and Shamir can be found here

Linear cryptanalysis exploits the probability of a subsection of bits from a given input is correlated with a subsection of bits in the output of a function

A subsection of bits is selected via bitwise masking
The exploitable relationship is if the parity  of the hamming weight  of the subsection of input and output bits is the same
The more regularly this relationship occurs, the more effective linear cryptanalysis will be
A relatively simple tutorial with code can be found here
The original paper by Matsui can be found here

Linear and differential cryptanalysis can provide hints as to what the internal state of the cipher may be, up to a certain point. This can reduce the number of possible values for a part of the key that an adversary will have to guess. These are considered to be two of the most powerful tools in regards to cryptanalysis of a modern cipher.

Block Cipher constructions

There are two main classes of cipher constructions: The Feistel network , and the substitution-permutation network.

The basic design of the Feistel network is to split the message block into two halves, a left and a right. A keyed function with good diffusion and confusion is applied to right half, and the output of this is added to the left half. The halves are then swapped, and the process repeated. Decryption is more or less the same operation performed with the reverse keys, and so this construction is relatively lightweight in terms of implementation complexity. DES is an example of a Feistel network. There are differential and linear attacks against DES.

The design of a substitution permutation network is typically finer grain then a left and right half of a Feistel network. For example, in the Rijndael cipher, also known as Advanced Encryption Standard (AES), the message is operated upon as 16 x 1 byte state, arranged as 4 rows and 4 columns. It consists of 4 main steps: a byte substitution, a row transposition, a mixColumns step, and the addition of key material via XOR.

Many, if not all modern block ciphers, are made of repeatedly iterating the same core function(s), often times with multiple different keys between each application. Often times, these keys are derived from the master key that is actually supplied to the cipher by the user. We refer to keys generated this way as the round keys, and the process of generating them the key schedule.

The way round keys are derived can influence both the security and efficiency of the cipher. Ideally, recovery of any round key information should reveal as little as possible about other rounds keys or the master key. This is one of the strengths of the OTP: recovery of a byte of key material (i.e. via known plaintext attack) provides no assistance in the recovery of any other bytes of the key. It is also generally considered beneficial for the generation of round key material to be quick, as a cipher with a slow key schedule may have greater latency and/or lower throughput.

Designing a round function

In order to know what to operations to use, we need to know what we need to accomplish:

Diffusion

Flipping one input bit anywhere should flip (about) half the output bits on average
Bytewise shifts, rotations, and transpositions can help spread the influence of a given subsection of bits
Bitwise transpositions can be used too, but can be relatively slow in software (but potentially fast in hardware)

Confusion/Non-linearity

The relationship between the key and ciphertext should be complex
A linear cipher can be broken by gaussian elimination
Mixing arithmetic in different fields can provide non-linearity (i.e. xor and addition modulo 256)
Boolean functions can provide non-linearity

Invertible only with the correct key

The cipher will only provide confidentiality if secret (key) material is introduced at some point.

Applying a key on the input before applying any rounds and after applying all rounds is called key whitening and is common
Additionally, a key is added every N rounds, where N is often 1 (i.e. after every round)
Key addition is often times done via xor and addition modulo (2**wordsize_in_bits), or both

There should be no "weak keys"

So our goals are to combine the message with a key, and flip lots of bits in a diffusing and non-linear fashion.
Ideally, we would like the composition of our operations to produce output similar to that of a random permutation.

Some available instructions are:

Xor

Useful for combining two inputs (i.e. message and key)
Is its own inverse (an involution)

No subtraction instruction required to invert

Bit sliced
Needs addition/boolean function/s-box lookup for non-linearity

Addition

Useful for combining two inputs
Requires separate subtraction instruction to invert
Tends to flip low order bits more then high order bits

Lookup tables

Useful for good differential/linear properties
Effectively equivalent to the cached inputs/outputs of a non-linear function
Can be vulnerable to timing attacks on machines that utilize a cache

Boolean functions

Useful for non-linearity
Some examples are the Choice and Majority functions

Choice

Logically, If C then B, else A
c ^ (a & (b ^ c)) (for mathematicans: $c\oplus(a\wedge(b\oplus c))$ )
Bit sliced operation

Majority

(a & b) | (a & c) | (b & c) (for mathematicans: $(a\wedge b)\vee(a\wedge c)\vee(b\wedge c)$ )

Rotations/Shifts

Useful for diffusion and carrying/spreading differences through a word
Generally done by fixed amounts, but not necessarily

Transposition

Shuffling the order of state words can help provide diffusion
Transposing bytes according to secret data can be vulnerable to timing attacks (secret dependent memory access is the concern)
Includes rotations

Composed bitwise and bytewise transposition:

Acts like a shuffle (permutation) of the input bits
Only modifies a given bits position, not its value (Does not modify hamming weight)
Is a linear transformation
Example: The Keccak permutation, specifically the Rho and Pi steps
Can provide "weak alignment"

Pseudo-Hadamard transform:

Provides diffusion
Used by SAFER and Twofish

Some example combinations of the above operations:

Rijndael consists of addRoundKey, mixColumns, shiftRows, subBytes on the message:

subBytes is a lookup table (good differential/linear properties)
shiftRows is a bytewise transposition
mixColumns is a linear transformation that, in conjunction with shiftRows, provides diffusion
addRoundKey xors the key with the state

DES round function consists of an expansion permutation, key mixing, s-box application, and bit permutation

Expansion compensates the S-boxes going from 6 to 4 bits.
Keys are applied every round via xor
S-boxes provide resistance against differential cryptanalysis
Bit permutation provides diffusion

Serpent round function consists of key-mixing XOR, a 4×4 S-box, and a linear transformation

Keys are applied every round via xor
S-boxes are applied in parallel (bit sliced design)
Linear mixing provides diffusion

TEA uses only addition, shift, and XOR:

xor/addition create nonlinearity and apply key material
shifts/additions provide diffusion

As we can see from some examples, there appear to be at least two different approaches:

S-box based designs

Can offer very good linear/differential properties with good performance
Can be hard to find good large s-boxes because of the huge search space
Tend to be used in conjunction with a linear mixing layer for diffusion
Rijndael strategy:

Use an s-box with the optimal worst case differential/linear properties
Use a mixing layer that aims at increase the lower bound of the rate of diffusion
Notice how it's designed around the worst case scenario

Can provide clear proofs of resistance to differential/linear attack

ARX based designs (addition, rotation, xor)

Are inherently less conducive to timing based side channel attacks then s-box based constructions

Addition, XOR and rotation by fixed amount are often times implemented in constant time

Fast performance on PCs (especially if you can avoid memory accesses/stick to the registers)
Compact/simple implementation (does not require the space that lookup tables need)
Not as straightforward to analyze security to differential/linear attack compared to s-box based design

Many ciphers use a set of constants. Every round, a new constant is introduced to the state via addition/xor. This can help against slide attacks by making successive rounds different.

Breaking a round function

Before you resort to applying linear and/or differential cryptanalysis to any new design, considering running some statistical tests. Statistical tests can tell you very quickly whether your latest design is totally broken. Note that statistical tests cannot confirm whether a design is cryptographically secure, it can only confirm that a design is insecure.

Some example tests might be:

Avalanche test

Generate blocks of random data with a given key (i.e. encrypt an incrementing counter) and measure the hamming distance between successive outputs (measures diffusion of data)
Encrypt the same series of successive values with a different key, and measure the hamming distance between the previous set of random data and the new set (measures diffusion of key)

Randomness test

Generate a sizeable (>1MB) amount of psuedorandom data with the cipher (i.e. by encrypting an incrementing counter)
Pass the data to a tool such as ent, dieharder, or the NIST test suite

Run the mentioned tests on both your design and on os.urandom: ideally the two results should be indistinguishable.

When devising an attack, try attacking a reduced (single?) round version of the cipher first. Look for the weakest points in the design.
Try practising against FEAL, it has a major weak point and is useful for learning differential/linear cryptanalysis, and slide attacks.
Some of the attacks against DES would probably be helpful ways to learn about linear cryptanalysis and brute force search

Once you've got a handle on those, there are actually many different attacks besides generic linear/differential cryptanalysis
You may find some software related to cryptanalysis here

Math and visualization

If you find visualizations and diagrams helpful, this page may be interesting to you.
If you do not know math well, try learning some of the notation. Much of the information you want to understand will be in scientific research papers and written in the language of math.

Some of the subjects that will prove useful when reading papers and in cryptanalysis/cipher design are:

Basic Set theory
Basic Probability theory
Basic linear algebra
Boolean logic
Finite fields


Block cipher block and key sizes Is there any point in making block size less than key size in block cipher?
For example, Russian GOST symmetric cipher uses 256-bit keys to encrypt 64-bit blocks. That means there are many keys which give the same result, so why making keys so large?

GOST symmetric cipher uses 256-bit keys to encrypt 64-bit blocks. That means there are many keys which give the same result

This is actually incorrect. A block cipher, when given a key, maps $n$-bit plaintext blocks to $n$-bit ciphertext blocks (and vice versa for decryption). Here's a toy example for $n=2$:

  $E_k(00) = 01 \\
E_k(01) = 10 \\
E_k(10) = 00 \\
E_k(11) = 11$

Although there are $2^n$ possible plaintext blocks and $2^n$ possible ciphertext blocks, there are actually $2^n!$ different possible ways to map plaintext blocks to ciphertext blocks. In this toy example, there are actually $2^2! = 4! = 1\times2\times3\times4 = 24$ different ways of mapping each two-bit input to a unique two-bit output.

Back to your question, GOST uses 256-bit keys, meaning that there are $2^{256}$ possible keys. However, with a 64-bit block size, there are $2^{64}!$ different possible permutations, and $2^{64}!$ is much larger than $2^{256}$.


How would I prove a number is not within a range? This would be the opposite of a rangeproof.

For example, I wanted to prove that my number was not between 0 and 200 in zero knowledge?

On a separate note: how would I prove that I hold a number, but it is not a specific number x ?

You can achieve that by combining two range proof with an OR proof.

Specifically, given a commitment $c$ to a secret number $x$, you would prove the statement: ($x > 200$) OR ($x < 0$). Each of the two statements can be proven using any standard $\Sigma$-protocol for range proofs (see e.g. my answers here and here), and there are standard methods to construct a $\Sigma$-protocol for the OR of two statements given a $\Sigma$-protocol for each of the statements. You can find simple explanations about how this works by reading Section 3.5.1.2 of my PhD thesis.

For your second question, the usual strategy is as follows: you have a homomorphic commitment (e.g. a Pedersen commitment) to a value $v$ over $\mathbb{Z}_p$, where $p$ is a prime, and you want to prove that it is not equal to $x$. To do so, compute $m = (v-x)^{-1} \bmod p$ and commit to it. Note that $v-x$ has an inverse modulo $p$ if and only if $v \neq x$. Then, prove that the committed value $m$ was correctly constructed by proving that $m\cdot (v-x) = 1$, using any standard $\Sigma$-protocol for proving multiplicative relations between committed values.


Are there any special points on an elliptic curve which would weaken security? So, according to the elliptic curve discrete logarithm problem:

$$A=[r]B$$

In which $A$ and $B$ are points on the curve, and r is the scalar. It is trivial to compute $A=[r]B$ if $r$ is known, but it would be incredibly difficult to find $r$ if $r$ is unknown.

Now, take bitcoin's elliptic curve as an example - secp256k1. Are there any "special" point $B$s on this curve which would allow an attacker, with knowledge of $A$ and $B$, to trivially compute $r$, and thus render the elliptic curve insecure?

Let's first consider your proposed secp256k1 curve. The order of the curve is prime, which means any (valid) point on the curve will generate the whole curve; for any choice of your base point $G$ except for the point at infinite $\mathcal O$, there are integers $r$ such that $[r]G$ reaches the whole curve. In other words, the only sub groups are the whole curve and the trivial group $\{\mathcal O\}$.

This is however is not true for all elliptic curves.  In fact, many have a composite structure (order $n=r\cdot h$), consisting of a large subgroup of prime order $r$ and a "cofactor" $h$. This property can lead to a subgroup confinement attack.  For more information about the cofactor, see this excellent answer. In order to avoid this, care has to be taken when these kinds of curves are used in protocols.

This is (of course) not the only attack we can think about, but it's the most evident from wording of your question. SafeCurves, a webpage by people with a lot more understanding of elliptic curve cryptography than me, lists up many curves with their flaws. Curves like secp256k1 may be safe from subgroup confinement, but have other flaws w.r.t. timing and side channels.


Shadowed identity in cryptography I was trying to implement zero knowledge protocol for authentication based on the paper "A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory".

In that, the first step is…

  each security device with identity $I$ receives an authentication value $B$ (The inverse of $A$ modulo $n$) computed by some authority from $A=J^{1/\mu} mod\ n$, where $J$ is the shadowed identity $I$

Also, they have defined “shadow” as…

  Shadow: One first completes a short message (half the length of a public modulus $n$) with a similar sized redundancy, named shadow, then extracts the $\mu^{th}$ root of this element in the chosen ring based on the composite integer $n$.

From my point of view (being a programmer), I do not understand what this “shadow” is and how to calculate it.

Also there is a sentence…

  then extracts the $\mu^{th}$ root of this element in the chosen ring based on the composite integer $n$

How I set the value of $\mu$? Can I take any arbitrary value? What is the significance of that value?

  Also there is a step $t=r.B^d\ mod\ n$. This means $(r.B^d)\ mod\ n$
  or $r.(B^d\ mod\ n)$?

The GQ identification scheme is essentially a zero-knowledge proof of a value $x$ such that $x^\mu \equiv J \pmod N$ where $N$ is an RSA modulus and $(\mu,N)$ are system parameters and $J$ is known to the verifier and $x$ only known to the prover.

Now your question is not directly concerned with the aforementioned proof where a user shows the possession of a credential, but with how credentials are issued to users by the authority.

Before going into the questions regarding the GQ identification scheme, I briefly recall existential forgeability of textbook RSA signatures.

Recall the RSA setting where we have an RSA modulus $N=pq$ being the product of two primes $p$ and $q$ and the public exponent
 $e$ being an invertible element of the multiplicative group $\mathbb{Z}_N^*$ (with order $\phi(N)$) and the private key $d$ it's multiplicative inverse,
 i.e., $d \equiv e^{-1} \pmod{\phi(N)}$. Now we may abuse the notation and write $d:=1/e$ (what is done in the GQ paper).

So, in texbook RSA signatures the computation of a signature for a message $m\in \mathbb{Z}_N$ amounts to computing
 $\sigma \equiv m^d \pmod{N}$ and verification amounts to checking $m\equiv \sigma^e \pmod{ N}$.

Observe, that by simply choosing $\sigma$ and computing the message $m$ as $m:= \sigma^e {\mod N}$ gives an existentially
 forged message signature pair $(m,\sigma)$ for the textbook RSA signature.

Observe, however, that the adversary cannot
 control the message $m$, since the adversary cannot predict what $\sigma^e$ will yield (consequently, it is a good idea to apply a cryptographic hash function $H$ to messages before signing, since then such an existential forgery would yield $H(m)$ and one would need to find $m$ which is firstly hard given a secure hash function and moreover will very likely not yield a meaningful message $m$ anyways. This is called the hash then sign paradigm).

Shadowed Identity

Now, exactly this is the purpose of a shadowed identity in GQ, i.e., we require the credential including identity $I$ to have some structure and thus the identity is shadowed to $J$.
 Consequently, it is not efficiently possible to choose a random element $A$, compute it's $\mu$'th power ($\mu$ is the public key $e$ from above) and obtain a valid shadowed identity $J$.
 Note, that one could choose $A$ randomly and compute $J\equiv A^\mu \pmod N$, but requiring $J$ to have
 some defined redundancy (being an shadowed identity),
 such a forgery will not lead to a valid identity $J$ under the redundancy scheme with very high probability.

Note that this prevents an adversary from computing a credential on its own without interacting with the authority (knowing the value $1/\mu$). The authority, however, can form the shadowed identity $J$ and then compute $A\equiv J^{1/\mu} \pmod N$. Observe that this is essentially a textbook RSA signature of the authority for message $J$.

Nevertheless, it is not exactly stated in the paper how this shadow should be chosen.

Extracting $\mu$'th roots

Note that $\mu$ plays to role of $e$ (the public exponent) in the RSA setting and note that computing the inverse $1/\mu$ from $(\mu,N)$
 (which is equivalent to the private exponent $d$ in the RSA setting) requires to know the factorization of $N$. Observe that
 $1/\mu$ is computed as the multiplicative inverse of $\mu$ modulo $\phi(N)$ using the extended euclidian algorithm.

In the GQ identification scheme as described in their paper, the factorization of $N$ is only known to some authority and thus the identification tokens $A$ can only be computed by this party. Consequently, having this redundancy scheme (shadowed identities) and limiting the knowledge of the private key $1/\mu$ and the factorization of $N$ to some authority, $\mu$ and $N$ can be system parameters for many users.

The value $\mu$ can be chosen to be any value that is co-prime to $\phi(N)$ and for instance fixed to the prime $2^{16}+1$ as it is common in the RSA setting.

Last part of the question

You write

  Also there is a step $t=r.B^d\ mod\ n$. This means $(r.B^d)\ mod\ n$
  or $r.(B^d\ mod\ n)$?

It means $(r\cdot B^d)\ mod\ n$ and this is equivalent to $(r\cdot (B^d mod\ n))\ mod\ n$.

Final remark

Finally, I would like to suggest to read about the GQ identification scheme in another source such as chapter 10 of the freely available Handbook of Applied Cryptography, since the description is much easier accessible than in the original paper.


Can any MAC be used as a KDF? First, let me clarify what I mean with a Key Derivation Function (KDF). I'm interested in KDFs that take an $n$-bit symmetric master key and some diversification data of arbitrary length as input and produce an $n$-bit symmetric key as output that can be used in subsequent cryptographic operations.

It seems to me that such KDFs have much in common with MACs:

A key and data as input and an output that has the same length as the input key;
The output should be unforgeable for an attacker who does not have access to the input key;
The probability of producing equal outputs for unequal inputs should be negligible.

Hence my question: is it secure to use any secure MAC algorithm as a KDF?

No. A MAC guarantees unforgeability but not pseudorandomness. It is true that all MACs that I can think of right now are essential pseudorandom functions, but this does not mean that the MAC definition implies this. Indeed, it clearly does not.

So, conceptually, you need a pseudorandom function. You can assume that HMAC is a pseudorandom function. It is proven that CBC-MAC on prefix-free inputs behaves like a pseudorandom function. But this doesn't mean that it's always the case.


Can I apply "encrypt with public key and decrypt with private key concept" using ECC certificate? If Alice wants to send encrypted message to Bob, she can use Bob's public key to encrypt the plain message. Once Bob reliably gets encrypted message, he can decrypt it with his private key. In this process, Bob will never have to know anything about Alice (assuming message is not tampered). In other words, Alice does not need her own public/private key pair. Further this process can be easily achieved by Bob's RSA certificate and Alice does not have to have any RSA certificate. I also understand that this is following asymmetric algorithm (i.e. using PKI).

How does this encryption and decryption process change if Bob has ECC certificate only?

I have reviewed Integrated Encryption Scheme (https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme). As far as I can tell, both DLIES and ECIES seem to suggest deriving a key (using key agreement protocol), then encrypt and decrypt messages using that key, which is essentially a symmetric algorithm.

Does not this mean both Alice and Bob need each other's ECC public key?
If so, this process appears to differ when RSA certificate is used. Am I correct?
Does this mean Alice now needs her own ECC certificate because she needs to send her public key to Bob along with encrypted message so that Bob can successfully decrypt it using Alice's public key and his private key?

You are right that (EC)IES essentially consists of a Diffie-Hellman key agreement and authenticated symmetric encryption, but the protocol flow is different. In particular, IES is a "one-shot" public-key encryption scheme: Assuming that Alice knows Bob's public key beforehand, she can encrypt a message for Bob "offline" without any interaction, just like with RSA.

In summary, ECIES consists of the following steps:

Assume Alice knows Bob's public key $Y=[y]P$.
Alice generates a random private key $x$ and computes $[x]Y$.
She derives a symmetric key $k$ from $[x]Y$.
Using some authenticated symmetric encryption algorithm, she encrypts her message using $k$ as the key, yielding a ciphertext $c$.
She transmits the pair $([x]P,c)$ to Bob.

Based on this, we can answer your questions:

1.
No, in IES the receiver (Bob) does not need Alice's long-term public key because she generates a fresh ephemeral key pair (whose public part is transmitted as part of the ciphertext) for each message. In fact, Alice does not even need to have a long-term key to be able to encrypt messages for Bob! This is in line with the general public key encryption setting: Everybody can encrypt, only Bob can decrypt.

2.: Yes, the encryption procedure for RSA is different from IES. But the protocol flow is not! Both are public-key encryption schemes.

3. No, according to 1.


Is one-time pad encryption vulnerable when near identical data is sent many times with different OTP? Let's assume a text file that grows at its very end but is otherwise not edited. We now have 100 transmissions of this, but OTP-encrypted (different OTP each time, of course). The first 50% of the original file are identical.

Of course nothing can be said about the other 50%. But can parts of the first 50%, which stay perfectly identical, be attacked?

(Please be light on the lingo and math, I'm a noob.)

Different scenario, same question: The text is edited in various places, but only individual sentences. This shifts the bytes around, but apart from that, most of it stays perfectly identical.

No. As long as each pad is completely random and independent, you can encrypt literally anything of the appropriate size (no larger than the pad) and retain information theoretic secure confidentiality. This attack is termed a known-plaintext attack, or KPA. The OTP encryption scheme is only vulnerable to this if you re-use padding material, which breaks the scheme. A proper OTP is not vulnerable to KPA.


Is my AES-128-CTR implementation secure enough to encrypt private keys and mnemonic seed? I am building a cryptocurrency wallet online where everything is stored in the browser (No servers).

At this moment I am storing all private keys encrypted using AES-128-CTR I've chosen this method because is the standard for Ethereum keystore file format.

Is this algorithm secure to encrypt any other private key such Bitcoin (which is not hexadecimal)?

Would it be also secure to encrypt 12 words mnemonic or any other string?

Here is my implementation:
https://github.com/elevenyellow/coinfy/blob/master/miscellaneous/experiments/aes-ctr-128.js

Edit:
@SAI Peregrinus says on his response that my implementation is completely insecure which make me think, is the same for myetherwallet.com? Because my code is just a refactor of this:
https://github.com/kvhnuke/etherwallet/blob/44074daeef3f98ca15410158b5a5403ac734a08a/app/scripts/myetherwallet.js#L196

Edit2:
Studiying the geth (Ethereum go) client implementation I don't see any difference except for the parameter kdf.n where their value is 262144
and mine is 1024:

https://github.com/ethereum/go-ethereum/blob/bedf6f40aff0dd14bfab533a37c329ddc9a4bdd5/accounts/keystore/keystore_passphrase.go#L118

This is not secure at all. It's technically off-topic since it's a coding question, but this implementation contains many basic errors. One example is using an insecure random number generator, which utterly destroys the security of the encryption. Another is using AES-128-CTR without authentication.  Do not try to implement your own cryptographic primitives, it takes a ton of work and is prone to obscure errors causing total failure. Use an existing library that provides constructions based on secure primitives that do what you need. That pretty much means libsodium, libhydrogen, tweetnacl-js, or a similar library.

If you use libsodium there's a version compiled to JS: https://github.com/jedisct1/libsodium.js

Documentation here: https://download.libsodium.org/doc/

You're looking for the authenticated encryption functions (crypto_secretbox_easy and its helpers).

Libsodium can encrypt whatever you want. Also the bitcoin private keys are just bitstrings, just like the Ethereum private keys. They can be represented in hexadecimal just as easily as any other encoding.


Can I use any number as an ECC key? I've been looking into elliptic curve cryptography, and have been trying to understand how I can and can't use it. Note that this is a hobby project and I am not making my own crypto systems for anything serious.

I am attempting to create an elliptic curve key pair that is dependent on outputs from other cryptographic functions. As far as I understand it, an key in ECC is based on a single point on the curve, as opposed to RSA which uses a pair of primes.

Does this mean that I can use random bits (or hash outputs) of the correct length as the private key of a curve such as Curve25519?

I've struggled to find information on this topic, but I do know that the soon-to-be released system SQRL (https://www.grc.com/sqrl/crypto.htm, "SQRL's underlying crypto technology") mentions using such a system. If I haven't understood it right, how is this working?

You have to specify a particular cryptosystem for a particular answer.  Generally, in an elliptic-curve-based cryptosystem, a secret key involves a scalar, which is an integer within the range of the number of points in a group on the curve, possibly subject to some constraints, and chosen uniformly at random from all possibilities.  It's OK if you get that by hashing a secret of sufficient entropy, and shoehorning it into the right range.

In the Diffie–Hellman function X25519, a secret key is traditionally an arbitrary string of 256 bits, with some bits masked so that the Curve25519 scalar is a uniform random choice of a multiple of 8 between $2^{254}$ and $2^{255}$ for a couple of reasons: [1], [2].

In the signature scheme Ed25519, there are a few different forms of secret key for different applications and performance constraints.  For compatibility reasons, the same masking is often done on the bits that get interpreted as an edwards25519 scalar, though there are other issues too in more exotic applications.

In ECDH and ECDSA over prime-order curve groups such as NIST P-256 or secp256k1, a secret key is usually the canonical encoding of any positive integer below the order of the group which is necessarily also the order of the standard base point.  Mostly ECDSA is done over curve groups with prime order and no concern for twist security (e.g., the largest prime factor of the order of the quadratic twist in NIST P-224 has only 118 bits, well within the realm of ECDLP feasibility), unlike X25519 and Ed25519 which work in a curve group of cofactor 8 whose quadratic twist has cofactor 4.


What does "running in polynomial time" really mean? I'm currently learning private-key cryptography. I've been able to see that perfect secrecy is achievable if no assumption is made about the computational power of the attacker.

However, perfect secrecy is quite heavy to use, so we relax our assumptions to achieve the so-called computational secrecy, by assuming that the computational power of the adversary is bounded.

Then they speak about "efficient adversaries". They are defined as "running in polynomial time". I'm sorry, I know what asymptotic time-complexity is, but here I have no idea of what it means.

I'm confused because there seem to be a restriction. Security is said to be preserved only against efficient adversaries, that run in a feasible amount of time. In other words, they seem to say that polynomial time is a limitation on the adversary, and I don't understand that because to me it is the best complexity that can be achieved by an algorithm. If we are protected against polynomial adversaries, shouldn't we be protected against ALL adversaries ?

So maybe I'm missing something... Can someone explain what an efficient adversary really is ?

Perfect secrecy is achievable in a few cases, such as one-time pads, and, well, that's pretty much it. Most cryptographic protocols are vulnerable to an all-powerful, all-knowing attacker. If you do not put any restriction on what the attacker can do, then

Guess the key.
Profit.

breaks almost any cryptography, as does

Wave a magic wand.
Profit.

So at the very least we must restrict our model attackers who can do things we haven't even imagined. Cryptography also doesn't aim to protect against lead pipe cryptanalysis. So we assume that attackers are only allowed to do things “inside the system”. Based on Turing's thesis, we assume that the attacker can only compute computable functions, and that the function computed by the attacker does not depend on the key. (It's ok if the attacker can make random choices too, as long as their probability isn't influenced by the key.)

Even a deterministic attacker who does not know the key can still break most cryptographic protocols with enough effort. All he has to do after all is enumerate all possible keys. But for sufficiently large key sizes, this should be unrealistic: as a rule we aren't interested in attacks that would take more than the lifetime of the universe.

If you want to analyse the resistance of an algorithm very precisely, you would need to know exactly how powerful the attacker's computer is, and study all possible ways in which he can make the computation required by the attack to find which one is the fastest (or more generally the cheapest). This is impractical. To start with, we look at the asymptotic behavior of the attacks: the way the attacks become harder as the parameters (such as key size) become larger.

In computational complexity, there is a nice break between polynomial and super-polynomial algorithms. This break fits cryptography well. The usual methods of doing realistic stuff tend to be polynomial, whereas enumerating all keys is exponential in the size of the key (or more precisely in the strength of the key). So restricting to polynomial attackers combines two nice properties:

It is good for getting theoretical results.
It does a good job of including realistic attackers and excluding unrealistic ones.


Is SHA 2 suitable for key derivation? Let's imagine that I've got a number modulo n given by DH protocol. I want to use it as a key for  AES encryption. So I have to cut this number to fit it in AES (128,192 or 256 bits). I can use hash functions to achieve that, but what hash function is suitable for key deriviation? Can I use SHA2?

In principle raw SHA2 is suitable for deriving an AES key from a DH shared secret.

But the "proper" solution is to use a KDF. My preferred choice is HKDF, which can use SHA256 as the underlying hash function. It allows you to derive several named key and keys longer than 256 bits from a single secret.


Space needed to store an RSA private key How much space is actually needed to store a $4096$-bit RSA private key? I originally assumed $0.512$ kB since $\frac{4096}{8} = 512$, but then I started to wonder whether it was in hex.

Simply, what's the size of a $4096$-bit private key, and how does it compare to the public key?

What's the size of a 4096 bit private key?

It depends.

The range goes from 512 bytes (only $d$, no formatting, no encoding) up to 5632 (full parameter set, maximal $e$ size, no formatting, hexadecimal encoding) bytes for two-prime RSA. If you also consider multi-prime RSA, the range is much wider.

So what influences the size of the stored private key then?

How do you encode the stored data?

No encoding, this will give no increase in storage need
Base64 encoding, this encodes 3 bytes of data into 4 bytes of encoded data
Hexadecimal encoding, this will encode 1 byte of data into 2 bytes of encoded data

How do yo format your data?

No formatting, this also means no overhead
ASN.1, this will give some overhead to make the structures parseable and the overhead will increase if you use XER instead of DER, the relevant standard is PKCS#1 (PDF) here as well as PKCS#8 for containers and PKCS#12 (PDF via Archive.org) as additional wrapper.
PEM, this will give you some overhead for internal structure and the header and footer of the data block

How much data are you storing?

The absolute minimum $p$, which will allow you to factor $n$ using simple division and will allow you to later derive $d$ "the usual way". This approach provides optimal storage requriments, assuming you're not willing to run the algorithms from 3. which would reduce the need for stored bits of $p$.
Only the private exponent $d$, which will give you a good storage characteristic, but also requires external supply of the public modulus $n$ and the public exponent $e$ for proper operation
A complete minimalistic approach $(n,p',e)$, this will require you to store $e$, but you can optimize it by hard-coding it as $F_4$. The technique is to store only a minimalistic amount of information of $p$, but enough to recover $p,q$ as per "On Factoring Arbitrary Integers with Known Bits" by Herrman and May (PDF) and "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities" by Coppersmith (PDF) . This reduces the storage requirement to 5120 bits, however I do no recommend this as it is highly non-standard and will give you large interoperability problems for a marginal storage saving.
The smallest (trivial) complete set $(p,q,e)$ which will allow you to recover $n$ using standard multiplication and will allow you to recover $d$ the usual way.
A middle-ground minimum $(n,d)$, this will not allow you to factor $n$ without external supply of $e$ (which may be an agreed-upon constant), but is enough to decrypt messages "classically"
Only the bare minimum $(n,e,d)$, this will allow you factor $n$ somewhat quickly if needed and it will allow you to do all operations without external data supply
A middle ground amount of data $(n,e,d,p,q)$, this will take away the "heavy" step of factoring $n$ but still leaves some computations to be done if you want that speed-up from the CRT.
The full set $(n,e,d,p,q,d_p,d_q,q_{\text{inv}})$, this allows you to load the data and outright start with the computations, including the CRT speed-up

  How does it compare to the public key?

Look at the above list of influencial factors and adapt the third major point, a public key "only" has the option $(n,e)$ there, meaning it can be larger than the private key or it can be significantly smaller, if you include the associated data in the private key.


Clarification of one-way property of hash functions One-way property: computationally infeasible to find data mapping to
  specific hash

The definition above is a little vague, if we have h(x) = floor(log(x)), finding "some" x that gives a hash value is easy, however, deterministically finding the actual x value that has led to the output is impossible. Do such hash functions have the one-way property?

Your function is too easy. Given an hash value $h$, calculate $b^h$ and $b^{h+1}-1$, where b is the base of your logarithm.

Any value between $b^h$ and $b^{h+1}-1$ will be pre-image.


Are there drawbacks to encrypting data locally before being encrypted in cloud backup (multiple encryption)? I am planning on backing up my hard drive using a cloud backup service but have become skeptical of the industry based on incidents like these:

http://dbmsmusings.blogspot.com/2011/02/why-i-no-longer-trust-emc.html
https://security.stackexchange.com/questions/7142/online-backup-how-could-encryption-and-de-duplication-be-compatible

And this response to the question of losing one's private key by Altdrive:

"What if I lost my file encryption key?

We don't want to hear that! Your private encryption key is VERY important and personal. Without it, you cannot restore your data in event of a system loss. We highly recommend that when you create your encryption key, you store it in a safe place: e.g. printed out and in a safe deposit box, or backed up somewhere else on the Internet.
If you did, contact us immediately. There may be a few options depending on the circumstances."

Based on lack of trust of these providers, I am planning on encrypting my hard drive using EncFS on an external hard drive and then using Altdrive (the cheapest backup cloud service) to back up that external hard drive, so that regardless of whether I use Altdrive's user-defined private key or their own key, stored on their server, it should not be possible for them to access any of my data.

What are the risks to consider in this approach, eg is there more a chance of corrupting my data since it will be encrypted multiple times, will it be harder to access or obtain individual files, ie maybe I have to download the entire volume since I shouldn't be able to recognize each file on their server (not sure how it works to obtain data from cloud backup providers in general)?

I am using linux.

Apart from the performance hit of encrypting / decrypting twice, and the inconvenience of having two keys to not lose, this should work fine. In fact I wish more people had your approach to data privacy and encrypted things before sending them over the internet!

About Altdrive in particular, a good question to ask yourself about their upload service / upload webpage is: is the data being encrypted on your computer and then uploaded, or uploaded and then encrypted? If their uploader encrypts on your end with a key you never give them, then double-encryption probably isn't adding anything, but if it's sent to them in the clear, then your EncFS idea is good. A good test would be to upload a secret.txt file, then log in to the site from a different computer that doesn't have the encryption key and see if you can download and decrypt the file. If you're not able to decrypt it, then their service is probably trustworthy.

That bit from Altdrive about losing your key is a standard warning in the encryption world: backing up your key protects you from losing it, but means there are more copies of your key for someone to steal. You have to decide which you're more worried about: losing your key, or having it stolen? I can tell you that there are many large corporations and governments who back up decryption keys, and many who don't. You have to decide for yourself.

I've never used EncFS, but from a quick google it looks like it encrypts each file individually, so you should be able to pull down files one-at-a-time rather than having to download the whole block. BUT it looks like it encrypts the filenames by default, so you'll have no idea which file you're grabbing. Does EncFS have a setting to turn off filename encryption?

Again, from a quick google of EncFS:

  Files are encrypted using a volume key, which is stored encrypted in the source directory. A password is used to decrypt this key. wikipedia

You probably want to not upload that volume key file since that would mean that cracking your password gives an attacker your decryption key (and it's ALWAYS easier to crack a password than a full key).


Is there a practical security difference between OTP with letters and OTP with numbers? Is there a practical security difference between “OTP with letters” and “OTP with numbers”?

If, for example, I encrypt a letter message using Tabula Recta with a random letter key, I would get:

THISI SATES TXAAA - message
MOSSK VFXNN EJRQW - OTP key
FVAKS NFQRF XGRQW - cipher

Would such encryption be less secure when it comes to frequency analysis, compared to (let's say) Dirk Rijmenant's CT-46 OTP where the most frequent letters (AEINOR) are associated with a single digit instead of two digits, like the rest of the less frequent letters in the alphabet?

Example:

THISI SATES TXAAA
83753 82390 82183 28290 83871 11000 - message
08733 64840 36236 58407 58482 94160 - OTP key
85020 28550 56957 70893 35499 27940 - cipher

There is no security difference. Of course, purely random characters with entropy rate $\log M$ where $M$ is the size of the alphabet should be independently generated and used for the OTP, whatever the size $M$ of the alphabet.


How are precision and security related in a Gaussian Noise Sampler for R-LWE? My understanding is that the sampling precision in Gaussian Noise sampler is related to security. But not sure about why is that? I read that when the samples are floating-point numbers and precision after the decimal point is equivalent to 72 bits that can be correlated to 128-bit security.

However, certain schemes use 32 bits precision, so how does that impact the security? And what is a good number to select for the precision value? Also, if the samples are integer values then how to deal with precision and security?

The discrete Gaussian distruibution have the most entropy at the same standard deviation compared to other discrete probability distributions. It's important in some LWE/SIS digital signature algorithms because it helps reduces the signature size (most notably in BLISS and FALCON), but otherwise not so essential in key exchange or encryption (and has been replaced with binomial distribution in NewHope).

The reason using Gaussian distribution reduces the signature size, is because it allows certain entries in the signature to be represented with shorter codewords using e.g. Huffman coding. But doing it right can be difficult, as slightest observable difference from true discrete Gaussian distribution can lead to leak of private key information.

Take a Fiat-Shamir signature scheme as an example, the signature $z$ is calculated as:

$$u=Ay$$

$$c = H(u,m)$$

$$z = y+sc$$

Where $A$ is a component of the public key, $m$ is the message, $s$ is a private key component, and $c$ is the output of hash function and $y$ is randomly generated according to discreate Gaussian distribution.

We want $z$ also be in discrete Gaussian distribution, becuase

since we've added $sc$ to bind the private key to the signature, and
$c$ is a public component,

we have to hide the private component with $y$. And here, in order to achieve the expected distribution, rejection sampling is used.

See also: How would low-precision Gaussian sampling impact the security of BLISS?


Webapp password storage: Salting a hash vs multiple hashes? For security's sake, of course it's blasphemous to store passwords in plain-text; using a hash function and then doing a re-hash and comparison is considered much better.

But, if bad guys steal your database, they still could brute-force against the hash and conceivably retrieve many passwords.

The question I have is: Is salting a hash as effective for the effort as say, combining multiple encryption methods with a signifier?

For the sake of example, let's say MD5 = 1, DES = 2, and AES = 3. During the first time the password is stored, why not generate a random sequence of these numbers (i.e. "231"). Then, hash the password in that order (e.g. for "231", DES, then AES, then MD5) and add the digits to the front of the hash. Then, comparison does all three hashes in a random way, by taking the first three digits to see how it should be compared.

I know this is more computationally expensive than adding a salt before hashing, but given the random algorithm assignments plus the task of brute forcing (and taking into account that the attacker would have to have source-code access to see your enum of what numbers are what, etc.), would it be more effective?

Short summary: Don't do it, use an established password hash function like bcrypt, scrypt or PBKDF2.

Long form:

What you are doing here in effect is this:

Create a combined hash algorithm out of several different hash algorithms (or block ciphers made into hash functions).
Use a salt input to the combined algorithm to decide which of these algorithms to call in which order.
Store the salt and the resulting hash.

There are three ideas hidden here: A salt, repeated hashing, and use of different hash functions.

The reason to use a salt for password storage (or any usage of a password, really) is to avoid that the attacker can simply use a rainbow table - or, in fact, to make the needed rainbow table that many times bigger. As an example, if you have tree algorithms which will all be used, in a random order, you in effect have 6 possibilities (123, 132, 213, 231, 312, 321), which means a rainbow table has to be six times bigger.

At the same time, the hash execution time will be three times longer, so generating the rainbow table takes in effect 18 times the original time.

To make a rainbow table attack totally ineffective, you use a salt that big that it is not practical anymore to use a rainbow table (since it would need to long to generate and too much space to store). The Bcrypt algorithm, for example, takes an 128 bit salt input. A rainbow table for just a single password and all possible salts would take $2^{128}$ entries.

A salt alone still does not help against a brute force attack - you can check all realistic passwords in a dictionary for MD5(salt | password) == hash just as fast as MD5(password) == hash.

Here your second idea comes in: Repeated hashing. In your example, you use three hash invocations for each password - this means brute-forcing a single password takes three times the time as brute-forcing it with a single hash function. Three times is not much.

Instead, use a lot larger number of hashes. There are specialized slow hash functions around (like bcrypt), which have a configurable work factor build in - e.g. they take beside the hash and password input a work factor parameter, which says how often is should loop. You then can simply scale this with the hardware progress so your user does not have to wait too long for login, but an attacker still needs very long to crack the password.

Other schemes (like PBKDF2) use a fast hash function (like MD5, SHA-1, SHA-2) a large number of times (something like Hash(password, hash(password, hash(password, ...(password, hash(password, salt))...)))).

Your third idea is using a different hash algorithm depending on the salt.
Using a different salt as input to a hash function has a similar effect to using a different hash function, but is much simpler to implement. Using different algorithms makes your combined algorithm harder to analyze (i.e. harder to guess about its security), and also harder to implement. Also, you are depending on the security of multiple algorithms.

I could think about using different algorithms to secure against cryptanalytic breakthroughs in any of them, but then you should always use all of them, and there is no reason to randomize which algorithm to use.

So, don't do this, use instead an established password hash function like bcrypt, scrypt or PBKDF with an appropriate work factor. (These all include the use of salt.)


Question about key verification I am studying for network security exam. And in the slide about Key Management, under a heading Key Verification I see this:

Key Verification

Almost all cryptographic algorithms have some weak keys that should
not be used.
With the help of key verification procedures, these keys can be
regenerated if they occur.

This doesn't make sense to me, how some particular key in algorithm might be weaker then any other key? Does key verification mean something else? And lets just for the moment imagine that some are weaker, then why would they be generated in the first place?

There are many types of weak keys, some of them make it vulnerable to chosen plaintext attack, some of them may leak some statistical properties through the plaintext, some keys generate same subkeys for multiple rounds of an algorithm etc. See https://en.wikipedia.org/wiki/Weak_key .

Keys are usualy generated randomly. The randomness is tightly connected with unpredicability, which is of course very desired property of key generation. It would be probably rather hard (and error-prone) to skip all the weak keys. (The hardness, however, depends on the algorithm.) Just identifying the weak keys and restarting the key generation is probably much simpler. Since there are usually few weak keys, it is usually rare to generate one and probability of repeated random choosing a weak key is negligible, so it is very improbable to get stuck for a long time in a loop because of weak keys.


Diffusion in Stream Cipher The diffusion property of a cipher defined by Shannon refers to the ability of a cipher to cause a lot off bits in the cipher text to be modified, when even a single bit in the plaintext is flips.

However, in stream ciphers – when the cipher text is the xor of the plaintext with the key pattern – a flip in the plaintext will always cause exactly one bit modification in the cipher text.

Does this mean that stream ciphers have a low level of diffusion?

Stream ciphers in general are more efficient but less secure than a block cipher, provided all else being equal in terms of each construction following both necessary and preferred principles (Katz & Lindell, 2009; Boneh, 2013).

Shannon's “confusion and diffusion” refers to good confusion and diffusion of message block bits and secrecy bits based upon linear and non-linear functions as you mostly point out.

There are different kinds of stream ciphers as there are different block ciphers. Some stream ciphers did not pass two or more critical statistical tests to show powerful diffusion.

In general you are correct: stream ciphers either have low or even slow diffusion rates. However, linear masking and improve initialization processes helps reduce vulnerability to linear and side attacks. Stream cipher Hc-256 is a good candidate to test further.

Stream ciphers are faster than block ciphers, but block ciphers with proper construction have higher diffusion – still, pseudo-randomness can be generated from a block cipher to stream ciphers to reduce attack vulnerabilities.

Additional reading:

http://publications.drdo.gov.in/ojs/index.php/dsj/article/view/1435/4669
http://www3.ntu.edu.sg/home/wuhj/research/publications/wuhongjun_thesis.pdf

Same author as thesis but shorter and more straightforward:

http://www3.ntu.edu.sg/home/wuhj/research/hc/hc256_fse.pdf


Unsure of syntax used in Searchable Encryption This image is taken from Algorithm 1 from "Σoφoς – Forward Secure Searchable Encryption, CCS '16".

On line 4 there seems to be a new variable, M, that is never defined throughout the rest of the paper. Should I attain a random byte[] and set that as the value of ST_0?

This is being implemented on a Java programme.

$\mathcal{M}$ is the domain of the inverse trapdoor permutation $\pi^{-1}$. For example, if $\pi^{-1}(m)= m^d \bmod N$ implemented using RSA, then $\mathcal{M}=Z^*_N$. The domain/range of $\pi$ and $\pi^{-1}$ are all $\mathcal{M}=Z^*_N$.

Generate a random big integer in $Z^*_N$ (roughly from range 1 to $N$) should be fine (there is a negligible probability of getting something not in $Z^*_N$, but since it is negligible we don't care).


El Gamal signature scheme variant Suppose we have the following El Gamal digital signature scheme variant: We fix a prime number $p$ and a generator $g$ of the group $Z_p^*$. We choose $x \in Z_{p-1}^*$, which is going to be our secret key and we compute $y = g^x \pmod{p}$, which is going to be our public key. For the signing algorithm, we choose a random varue $k \in Z_p^*$, then compute $$r = g^k \pmod{p}$$
 $$s = (m-kr)*x^{-1} \pmod{p-1}$$
and output $(r,s)$.

In order to verify the signature, it's easy to see that the following should hold:
                       $$y^sr^r \equiv g^m \pmod{p}$$
Now, as far as i can tell, the signing algorithm is faster than the one in the original El Gamal scheme, as we compute the inverse of $x$ once and forever, while in the initial scheme we have to compute the inverse of the new random $k$ every time we want to sign a message.

However, what about security? Can we say that the new scheme provides the same security as the initial one or it can be beaten in some way?

First, you should not use $p-1$ as modulus. Instead , use a big prime factor $q$ of $p-1$, as it is done in the DSA algorithm.

The DSA variant  you describe exists as an elliptic curve version. It is called EC-GDSA ( Elliptic Curve German Digital Signature Algorithm) . It is described here: https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TR03111/BSI-TR-03111_pdf.pdf?__blob=publicationFile