Encryption of numeric value using playfair I am studying in CSE and in my recent exam paper, A question was asked as:

Construct a playfair cipher for Plaintext: semester5 and key:technology.

Generally as we are taught yet, there is no example of playfair matrix substitution for numeric value.

So, what to do with number 5? Is there any trick for this kind of encryption?

use letters to represent digits

"a captured German revealed under interrogation that Enigma operators had been instructed to encode numbers by spelling them out ...  Alan Turing reviewed decrypted messages and determined that the number "eins" ("one") was the most common string in the plaintext."
-- Wikipedia: known-plaintext_attack

"The Enigma machine didn't encode spaces (nor punctuation characters), so either leave out the spaces in your message or replace them with X's. ... If you wish to encode numbers in your message, you must spell them out."
-- Madlab: Enigma

"The German Army, Air Force and Police used the Double Playfair system as a medium-grade cipher in WWII, ... numbers were spelled out. As the German numbers 1 (eins) to twelve (zwölf) contain all but eight of the letters in the Double Playfair squares, pro forma traffic was relatively easy to break"
-- Wikipedia: Playfair cipher

"each digit was represented by 2 letters"
-- "Enigma Uhr"

use some other cipher that can handle letters and digits directly

"... we proposed a 6 X 6 Playfair cipher ... 6 X 6
Playfair cipher supports all 26 alphabets (A-Z) and 10 digits (0-
9)"
-- "6 X 6 Playfair Cipher using LFSR"

"This extended play fair algorithm is based on the use of a 6 X 6
matrix of letters ... and digits..."
-- "An Extension to Traditional Playfair Cryptographic Method"


Meet in the middle attack: Why would it be easier to get elements of one of the 2 sets? This is from Bruce Schneier's Book Cryptography Engineering. In his description of Meet-in-the-Middle attack, he writes (Chap 2, Page 35)

A meet-in-the-middle attack is more flexible than a birthday attack. Let’s
look at it in a more abstract way. Suppose we have N possible values. The
first set has P elements, the second has Q elements. There are PQ pairs of
elements, and each pair has a chance of 1/N of matching. We expect a collision
as soon as PQ/N is close to 1. The most efficient choice is P ≈ Q ≈ √N. This
is exactly the birthday bound again. The meet-in-the-middle attack provides
extra flexibility. Sometimes it is easier to get elements for one of the sets than it
is to get elements for the other set.

I don't understand the last line - why would it be easier to get elements for one of the sets? One of the sets is the set of transactions which you are snooping & the other set is the set of keys for which you have pre-computed the encrypted message for a header you expect at the start of the transaction. If this is right, then why would it be easier to get elements for one of the sets?

In many cases you are memory bound and you can't keep everything you compute in memory. So you can compute as much as fits in memory to get group A and then compute without storing in memory a potentially much larger group B. Checking for a collision is done efficiently because one group is in a hashset you have stored.
The memory limit could be RAM limit so lookup is very fast but it could also be disk limit, you really can not store more data.


PKCS RSA - Why do we need encoding In the RSASSA-PKCS-v1_5 signature scheme, the first step is to perform an encoding on the hashed data. (0x00||0x01||PS||0x00||T).
Is this encoding important for security ? What happens if the hash is directly encrypted without encoding ?

As per section 9 of the paper, the encoding used is required for the security of the scheme.

The encoding operation may introduce some randomness, so that
different applications of the encoding operation to the same message
will produce different encoded messages, which has benefits for
provable security.  For such an encoding method, both an encoding and
a verification operation are needed unless the verifier can reproduce
the randomness (e.g., by obtaining the salt value from the signer).
For a deterministic encoding method only an encoding operation is
needed.

Two encoding methods for signatures with appendix are employed in the
signature schemes and are specified here: EMSA-PSS and EMSA-PKCS1-
v1_5.

The paper then goes into further detail on these two encoding methods.
You would be compromising the security proof of the scheme if you did not use the encoding, however you could feasibly apply the encoding after hashing the message.  Per the paper:

Without compromising the security proof for RSASSA-PSS, one may
perform steps 1 and 2 of EMSA-PSS-ENCODE and EMSA-PSS-VERIFY (the
application of the hash function to the message) outside the
module that computes the rest of the signature operation, so that
mHash rather than the message M itself is input to the module.  In
other words, the security proof for RSASSA-PSS still holds even if
an opponent can control the value of mHash.

The fabulous answer here goes into detail regarding one attack the encoding prevents, and provides links to other attacks on wide deterministic RSA signature signature schemes.
Section 2 of the original paper by Bellare & Rogaway outlines several advantages of the encoding scheme.


Generating two secret keys from a physical analog signal: Crypto HASH analogous to time varying signal Can we generate two secret keys from same source?

The idea is we have time varying signal. We capture a window of say few milliseconds,$t$. I can chop values of signals at a rate $N_S$ and get $tN_S/1000$ samples. I put a threshold and assign 0 and 1 to values below and above it.
Since this signal is shared I get a secret key of length $tN_S/1000$ bits.

Now the length of key depends on $N_S$ for a given window. We do agree that it gets harder to track original data if I decrease this $N_S$.

My problem is can I generate two different secret keys using this time varying signal. Approach can be to to use different functions say: digitization and derivatives. I can encode derivative to some bits.

These two functions can give two separate sequences. Now issue is I cannot say I have got additional level of security because: Signal can be compromised and that will compromise both functions results. This is what happens in general cyrpoto key management.
Another point is I can use first method(thresholding) to generate back signal and guess output of second sequence hence its useless to generate that sequence!

My point is viability of back generation of signal depends on sampling rate.If its high the second sequence can be broken. But if sampling is low enough then back generation will be erratic hence second sequence cannot be guessed correctly.

I feel sampling can be optimized and keys generated through one process is not able to capture the full prowess of source and I can generate more keys from the signal which is still secure be it of a small length.

Is there any method already studied in literature of generating two secrets from a signal?

Hash is one practice that is effective in key management but the security level is decided by parent key no matter how many hashed keys we generate ahead. But if we generate two keys from a physical signal(assuming this signal is shared and random enough and cannot be guessed by eavesdropper) can the security level of system be increased?

If not are there analogous to hash functions on such time series signals?
If not one way functions how can we compare feasibility of choosing two such functions? Is cross correlation a good choice?

There seem to be multiple problems you try and solve at once. Lets split the problem in at least two sub-problems:

First of all you want to have to extract entropy;
Then you want to create two keys using the entropy or random number generator.

Extracting the entropy

Extracting the entropy from the source involves whitening techniques. In case the amount of entropy is low you may want to use this entropy as input to a DRBG (deterministic random bit generator).

You may also want to include other entropy sources or identifiers, anything that may add randomness if you're using a DRBG.

Lets call the resulting bit string with $K_{master}$. $K_{master}$ does not have to be formatted as a key, it's just a bunch of bits that together hold a minimum amount of entropy.

Creating two separate keys

OK, so now you need two separate keys that are independent on each other. This is easier then you may think; you can simply use a KBKDF such as HKDF, which is based on a hash function: $K_1 = \operatorname{KBKDF}(K_{master}, \text{"1"}, l)$ and $K_2 = \operatorname{KBKDF}(K_{master}, \text{"2"}, l)$ (where $l$ is the amount of bits required for $K_1$ and $K_2$.

HKDF first explicitly extracts ("compresses") the entropy in the key to a fixed size output that depends on the hash algorithm used. It then expands this extracted information into enough key material for $K_1$ and $K_2$. Of course the strength is limited by the entropy in the input key material and the used hash function (however SHA-256 or higher should be enough for any normal usage).

You could include a device specific secret into the IKM by appending or prefixing it to the $K_{master}$ that you got from whitening your entropy source.

Most importantly, revealing either $K_1$ or $K_2$ to an attacker won't give the attacker any information on the other key or the input keying material (given it has enough entropy not to be brute forced).

This way you can focus on the best way to get entropy from your source. Try not to create any data that depend on other data as you seem to suggest.


Why does consecutive permutations or consecutive substitutions not enhance security? My professor stated that permutations which are done repeatedly does not further enhance security than just one permutation. He also stated that fact this applies to consecutive substitutions as well. Algorithms such as AES which intertwine permutation and substitution in each round does in fact increase security. I understand this is because if they are intertwined, then the substitution effect will be diffused by the following permutation. However, if he were to ask this question in a test: why does repeated permutations or substitutions not enhance security? I won't be able to think of a good answer.

The reason two permutations in a row don't increase security is that there is always a third permutation that's equivalent to performing the two permutations in a row. For instance, suppose we have 5 elements, and the following two permutations:
$$\begin{align}
\sigma_1 &: 12345\to34251 \\
\sigma_2 &: 12345\to43512
\end{align}$$

Then if we apply $\sigma_1$ followed by $\sigma_2$, we send $1$ to $5$ by $\sigma_1$ and then to $3$ by $\sigma_2$; if we work out all of the 5 elements, we get
$$\sigma_2\circ\sigma_1 :12345\to52134$$

This is just another permutation (using more common cycle notation, $\sigma_1=(13245)$, and $\sigma_2=(14)(235)$, so $\sigma_2\circ\sigma_1 =(1543)(2)$). As you can see, composing the two permutations just popped out a third permutation; from an attacker's point of view, the fact that we did two permutations is irrelevant, because he can treat it as just one permutation.

With substitutions, it's similar: composing two substitutions gives a third (single) substitution, so there's no difference from an attackers point of view.


Is quantum randomness different to conventional randomness? I've been reading a question regarding the uses of quantum computing.  There is a broad theme throughout the answers that seems to suggest that randomness generated via quantum means is somehow better than randomness generated via traditional means.  I get the impression from some of those answers that the massive processing potential of quantum computers can somehow derandomise traditionally generated randomness.

A quantum computer would use quantum gates.  They would be operating via entanglement and superposition to produce random states. A classical physics based random number generator using say a humble diode, would use chaos theory to produce entropy+.  Both constructions would in their gross outputs generate large biases which would be whitened via additional hardware /software. So both techniques converge onto a conventional randomness extractor.  Both techniques would also be massively affected by electrical system noise which might be ~50% of the total raw entropy in the quantum case as in this 2 Gb/s beam splitter.  Electrical noise is generated mainly by classical physics.

Ultimately, a quantum random number generator outputs a sequence of bits that might be "1" with a 50% probability.  I thought that random is random is random.  Have I misunderstood?

+Diodes also use quantum effects for noise /entropy generation.

Statistically, yes, random is random (read: entropy).  It's also worth stating that you can really only approximate how random something is based on samples.  This means that you can't measure randomness explicitly, but you can make approximations based on expected outputs compared to conditional probabilities, etc.

Quantum computing does have random properties which are a fundamental part of quantum mechanics, but a strict requirement of any quantum gate is that they are invertible.  This means that for any quantum gate, and any quantum algorithm, you must be able to reverse any transformation (page 18).  This is achieved through the use of error-correction, as well as the design of algorithms used in quantum computing.

There is a subtle difference between the randomness associated with quantum computing, and the randomness generated by quantum properties.  I've submitted an answer to the question you linked, and the reason I made it clear that you don't need a quantum computer to generate randomness using quantum mechanics is because it's a different use of quantum mechanics.

Quantum randomness can be generated by some cameras already built into several models of smart phones.  This is possible through measurement on the few photon level.  Essentially you use a camera to measure a few photons, and then translate that into a seed for a PRNG.  This works because when light is measured as a photon, the distribution follows the double-slit experiment for individual particles.  If you were to measure light as a wave, the distribution is fundamentally different.

The main upshot is that randomness is randomness.  For cryptographic purposes, this obviously isn't enough of an answer.  We need ways to measure randomness, and so we use tools to approximate how random an output is.  This isn't measuring randomness itself, but the approximation helps give information on whether we should classify something as an RNG or PRNG.

So while there's a difference between calling rand in C++, or /dev/urandom in Unix systems, in terms of a PRNG generated classically compared to quantum randomness the difference may potentially be less pronounced.  Even if there is a sharp distinction between a classical PRNG and quantum randomness, you're right that for the foreseeable future both would most likely rely on classical randomness extractors.


Why does SHA-2 call for doing 10* padding in addition to appending the message length? Appending the length of the message when padding of a SHA-2 message is sufficient to satisfy the Merkle-Damgård construction.  However the padding in SHA-2 also pads with 10* between the end of the message and the message length data.  I know that 10* padding lets one turn non-block-aligned length messages into block-aligned length messages in a reversible way.  However, because the padding already encodes the bit length of the original message, this 10* padding is redundant.  Using the bit length data we can already determine where the original message ends and 0* padding would be sufficient.  In fact, in "One Way Hash Functions and DES. Advances in Cryptology" in Crypto’89, Merkle uses 0* padding followed by the length.

So my question, why does SHA-2 call for doing 10* padding in addition to appending the message length?

As rightly pointed in the question, 0*+length padding would work just as well as 10*+length padding, with the benefit of simplicity and requiring one less block in some cases, like SHA-256 for a message of 56 bytes.

I guess SHA-2 does this because SHA-1 did, and before that SHA, MD5, and Ronald Rivest's MD4 (1990), which is the earliest reference that I can point, and already had:

  Step 1. Append padding bits

     The message is "padded" (extended) so that its length (in bits)
     is congruent to 448, modulo 512.  That is, the message is
     extended so that it is just 64 bits shy of being a multiple of
     512 bits long.  Padding is always performed, even if the length
     of the message is already congruent to 448, modulo 512 (in
     which case 512 bits of padding are added).

     Padding is performed as follows: a single "1" bit is appended
     to the message, and then enough zero bits are appended so that
     the length in bits of the padded message becomes congruent to
     448, modulo 512.

  Step 2. Append length

     A 64-bit representation of b (the length of the message before
     the padding bits were added) is appended to the result of the
     previous step.  In the unlikely event that b is greater than
     2^64, then only the low-order 64 bits of b are used.  (These
     bits are appended as two 32-bit words and appended low-order
     word first in accordance with the previous conventions.)

Perhaps earlier block-cipher based MACs used 10* padding without length strengthening, where 10* prevents some trivial attacks 0* allows. In particular, 10* padding was used for variants of the so-called "CBC-MAC", which became ISO/IEC 9797-1 MAC Algorithm 1 padding method 2 (approved 1999). It would then be plausible that the 10* padding was kept, and length-strengthening as suggested by Merkle added, because 10* padding alone would not be as safe.

Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, in section 9, mentions both padding with 0* (algorithm 9.29) and 10* (algorithm 9.30) and note:

  The padding method of Algorithms 9.29 and 9.30 originated from ISO/IEC 10118-4 “Information technology – Security techniques – Hash-functions – Part 4: Hash-functions using modular arithmetic”, draft (CD), 1996.

but I doubt this is the true origin.


DES — Can I recover the key when I have both ciphertext and the plaintext? Given a message and DES encrypted form of said message, is it possible to efficiently compute the key used to encrypt the data?

Efficiently - no. However, the best attack on DES - linear cryptanalysis - works with known plaintexts, and theoretically may work slightly faster than the brute force even for small amounts of data.

Computing linear relations between plaintext $P$ and ciphertext $C$, an attacker is able to enumerate all keys according to their likelihood. The PhD thesis by Junod provides a comprehensive description of the attack for various parameters in Sections 3.1, 3.2. There is a formula of the probability that the correct key is found among the $r$ candidates with the highest score after analysis of $\nu$ (plaintext,ciphertext) pairs. Given only few ciphertexts, all the keys will have almost the same likelihood, and $r$ must be very close to $2^{56}$ to provide the success rate close to 1. Still, the resulting attack must be faster than the brute force, even though only marginally.


Message length in XMSS I read that XMSS generates many private keys and one key must sign only one message. Does it mean though that I sign many different messages, or do I sign one message, which, if its longer than 256bit, will be split into two parts and the 2nd part will be signed with the 2nd private key? Is the signature only meant to sign one message and its parts, or many different messages?
What is the maximal length of the message? XMSS computes 2^h keys, where h is the height, usually of value 20, does it mean I can only sign 2^20 messages or a message with 2^20 parts?

Does it mean though that I sign many different messages, or do I sign one message, which, if its longer than 256bit, will be split into two parts and the 2nd part will be signed with the 2nd private key?

You can sign many ($2^h$) different messages; it does what just about any other signature algorithm does; it hashes the initial message, and then signs the hash.  If you're using SHA-256 or SHAKE-128 as your hash function, then this hash is 256 bits, which is what is signed by a single WOTS+ private key.
Now, XMSS is a bit different than most other signature schemes; it stirs in some unpredictable data at the front of the message when it computes this hash (and includes this unpredictable message in with the signature) - it does this to prevent collision attacks from working (an adversary who picks the message to be signed cannot predict this unpredictable data, hence he cannot pregenerate a collision) - it does this because everywhere else, XMSS depends on the (second) preimage resistance of the hash function, and it would be a shame if it made a stronger security assumption on the hash function for the initial message hash.

What is the maximal length of the message?

If you're using SHA-256, this would be not quite $2^{61}$ bytes; if you're using SHAKE-128, there is no upper bound.


Weak Boneh-Boyen Signature in Composite order group In the paper Ring Signatures of Sub-linear Size Without Random Oracles, authors have remarked that the scheme is instantiable in composite order setting, too. I am attaching the following reference below. Can anyone please help me in understanding the argument I have highlighted?

1) To perform verification in the order $p$ subgroup (if the order is $n=pq$ for $p,q$ prime, $a^q$ maps an element $a$ into the order $p$ subgroup - and this clearly also holds in the target group).

2) The argumentation in the unforgeability proof is that switching from $h$
of order $n$ in the common reference string of the GS proof to $h$ of order $q$, then under the subgroup decision
assumption the probability of a forgery to happen only changes negligibly. So their idea is that
playing the original unforgeability game with the adversary (where $h$ is of order $n$) and a forgery happens,
then playing the modified game with $h$ of order $q$ does not change the probability of a forgery
to happen. But now as in the modified game the commitments are perfectly binding and the
proofs are perfectly sound (the adversary cannot forge a proof), a forgery output by the adversary implies a forgery of a BB signature (which we know can
only happen with negligible probability).

Now, as the simulator who interacts with the adversary knows the the factorization of $n$ (trapdoor of the GS common reference string), it would not yield a valid reduction
if the security of the BB signatures would be considered in the entire group and would require that the factorization of $n$ is unknown (as the simulator knows the factorization, it could then compute a forgery on it's own and thus the reduction would be meaningless). However, if one assumes that forging BB signatures in the order $p$ subgroup is hard even if knowing the factorization of $n$, then the reduction can use the forgery output by the adversary in the unforgeability game to break the unforgeability of the BB signature scheme.

As the proof in the paper is very sketchy, this does not show up anywhere else in the paper.


How to alter text that was encrypted with AES CBC using PKCSPadding7 Assuming, I had a ciphertext along with its decrypted plain text result but not the IV or the Secret Key. (keep in mind that the text was encrypted with AES/CBC/PKCSPadding7).
How would I go about changing specific characters in the ciphertext?
For Example:
Ciphertext: 08226C1C87A83DDF02C54CF0802624D8
Plaintext: Apple1

How would I change the ciphertext to decrypt to Apple2?

First, normally a message authentication function (e.g. HMAC) is used with AES-CBC, specifically to prevent the type of attack described in this question, where the ciphertext is altered by an attacker in an attempt to produce a ‘wanted plaintext’ upon decryption.  See When do I need to use CBC and HMAC? for more info.
Also, the ciphertext that you posted is only one block long (16 bytes, or 128 bits).  So, AES alone (without CBC, and therefore without an IV) could have been used to produce this one block ciphertext.  It’s not clear from your question whether this one block of ciphertext was produced using AES alone, or using AES-CBC (with an IV).
If this one block of ciphertext as produced using  AES-CBC (with an IV), then normally the IV would be sent along with the ciphertext.  Without the IV, the recipient would have no way of decrypting the first block (and in this case, the only block) of the message.  The HMAC (above) is usually taken over the ciphertext and the IV, so that an attacker cannot modify either of these without detection.
In light of the above, there are a few ways to answer this question.

Older encryption algorithms such as XOR, OTP, Caesar, etc. without authentication, are notorious for being vulnerable to the type of attack that you describe, where the ciphertext is altered to produce a ‘wanted plaintext’ (see examples at https://security.stackexchange.com/questions/33569/why-do-you-need-message-authentication-in-addition-to-encryption).  However, putting aside the CBC part of AES-CBC, AES in and of itself is considered to be resilient to ‘known plaintext’ attacks.  Therefore, knowing the ciphertext and the plaintext of the message does not give an attacker an advantage in finding the encryption key, or mounting an attack like the one that you describe.

If we consider AES with CBC (AES-CBC), and the ciphertext and IV are not authenticated using an HMAC as described above, and the attacker knows the original plaintext, then the attacker can change the IV to cause the decryption to produce any plaintext he wants in the first block (and in this case, the only block) of the message.  See Can you change an AES encrypted message if you control the IV? for more info.

Nothing in this answer so far involves padding.  The fact that you mention padding in your question suggests that perhaps you are thinking of a padding oracle attack.  This type of attack requires the recipient of the message to leak information when it encounters a padding error upon decrypting the message.  In this case, the attacker can gradually deduce the encryption key by repeatedly crafting and submitting ciphertexts to the recipient for decryption, and learning from the recipient which ones produce padding errors.  Once the attacker learns the encryption key, he simply uses it to encrypt the wanted plaintext, so that upon decryption, the ciphertext decrypts to the wanted plaintext.


Elgamal Protocol Failure I'm having a difficult time trying to solve this problem.

  Suppose Alice uses the Elgamal signature scheme with  $(\alpha,
 \beta, p) = (2, 33384, 65539)$.   She publishes the two signed
  messages: $(m_1, r_1, s_1) = (809, 18357, 1042)$ and $(m_2, r_2,
 s_2) = (22505, 18357, 26272)$. Find $a$ by setting up and solving
  appropriate linear congruences. (I.e., don't compute the discrete
  logarithm of beta directly)

I know that $\beta = \alpha^a \bmod p$, which in this case would be $33384 = 2^a \bmod 65539$.  However, I have no idea how to use the messages to set up congruences to solve for $a$. Any help is appreciated.

Note the relation between $r_1$ and $r_2$
Infer the relationship internal variables need to have because of this
Write down the equations to calculate $(r_1,s_1),(r_2,s_2)$ and use the above relationship
Pretend the equations would be over $\mathbb R$ and solve the above system of equations for $a$
Now plug-in the values and actually perform the modular arithmetic
You now should have recovered the private key


ECIES for not shared encryption I am using ECIES (Cryptobox as poncho pointed out) for public key encryption with ECC between Alice and Bob with secret/public keys $(a,A)$ and $(b,B)$ respectively. So Alice encrypts to Bob with

$$
Encrypt(aB,Message)
$$

Additionally I would like to encrypt some of Alice's data such that only she can decrypt it. Is it safe to use ECIES to compute a shared secret from Alice's secret and public key as in

$$
Encrypt(aA,Message)
$$

I know I could randomly generate a public key, but then I would have to store this key somewhere which I would like to avoid.

Yes, however I believe that the reason is a bit subtler than what fgrieu gave.

From your question, I don't believe that you're actually doing standard ECIES, but instead something such as NaCl's cryptobox (which is a variant).

With standard ECIES, to encrypt to the public key $A$, the encryptor selects a random value $r$, and generates the ciphertext:

$$rG, \text{Encrypt}( rA, \text{Message} )$$

In contrast, with Cryptobox, Bob doesn't select a random value, instead, he uses his own private key.  That is, to encrypt to Alice's public key $A$, he will take his private key $b$, and produce [1]:

$$\text{Encrypt}( bA, \text{Message} )$$

This is effectively ECIES (with the $bG$ value implicit; that's Bob's public key).  As Bob's private key is random (independent of Alice's keys), this is secure as long as standard ECIES is secure [2].

However, this raises the question: what if Alice encrypts to herself?  Will that remain secure?  That would not immediately follow from the security of ECIES, as Alice's private key is not a random value independent of Alice's public key.

In this specific case, it turns out to be secure.  Specifically, the problem of "given $G, aG$, compute $(a^2)G$" (which is needed to decrypt Alice's message to herself) is just as hard as the general problem "given $G, aG, bG$, compute $(ab)G$".  That is, given a way to solve one, you can solve the other.

[1]: Actually, I believe Bob includes a nonce to make the encryption nondetermanistic; that's not important for this explination

[2]: Actually, we need to assume that this construction doesn't leak information about Bob's private key, and that ECIES is secure even if you repeat the same random value; that's actually the case.


SHA-3 block sizes / bitrate calculation? Looking into different papers and online documents, I find the following block sizes for SHA-3:

SHA3-224: 1152 Bit
SHA3-256: 1088 Bit
SHA3-384: 832 Bit
SHA3-512: 576 Bit

Somehow I am unable to find (calculate) these numbers from the specifications:

http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
http://keccak.noekeon.org/Keccak-implementation-3.0.pdf

How are these block sizes calculated, respectively where exactly are they specified?

First of all, in the case of SHA-3 we don't call it block size but bitrate.

SHA-3 has been formally defined in FIPS 202 and in its reference manual.

  We define the sponge function denoted by $\operatorname{KECCAK}[r,c]$ by applying the sponge construction as specified in Algorithm 1 with $\operatorname{KECCAK-}\!f[r+c]$, multi-rate padding and the bitrate $r$.
  $$\operatorname{KECCAK}[r,c] = \operatorname{SPONGE}[\operatorname{KECCAK-}\!f[r + c], \mathrm{pad10^∗1}, r]$$

$c$ is the capacity, it defines the security level of the sponge.

The value $b = r + c$ is called the width of the state. It is either $25$, $50$, $100$, $200$, $400$, $800$ or $1600$.

  In the scope of the SHA-3 contest, we proposed the largest permutation, namely $\operatorname{KECCAK-}\!f[1600]$.

So in our cases $b = 1600$.

The notation $\operatorname{SHA3-}\!x(M)$ produces a digest $x$ bits long and has a security claim $d = x$. Without going into details, $d$ can be seen as $c/2$ (see here and here, Chapter 7, page 71).

Therefore in:

$\operatorname{SHA3-224}(M)$, $c = 2\times224 = 448$ and $r = 1600 - c = 1152$
$\operatorname{SHA3-256}(M)$, $c = 2\times256 = 512$ and $r = 1600 - c = 1088$
$\operatorname{SHA3-384}(M)$, $c = 2\times384 = 768$ and $r = 1600 - c = 832$
$\operatorname{SHA3-512}(M)$, $c = 2\times512 = 1024$ and $r = 1600 - c = 576$

Hence:

$\operatorname{SHA3-224}(M) = \operatorname{KECCAK}[1152,448]$ with $\mathit{bitrate} = 1152$
$\operatorname{SHA3-256}(M) = \operatorname{KECCAK}[1088,512]$ with $\mathit{bitrate} = 1088$
$\operatorname{SHA3-384}(M) = \operatorname{KECCAK}[832,768]$ with $\mathit{bitrate} = 832$
$\operatorname{SHA3-512}(M) = \operatorname{KECCAK}[576,1024]$ with $\mathit{bitrate} = 576$

As the speed of the algorithm is directly related to $r$ (bit rate absorption), the higher the security, the slower the function will be.


Generating a 30-32-bit PRP I want to generate a small 30 or 32 bit PRP. I am going to use that PRP in an open web service and anyone will be able to get any number of plaintext-cyphertext pairs.

I've found an algorithm called FastPRP and the problem statement fits my requirements perfectly. However the performance seems quite low for 30-32 bit range.
I need a high-performant point evaluations for both PRP and an inverse PRP.

Are there any 32-bit PRP algorithms (less secure probably) that allow a faster point evaluations?

If you need a 32 bit PRP, might I suggest the Speck cipher?  It isn't greatly secure (with a 32 bit block size, the only option is a 64 bit key, which isn't great), however it's extremely fast.


Why does Fortuna (RNG) require entropy sources to specify accumulator pool? Re-reading my copy of Cryptography Engineering for the holidays, I was struck by the following question about the Fortuna RNG:

Why require an entropy source specify which pool a random event should go in?

(For code, see the add_random_event method in this python implementation).

The book discusses why you wouldn't want to just round-robin (or similar) all events, as a compromised source could force all good data into specific pools.  This makes sense.

If I'm following the discussion correctly, each entropy source spreading it's events evenly across all pools is the desired behavior.  This also makes sense.

What I don't quite get is why you couldn't attach a counter or similar to each entropy source and use that bit of Fortuna-managed data to route events.  Seems like that would make it harder for an evil entropy source to influence particular pools, and simplify the accumulator interface a little bit.  The cost is an additional bit of state per entropy source, which doesn't seem substantial.

Now since it seems obvious to me, I suspect there is a flaw in my reasoning.  So, why is pool choice delegated to the entropy source instead of managed by Fortuna?

I see essentially three ways to design this API:

Take a pool
Take a counter and have the accumulator calculate the pool as pool = counter mod poolCount
Take a sourceId

Of these 2) seems clearly superior to 1) since the caller doesn't need to care how many pools there are, or how to distribute among the pools.

Comparing 1), 2) with 3) is more difficult, but I think for most situations 1) or 2) is preferable over 3).

If you look at a practical implementation, there will be three kinds of component, which don't trust each other: a) the pool b) some kind of service/daemon reading from the entropy source and feeding into the pool c) the actual entropy source.

Implementing method 1) is pretty easy for both pool and daemon:

The pool just needs to take care of thread safety, and feeds the entropy into the pool it's told.
The daemon just needs to take care of one counter per entropy source

Implementing method 3) is much harder in most circumstances:

You need some kind of sourceId which is different for each entropy source. Using simple integers is already annoying, since you now need a protocol by which a daemon can request a new sourceID. Then you need a process to deallocate them when the daemon terminates, which is problematic if it crashes.

But your biggest problem is that one malicious daemon could try to guess the sourceIDs of another daemon, possibly allowing it to feed that other daemon's data into specific (probably high-index) pools. This means that you need some kind of unforgeable sourceId, such as a random 128 bit value. But now keeping that counter becomes annoying for the pool, since it needs a hash table, not a simple index into an array. No biggy for high level languages, but annoying in c.

For an in process pool in .net or python seems seems OK, since you can use new object() to create an unforgeable ID and weak hashtables are available.

For a multi process setup, this seems like a bad idea. For example on a unixoid system you could have some deamon processes that gather entropy and feed it to the /dev/urandom device via a AddEntropy(counter, data) syscall. This would be much more complicated with a sourceId based design.


Is it actually possible to secure data with gpg DSA keys? I think GPG is difficult to understand . All the different versions and policies and algorythms . But today I got really confused . I tried to create a 3072 bit DSA key ( which as far as I undestand DSA can only be used for signing ) and encrypted some data with it . And well ... It worked .
So here are my questions :

1) Why does The Digital Signing Algoryhtm encrypt data and why is this even an option in gpg ?

2) Is with DSA "encrypted" ( if it even is ) data secure ?

Why does The Digital Signing Algorithm encrypt data [...]?

You can't encrypt data using DSA.
However gpg supports ElGamal encryption, which is an encryption scheme which can be quite naturally derived from the Diffie-Hellman key exchange and typically gpg pairs "DSA signing" with "ElGamal encryption". Why is it paired like that? Because (in theory) you could use your DSA public key for ElGamal encryption and both scheme's security is strongly related to the discrete logarithm problem, so it makes sense pairing them.

  Why is this even an option in gpg ?

Back in the day, the dark ages of crypto, RSA was patented. That is you needed to license it from RSA (the company) to use it. This is one of the reasons why DSA was developed and as established above pairing ElGamal with DSA makes sense. Now of course gpg was also affected by the patent issues surrounding RSA which is (I could imagine) why they originally offered only DSA / ElGamal. The RSA patents have expired in the 2000s which is why we have now RSA for everything and DSA / ElGamal mostly is left in for backwards compatibility and to let users a choice on factoring vs discrete logarithm based security.

  Is with DSA "encrypted" ( if it even is ) data secure ?

As this means that the data is actually encrypted with ElGamal and only used to encrypt the key for hybrid encryption, I'm very confident that this is actually secure.


Has there been any research on entropy efficient information-theoretically secure PRNGs? I have an idea for an research project, but I am first wondering if it has been researched or implemented before.

I think I have a way to come up with a set of PRNG algorithms which have the following properties:

Information theoretic security (or perhaps even perfect security) of the output is guaranteed if it is guaranteed for the seed.
The algorithm "re-seeds" using additional information from the seed only whenever it is absolutely necessary to guarantee the first property.

It is easy to satisfy these properties: just make an algorithm that outputs the "seed" bits. That's not what I'm interested in. I'm interested in one that could convert between symbol spaces. More generally, this algorithm would present itself as a random number generation function which accepts a natural range n for each function call, and returns as the result a random integer in the range [1, n] which is chosen from a perfectly uniform distribution over that range. The seed would probably just be a bit sequence, but it could be any sequence of pairs (a, b), where a is the information in the form of a natural number, and b is the inclusive upper limit for a. As such it could convert between bases, even mid-sequence.

Meeting the first property is possible by using rejection sampling, but rejection sampling wastes information. My goal is to prove that an algorithm can satisfy both properties in an entropy-optimal way that wastes only a negligible amount of information so as not to burden an entropy source.

Since you are looking for an algorithm that guarantees entropy for the output if the input it entropic, you are not actually looking for a PRNG, which would expand a seed to a longer random output, but only a transformation from a binary sequence to arbitrary values.

You can achieve this using arithmetic coding, or range encoding, which is the same thing in a slightly different manner. It is a way to encode values from arbitrary probability distributions into minimal size. In your case you can decode a random "seed" sequence to extract random values in any interval(s).

Caution: normally it is fine to be slightly inexact in the encoder math as long as everything is deterministic, since that only worsens the encoding rate slightly. In your case, for secure random numbers the possible outputs must be equally probable so typical implementations may not work for you. Rounding must be done in a way that ensures this.


Can a computationally unbounded adversary break any public-key encryption scheme? Assume there is a public-key encryption scheme $(KeyGen, Enc, Dec)$ with perfect correctness (i.e., for all messages M and valid key-pairs (PK,SK), we have $Dec_{SK}(Enc_{PK}(M))=M$).

Will there always be a function $A$ such that for all messages M and valid public-keys PK, $A_{PK}(Enc_{PK}(M))=M$?

In other words, can a computationally unbounded adversary decrypt the message, having only the public key?

Yes, a computationally unbounded attacker can break any public key system.

One easy way to see this is to consider the KeyGen algorithm, which takes takes as input a value R (which in normal use is the output of some random number generator), and outputs a public key PK and a private key SK.

Now, what a computationally unbounded adversary can do is consider all possible inputs R, and see which one produces the public key that he has been given.  We know that there is at least one such input R (the one that was used when the public key was created); we can then use the corresponding private key to decrypt the message.

The obvious objection to this is "what if there are multiple such R's which generate the same public key, but different private keys?".  Actually, it turns out that this is not a problem; because each such private key SK was generated correctly by the key generation function and corresponds to the public key under attack, it must still satisfy the formula:

$Dec_{SK}(Enc_{PK}(M)) = M$

Hence, it must correctly decrypt the message, even if it was not the exact private key that the legitimate user had.


Implementing RSA with small integers in CUDA I have found some researches dedicated for speeding-up RSA calculations using CUDA. But I am wondering how they do that, given that the biggest unsigned int that could be declared in CUDA is 64 bit.

Could anyone clarify this ambiguity for me?

It is of course possible to combine multiple operations on 64 bit or 128 bit to operations modulo $N$ where $N$ is a value up to $2^{1024}$, where 1024 bits is about the absolute minimum size for an RSA key (2048 bit is now being more common, at least 3072 bits is recommended).

For example, take a look at my 32 bit JCInteger class that I created for the 16 bit Java Card platform. Processors even only handle operations on single bits and combine them into 64 or 128 bit instructions resulting in operations in your GPU.

One problem is that modular exponentiation - the most inefficient part of RSA operations - can only be parallelized to a small extend, leading to speed ups of about 2 times single core operation. This is because the multiplications required to perform the exponentiation generally require the outcome of previous multiplications.

So what you will probably see is that 1-4 GPU threads (1 probably most common) will be used to implement modular exponentiation. The rest of the speedup must come from executing a lot of RSA calculations in parallel. This would be useful for instance when a lot of server authentications are required for parallel TLS handshakes.

Parallel operation could be very efficient for creating RSA keys as well. Looking for primes is embarrassingly parallel, and creating RSA keys of 8Ki size and over takes plenty of time even on the fastest CPU's. Unfortunately that doesn't mean much in the end; generally RSA keys are long term keys so there are few use cases where the - possibly huge - speedup would be useful.

Note that I found quite a few CUDA related RSA papers that simply implement RSA for very small sizes of $N$. These should be thought of as exercises rather than real implementations of RSA. This is not always clearly mentioned in the readme files or papers.


Password protection in ARJ: 3 characters of password are retrievable On this site there is information that one can know first 3 characters (bytes) of the password without brute force. I know that ARJ in older versions has very simple encryption, i.e. XOR with passwords.

I can't understand how it is possible to retrieve those 3 characters. Is compression or realization of these archives is weak?

More info on the ARJ format with international (i.e. extremely weak) encryption can be found here at cpsr.org:

A = password
B = compressed text to be encrypted
A' = permuted password
B' = encrypted compressed text
C = constant
^ = XOR

A' = A ^ C
B' = B ^ A'

This is performed character by character.

So if you know the constant (from the application code) and the input and output character then you've got just one variable left: A, the password character:

A = B ^ B' ^ C.

However, the header contains at least 3 static bytes: the header ID and the archiver version number. So for these bytes / characters you don't need to test anything.

There are many other semi known values in the header, but you will need some additional information such as the length of the password to use them to crask the password.


Encrypt a file with AES using a secret key derived with Argon2 I would like to encrypt some sensitive files on my computer and smartphone so that they remain unreadable even if the computer is stolen.

So far as I'm concerned, AES is the best encryption algorithm, so I would go for it. For the AES, I also need a secret key (or cipher key). Therefore, I need a key derivation function, preferably a password-based one. Obviously, I do not want to store the derived secret key on the computer (or smartphone), otherwise, the encrypted text could be easily decrypted using the secret key.

I have read that Argon2 is considered the best choice for password-based key derivation these days.

Now, in the "argon2 cffi Documentation Release 19.1.0" (January 17, 2019) I have read that "Argon2i uses data-independent memory access, which is preferred for password hashing and password-based key derivation" (page 3). Then, on page 9 I read the very same words about Argon2id: "That makes it [Argon2id] the preferred type for password hashing and password-based key derivation".

Now my first question is: Which of the two types of Argon2 is the best for password-based key derivation?

Further, as per the same document, the argon2.PasswordHasher algorithm "always uses a random salt for hashing". This implies that every time I enter my password to decrypt the file, the hashing algorithm will produce different secret keys, so in no way can I reproduce the secret key to decrypt my file.

Of course, I can store the salt on the computer (or smartphone) but then two other questions arise:

How can I use Argon2 with a predefined salt?

Is there a point in using a salt that is freely accessible (if my data are stolen)?

So, can somebody shed light on how Argon2 can be used as a password-based key derivation function? And what would be the solution to my problem?

Which of the two types of Argon2 is the best for password-based key derivation?

In short, as said by draft-irtf-cfrg-argon2-03;

  If you do not know the difference between  hem or you consider side-channel attacks as viable threat, choose Argon2id.

Argon2d is faster and uses data-depending memory access. Data dependency immediately enables side-channel. This is suitable for cryptocurrencies and applications with no threats from side-channel attacks.
Argon2i uses data-independent memory access and this is preferred for password hashing and password-based key derivations.
Argon2id In the first half of the first iteration works as Argon2i and for the rest works as the Argon2d. This enables both side-channel protection and time-memory trade-off.

  How can I use Argon2 with a predefined salt?

From a library for Argon2

    Usage:  ./argon2 [-h] salt [-i|-d|-id] [-t iterations] [-m memory] [-p parallelism] [-l hash length] [-e|-r] [-v (10|13)]
            Password is read from stdin
    Parameters:
            salt            The salt to use, at least 8 characters
            -i              Use Argon2i (this is the default)
            -d              Use Argon2d instead of Argon2i
            -id             Use Argon2id instead of Argon2i
            -t N            Sets the number of iterations to N (default = 3)
            -m N            Sets the memory usage of 2^N KiB (default 12)
            -p N            Sets parallelism to N threads (default 1)
            -l N            Sets hash output length to N bytes (default 32)
            -e              Output only encoded hash
            -r              Output only the raw bytes of the hash
            -v (10|13)      Argon2 version (defaults to the most recent version, currently 13)
            -h              Print argon2 usage

The libraries handle this for you. You just provide a random salt and store it, if you want to get the same result again, use the same salt.

  Is there a point in using a salt that is freely accessible (if my data are stolen)?

Normally, you can store these values - salt, iteration, memory usage, parallelization, output size - with your data. If you really want to keep them separately from the storage you can do it, but there is no need. It is designed to be secure even if they are known by an attacker. When servers are attacked, all of these parameters are also acquired by the attackers. Salt is used against rainbows tables. Remember Kerckhoffs's principles, only the key is secret.

  can somebody shed light on how Argon2 can be used as a password-based key derivation function?

There is a Key Encryption Key (KEK) methodology that is common with disk encryption utilities. Let say a file encryption key (FEK) is randomly generated by a good random source. Then your strong password is used to derive the KEK by a KDF, here in your case Argon2id.
$$\text{KEK} = Argon2id(salt, password)$$
Use your KEK to encrypt FEK and store it on your target ( your computer or phone). $$FEK^* = AES\hbox{-} Enc_{KEK}(FEK)$$

Now, you want to encrypt a file, use your strong password to generate the KEK

$$\text{KEK} = Argon2id(salt, password)$$

and use the KEK to decrypt your FEK from the storage.

$$FEK = AES\hbox{-} Dec_{KEK}(FEK^*)$$

Encrypt the file with an authenticated encryption mode like AES-GCM or ChaCha20-Poly1305 and store it on your computer or cell-phone.

$$\text{EnryptedFile, ATag} = AES\hbox{-} GCM\hbox{-}Enc_{FEK}(\text{file})$$ where ATag is the authentication tag.

You need to keep FEK only in system memory and purge it when the operations are finished.

The benefits of this approach;

you only need to memorize your strong password
The Encrypted FEK and Argon2id parameters can be stored together with the files or some other suitable place for your choice.
For each file, you can generate a new random FEK.

  always uses a random salt for hashing".

It is for each file or password not for every run of Argon2 run. You need to derive the same results if you want to compare the hash of the file or generate the same key, you have to use the same parameters including the salt. And to not forget that salt, you must write it somewhere.


The perfect way of using IV in CTR mode I understand that it is necessary to use the same IV for both encryption and decryption in the CTR mode. I'm thinking about the case when I concatenate the secret key along with the IV after generation, and the resulting byte array is sent to the receiver side in secure manner.

Is it practical to create a 32 byte array such that the first 16 byte is used to store the secret key and the last 16 byte is to store the IV and send the result to the receiver side?

It doesn't make too much sense at all to send the IV together with the key. The whole idea of an IV is that it is unique per key. But if the key changes value each time, then any IV is unique.

So you could use a static IV or even an IV that consists of all zeros. In that case you only need to worry that you don't reuse the key at other locations in the protocol. For instance for CTR mode, you should not use a Key Check Value that is generated by encrypting a block consisting of all zero's, as it would leak the initial block of the resulting key stream.

It's not a good idea to perform operations with the key to derive an IV though. If you need a separate key and IV from a given secret, please use a KBKDF such as HKDF to separately calculate the key and IV from the secret.

If your key is not changing despite the protocol given above then just prefix a unique (cryptographically safe random) IV to the ciphertext. This should also be the fail-safe default. Using an authenticated cipher like GCM or EAX should also be considered.

Edit

Sending the secret value to the other side over a secure channel is usually not a good idea. Session keys should be established beforehand, preferably by using a key agreement algorithm to provide forward security. Sending the key over a secure channel sounds easy, but if you already have a secure channel, you don't need a session key to establish a new one.


Two files encrypted with related data versus one file I have some code that takes a list of credit-card numbers, splits the number into two chunks, one chunk is 8 characters long, the other chunk is the remainder.

Each series of chunks is saved into individual files, for example my test data looks like (these are test CC numbers):

378282246310005
4111111111111111
4242424242424242
378734493671000
4242424242424242

So, file X would contain:

37828224
41111111
42424242
37873449
42424242

and file Y would contain:

6310005
11111111
42424242
3671000
42424242

Each record is separated by a common delimiter (a newline character).

File X is saved to a TrueCrypt volume using AES, and file Y is saved to a different TrueCrypt volume, also using AES, but using a completely unrelated key.

My question is, does doing this lower cryptographic strength due to this structure?

The reason why I bring this up is that if you know the contents of one file, you can make assertions about the contents of the second, due to credit-card numbers adhering to LUHN-10 (mod10) specifications.

For example, if I know file X's contents, I know the corresponding record in file Y must pass the LUHN-10 check, and therefore knowing file X exposes information about file Y, Y's potential value is reduced by a factor of 10.

Slightly off-topic, but does storing a single file with full credit card numbers separated by a common delimiter expose information, if the attacker knows the structure of the file?

No, it doesn't lower security, but it doesn't (asimptotically) enhances it either.
AES (or better, as Thomas pointed out, the way aes is used inside Truecrypt) is secure against IND-CPA attacks, so the encryption of a file itself does not reveal ANY information about the plaintext, except for its length.

Even if an adversary knows 99 bits of a 100 bits encrypted file (but not the encryption key), it cannot find the last bit without iterating trough the whole set of keys.
Knowing something about the plaintext does not help the adversary.


Cracking simple RSA when just the ciphertext and one public key is known Can someone explain to me (Or better yet, point me to a tool that does the brute forcing) how to crack a standard, simple RSA cipher (So don't bother with padding) if I know just one public key, the ciphertext, and some text that I know for sure is part of the plaintext?

Please don't point me to the Wikipedia article or something, I'm trying to get a simple explanation that is fully understandable.

Running RSA backwards would imply cracking the key (determining the private key) and you could brute force that by factoring.  You could generate all possible prime's of the requisite size until you could generate the known public key.  Or perhaps there are other approaches that are more mathematical, that could factor for the primes, which would also be a form of brute force, as currently factoring is thought to be a NP-hard problem.


Hide the presence of a key in a key-value storage Problem: I want to build a key-value storage in such a way that it would be impossible to detect a presence of a key in the storage by inspecting it. In other words, any read operation with any valid key always returns a valid-looking value, and without additional knowledge about value it is impossible to say if this key was ever written to the storage, or is it a plain garbage.
Such kind of storage is possible. For example, a simple (but space consuming) approach would be to create a storage and pre-fill all possible valid keys with random values. Write operation replaces the existing value with the new one, delete operation replaces the existing value with a random one. Then just by looking at the storage it is impossible to tell which keys actually contain written values, and which just store a random garbage.
But this of course is impractical for large enough key space.
I suspect that there could be a more practical solution.

Suppose you have a set of key-value pairs $(k_1, v_1), (k_2,v_2), \ldots$. You can store the coefficients of a polynomial $P$ that satisfies $P(k_i)=v_i$. The polynomial can be evaluated at any point to give a plausible output.
The degree of the polynomial leaks the number of key-value pairs, but if the $v_i$'s are uniform then the polynomial leaks nothing about the $k_i$'s. This is because for every way of fixing distinct $k_i$'s, the polynomial's coefficients are an invertible linear function of the $v_i$'s, so the coefficients are uniform if the $v_i$'s are uniform.
The only real downside is that polynomial evaluation is a bit slow: if there are $n$ key-value pairs then probing this data structure costs $\Theta(n)$.
However, there are alternatives to polynomials that have the security properties you need, with cheaper $O(\kappa)$ access time (for security parameter $\kappa$).
They have slightly higher storage overhead, whereas polynomials are optimal in size (exactly $n$ space to store $n$ key-value pairs).
The best reference for these data structures is actually an upcoming paper of mine, which will be on eprint in the next few weeks. I can post an update here when it's available.
In the meantime, the "best" publicly available oblivious key-value store is the probe-and-XOR-of-strings data structure that we propose in ia.cr/2020/193.
It has $O(\kappa)$ access time and $\sim 2.5n$ size to store $n$ key-value pairs.


Is the linear and differential cryptanalysis only dependent on Sbox? While performing the linear and differential cryptanalysis a Linear Approximation Table(LAT) and a Different Distribution Table(DDT) is required which is created exploiting the S-box of the cipher which can be found in the tutorial of Howard heys. Now my question is if I take a random S-box for every other encryption and my cipher has a very good diffusion mechanism is my cipher still vulnerable to linear and differential attacks?

The question is contradicting with the title.
A random S-Box with a "very good diffusion mechanism" would be perfectly ok, assuming enough rounds.
A random S-Box without a "very good diffusion mechanism" would be worse.
For example, consider the AES with the S-Box replaced by a random S-Box. We can use known bounds on the number of active S-Boxes in AES (even the simple one - 5 active S-Boxes every two rounds), and use the differential uniformity / nonlinearity of the new random S-Box to give a provable bound on the differential/linear cryptanalysis. Possibly, we would need to increase the number of rounds a bit. Though, such proof would refer only to a single-trail cryptanalysis, but this is exactly what was done for AES. For example, truncated or higher-order differential cryptanalysis would not be covered.
Answering your question: security against linear/differential cryptanalysis depends both on the S-Box and the linear layer, though in a different way. Of course, in an edge case like fully linear S-Box, a strong linear layer won't help.


Disk encryption using AES-CBC: is reliance on previous block data a downside? I have seen drives that boast that they use AES with CBC mode, which doesn't really make sense in my opinion, sure it's more secure than ECB (but actually, leaving security aside, ECB is better suited for disk encryption than CBC, explaining later)

The Problem with CBC is that you have a serious chicken and egg problem, which doesn't get very bad when working with most files, but gets problematic in disk encryption because it relies on the ciphertext of the previous block, wouldn't this be a serious performance bottleneck?
Encryption parallelizing is one thing (although I think that encryption speed > HDD speed) but what happens if I change/remove for example block $1$? Won't the drive be unusable while re-encrypting ALL the remaining data?

ECB is junk security-wise, that one is true, but it doesn't rely on the previous data, which gives it an advantage, but then again CTR mode has the same advantage and XTS as well (aside from the last block which may rely on ciphertext stealing).

As you know, it makes reading and writing the disk very slow if all the data in the drive is chained together. If so, writing to a drive of size $n$ at position $p$ will require $\Theta (n-p)$ time. One solution is the drive being divided into sectors, and each sector being chained. The IV of each sector can be attained using ESSIV. it generates IVs from a combination of the sector number with the hash of the key. This method is used in dm-crypt, OpenBSD's swap encryption, and FreeOTFE.


Equivalent key size between HMAC and AES? I have seem comparison between AES and RSA, e.g., AES 128 bit key is equivalent to RSA modulus 3072 bits. Is there such comparison between AES key size and HMAC?

Well, there are two potential key recovery attacks against HMAC (assuming a reasonable hash function):

Brute force the key; that is, take a valid (Message, MAC) pair, and try every possible key, and look for a key that gives that MAC for that Message
Brute force the internal hashing state immediately after processing the IPAD/OPAD; here, you would take a valid (Message, MAC) pair, and try every possible key, and look for a key that gives that MAC for that Message

Now, for first attack would take $O(2^k)$ time (for a key size of $k$); the second attack would take $O(2^{2n})$ time (if the hash function had an internal state size of $n$ bits).

With realistic key sizes and hash functions, $2^k < 2^{2n}$; hence the best attack is an exhaustive search of the key space; this gives us the same approximate strength as AES for a given key size.


How can I retrieve data embedded in an image with steganography? I want to know is there any way to retrieve data embedded in a steganalised image by just scanning the image with mobile scanner? Just like qr code scanning

In general, you can't.

The reason is this: the data might be encrypted on a way what makes it indistinguishable from random noise. Actually, any good quality encryption does it so.

Thus, if you try to separate any possibly steganographically hidden data, you have no way to know, if it is really random noise, or it is encrypted, but worthy content.

It might be possible if the hidden data is not encrypted on some reason (for example, for better data safety).


What is best practise for salting and multiple-hashing of passwords? I have been presented with some custom PHP code for salting passwords and applying multiple rounds of hashing.

It looks reasonable, but I fear home-grown crypto.

Is there an existing password salting and multiple hashing algorithm which I could use instead of code from a non-cryptographer.

The algorithm needs to accept a password, a salt and the number of rounds.

I've found bcrypt, which looks appropriate, but I'm concerned that it's old.

Current best practice does include bcrypt, which is the same as PHP's built in password_hash() function. Future best practice will probably be Argon2.

Other widely used secure KDF options include PBKDF2 with SHA512 or SHA256 as the hash function, and scrypt. scrypt and bcrypt differ from PBKDF2 in that they can use large amounts of memory, and thus resist cracking on commodity hardware better, which has more processing power than memory in the context of hash brute forcing.

bcrypt and PBKDF2 do have a specific issue, which is that a large password can cause the algorithm do behave in a way one would not expect. In bcrypt, there is a hard limit on input text, and a long password is simply truncated. In PBKDF2, the password is used as a direct input to HMAC, and if it is too large, the hash function must process the data more than once. My fix is to simply hash the password once with SHA512 before sending it to the KDF, as that makes the password input 64 bytes, which is within the bcrypt limit, and needs only a single hash with PBKDF2-SHA512.

Storage in the database is also an issue. Best practice is to use either the Modular Crypt Format or the PHC String Format. The trend is to use the PHC format over MCF as it is still based on MCF, but more flexible, and with more specific rules. PHC format with parameters allows forwards/cross compatibility and easy migration.

An example PHC format string:

$bpmhash_sha512$i=5,l=48$caaaaaaaaaaaaaaaaaaaaaaaaaaaaaab$HvrCpcKm209ikRst7gpsWbh1p5QyiA33R6iovxo0da6CX+lU1wKw0SserPtb6U3O

Where :
algorithm = bpmhash_sha512 (pbkdf2 with 1 round prehash)
i = the round count as 5
l = the output in bytes as 48
salt = caaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
hash = HvrCpcKm209ikRst7gpsWbh1p5QyiA33R6iovxo0da6CX+lU1wKw0SserPtb6U3O


Why does this square root algorithm work? I've been doing some elliptic curve cryptography, and a library I'm using has this slightly bizarre algorithm for computing modular square roots:

Let $x$ be some quadratic residue modulo $p$ for some large prime $p$. Let $h$ be some element of $\mathbb{Z} \setminus p\mathbb{Z}$ such that $h^2-4x$ has no square root modulo $p$. Let $V_n$ be the Lucas sequence with $V_0=2$, $V_1=h$ and $V_n=hV_{n-1}+xV_{n-2}$. Let $k = \frac{p+1}{2}$. Then $V_k = 2\sqrt{x}$. This is obviously less efficient than the well known algorithm for $p \cong 3 \mod 4$, but apparently works in a more general case

Immediately, one might believe this definition to be contradictory; indeed the characteristic equation of this recurrence is solved by square rooting $h^2-4x$, but, being a Lucas sequence, this impossible term never appears in any particular value of $V_k$.

The only reference to this algorithm I've found is as an exercise in an undergraduate-level textbook, which suggests that this is solvable by some fairly simple maths, but nothing I've tried seems to result in a solution -- computing $V_{\frac{p+1}{2}}^2$ yields $V_{\frac{p+1}{2}}^2 = V_2 + 2x^{\frac{p+1}{2}} = h^2 - 2x + 2x^{\frac{p+1}{2}}$, which looks almost nothing like the $4x$ I would expect.

This is Cipolla's algorithm, I believe.

The integers mod $p$ we call $\mathbf{F}_p$, and since $h^2 -4x$ is a quadratic nonresidue mod $p$, the polynomial $P(Y) := Y^2-(h^2-4x) \in \mathbf{F}_p[Y]$ has no roots. We can then mod out the polynomial ring $\mathbf{F}_p[Y]$ to get $\mathbf{K} := \mathbf{F}_p[Y]/(Y^2-(h^2-4x))$ (which by some algebra we know is isomorphic to $\mathbf{F}_{p^2}$). It is in this field $\mathbf{K}$ that $h^2-4x$ has a square root (one can think of it as the indeterminate $Y = \sqrt{h^2-4x}$)

In this extension field $\mathbf{K}$ (which is still characteristic $p$, so $(m+n)^p = m^p+n^p$ for all $m,n\in \mathbf{K}$) we have that $\left(h + \sqrt{h^2-4x}\right)^p = h^p + (\sqrt{h^2-4x})^p$.

By Euler's criterion, $(h^2-4x)^{\frac{p-1}{2}} \cong -1 \pmod p$ and Fermat's little theorem $h^p \cong h \pmod p$, and all field operations in $\mathbf{F}_p$ are the same in $\mathbf{K}$ on $\mathbf{F}_p$ elements. Therefore  $h^p + (\sqrt{h^2-4x})^p = h + (h^2-4x)^{\frac{p-1}{2}} \sqrt{h^2-4x} = h - \sqrt{h^2-4x}$.

By now, with all that math we conclude that $\left(h + \sqrt{h^2-4x}\right)^p = h - \sqrt{h^2-4x}$. The same argument also yields $\left(h - \sqrt{h^2-4x}\right)^p = h + \sqrt{h^2-4x}$.

Finally we get to the square root of $x$. Clearly $$4x = h^2 - (h^2 - 4x) = (h + \sqrt{h^2-4x})(h - \sqrt{h^2-4x}) = (h+\sqrt{h^2-4x})(h+\sqrt{h^2-4x})^p = (h+\sqrt{h^2-4x})^{p+1}$$

Now, the $k$th term of the Lucas sequence $V_k := hV_{k-1} + xV_{k-2}$ is $V_k = a^k + b^k$ where $a = \frac{h + \sqrt{h^2-4x}}{2}$ and $b = \frac{h - \sqrt{h^2-4x}}{2}$. So $$V_{\frac{p+1}{2}} = \left(\frac{h + \sqrt{h^2-4x}}{2}\right)^{\frac{p+1}{2}} + \left(\frac{h - \sqrt{h^2-4x}}{2}\right)^{\frac{p+1}{2}}$$

$$V_{\frac{p+1}{2}} = \left(\frac{1}{2}\right)^{\frac{p+1}{2}} \left( (h + \sqrt{h^2-4x})^{\frac{p+1}{2}} + (h - \sqrt{h^2-4x})^{\frac{p+1}{2}} \right)$$

$$V_{\frac{p+1}{2}} = \left(\frac{1}{2}\right)^{\frac{p+1}{2}} ( \sqrt{4x} + \sqrt{4x}) = \left(\frac{2}{2^{\frac{p-1}{2}}}\right) \sqrt{x} = \pm 2 \sqrt{x}$$


security of a block cipher mode of operation Consider the following block cipher mode of operation:
\begin{align}
tag_0 &= mac\:key\\
plaintext_0' &= plaintext_0 \oplus iv\\
E(tag_0 | plaintext_0') = C_0 &= tag_1 | ciphertext_0\\
E(tag_1 | plaintext_1) = C_1 &= tag_2 | ciphertext_1\\
...\\
E(tag_N | plaintext_N) = C_N &= tag_{N+1} | ciphertext_N\\
cryptogram &= tag_{N+1} | ciphertext_0, ciphertext_1, ... ciphertext_N, iv\\
D(tag_N + 1 | ciphertext_N) &= P_N = tag_N | plaintext_N\\
D(tag_N | ciphertext_{N-1}) &= P_{N-1} = tag_{N-1} | plaintext_{N-1}\\
...\\
D(tag_1 | ciphertext_0) &= P_N = tag_0 | (plaintext_0 \oplus iv)\\
\end{align}
$tag_0$ is then validated against the mac key.

An explicit description, which demonstrates using a 128 bit block cipher (i.e AES) and 64 bit tag:

the the first block of a message that is encrypted consists of a mac key,
denoted as $tag_0$, concatenated with the first 64 bits of plaintext
$plaintext_0$ is xor'd with an IV
the block $(tag_0 | plaintext_0)$ is encrypted
the first 64 bits of $ciphertext_0$ are used as $tag_1$ for encrypting $plaintext_1$,
this is repeated for the entire message
The cryptogram consists of the final tag prepended to the ciphertext, and the iv
Decryption is the same process with the messages in reverse order, and
the tag validated against the mac key at the end.

Does the described mode of operation provide integrity and authentication of the plaintext?

Assuming so:

Does it have a name already/is there any established research?
What is the minimum acceptable value for the tag size? My guess is 64 bits.
Too much larger would seem to preclude usefulness with ciphers that have a
block size of <= 128 bits.
With a 128 bit block cipher, performance is 2 two block cipher operations
per 128 bit block of plaintext, which could be better
The number of block cipher operations would appear to become more
efficient with a larger blocksize + longer messages?

The ratio of required block cipher operations per block of plaintext appears
to be given by: \begin{align}blocksize / (blocksize - tag\:size)\\
\end{align}

Edit

Astute commentators have pointed out the construction is similar to the way a
sponge provides authentication. This is certainly not a coincidence! I have
been studying the sponge construct for a while. The tag in the mode of
operation described here fulfills a conceptually similar role as the capacity
of a sponge function does.

No, this mode as listed does not provide integrity of the decrypted plaintext.

An active attacker can flip arbitrary bits from the first 64 bits of the decrypted plaintext freely without causing a decryption failure.  He can do this by modifying the $iv$; the decrypted $tag_0$ will authenticate (because the $iv$ is not used to compute that), and then the decryption process will apply the modified $iv$ to the decrypted $plaintext_0$


Key wrapping - encrypting many times with AES-GCM When encrypting many short plaintexts with a single key, lets say about 2^64 total plaintexts at under 64 bytes each: (edit note - was 2^70 in the original question)

Is there a way to use AES-GCM, as specified by NIST Special Publication 800-38D, safely in this scenario?
Is is safe to use when there are no IV collisions, e.g when the IV is a counter?
Is it possible to use a larger IV while still adhering to the NIST specs, possibly large enough to collisions even with random IVs?

Does this change if the plaintexts are high-entropy, for example when wrapping keys?

No.  You're well above the birthday bound for a 128-bit block cipher.  Using AES under a single key for more than about $2^{64}$ blocks of data is asking for trouble.

The largest nonce you can use with standard AES-GCM is 96 bits,* which is safe sequentially, but you're probably not doing this sequentially unless you plan to wait a millennium for your sequential computer to count to $2^{70}$.  You could carve up the input space and assign disjoint subsets to an array of computers in parallel, but now you have much larger operational security and scaling issues that you almost certainly need to address first, and most likely the way you address those will be by using more than one key anyway.

Your best bet here is to give more details about what you're actually trying to accomplish, rather than ask how to use AES-GCM far beyond its advertised limits.

* Technically you can use >96-bit nonces with AES-GCM, but that's foolish because it is effectively the same as using random 96-bit nonces, and so it is worse than using sequential 96-bit nonces.


What's causing the poor randomness in this program: the LCG, or the program logic itself? (Crypto Gods, I should begin by stressing that I haven't lost my mind: I'm not doing this in real life, I'm just trying to understand the theory behind what's happening. With your help, hopefully I can do that.)
Let's say I choose the parameters for a linear congruential generator $L$, and pick a seed $L_0$. I then use the LCG to generate sequential pseudorandom numbers $L_1, L_2$ for the following program (which, for the sake of argument, picks two different indices in a 52-element array):

$x := L_1 \bmod 52$
$y := (x + 1 + (L_2 \bmod 51)) \bmod 52$

Let's say I choose $m = 8192$, $a = 4801$, and $c = 83$. By looking at the value of $x$, I can learn quite a lot about the value of $y$: for any $x$, there are only about nine or ten possible subsequent $y$s, and they're very unevenly distributed.
Then I tried other values of $a$ and $c$, and got very different results: for instance, $a = 2049$ and $c = 8141$ gives a distribution that produces all possible values of $y$ for a given $x$, and the distribution is much more uniform. It's still poor, but compared to the first set of parameters, it's a huge improvement.
My question is this: what's causing this drastic variation? I initially thought it might be because $m = 8192$, $a = 4801$, and $c = 83$ didn't satisfy the maximum period length theorem, but then I realised that (a) they do, and (b) that would be unlikely to cause this effect on this scale anyway, since I'm only generating two numbers sequentially. Is it some property of the way that the LCG output is being used that leads to this behaviour, or is it intrinsic to the LCG itself? If it's the latter, is there a theorem that states some properties that must hold in order for the joint distribution of $x$ and $y$ to be uniform (as far as possible, given that the program guarantees $x \neq y$)?

Let's say I choose $m = 8192$, $a = 4801$, and $c = 83$. By looking at the value of $x$, I can learn quite a lot about the value of $y$: for any $x$, there are only about nine or ten possible subsequent $y$s, and they're very unevenly distributed.

With a LCG every $L_1$ has a single possible $L_2$, and for a maximal period the reverse is also true. With your formula each $x$ corresponds to about $m/52$ possible $L_1$, and thus $m/52$ possible $L_2$.

The form of the $L_1$ for a given $x$ is $L_1 = x + 52n$, for some $n$. Thus the $L_2$ for a given $x$ is:

$$L_2 = (52an + ax + c) \mod m$$

What you wish is for different values of $n$ to give different $L_2$, i.e. for it to be a decent LCG where $a' = 52a$ and $c' = ax + c$. Substitute $a$ and you get $a' = 3892 = 2^2 \cdot 7 \cdot 139$. For maximal period $a'-1 = 3891 = 3 \cdot 1297$ would have to be divisible by 4 (due to $m$ being), which it is not, so this will give very poor results, as you observe.

If you fixed this, e.g. by choosing another value for $m$, you would also need to consider a condition for $c'$ and how the subsequent modular reductions and addition of $x$ affect it. Also, reducing a random number from the range $0 \le x < m$ modulo 52 will always be biased towards the small numbers unless $m$ is a multiple of 52.


What is 'Carry-forward verification' defense against MITM? Wikipedia article on Man-in-the-middle attack mentions, in the list of defenses against it, some method called "Carry-forward verification", but it does not explain it. I am curious about different MITM defense methods in general. Can someone describe this method or point to description? (Of course googling does not give anything except wikipedia itself with its clones.)

ps. Would be grateful also if someone points me to more elaborated survey of MITM defense methods (and especially for key exchange).

That was a bad edit to Wikipedia.  The phrase Carry-forward verification is not a standard, well-known term in the cryptographic literature.  It should not have been included in Wikipedia without a reference to something more specific.  But oh well, no one is perfect, sometimes these things happen.

Your request for an elaborate survey of MITM defense is most likely too broad for this site; the kind of defenses that are suitable are dependent upon the specific application domain.  You can read up about certificate authorities, web of trust, X.509, certificate pinning, trust-on-first-use (aka key continuity), and many other models.  There's lots written on this topic.


Inverting One-Way Functions One of the conditions that a one-way function has to satisfy is the following:

$$Pr[A(f(x))\in f^{-1}(f(x))] \leq negl(n)$$

Now, suppose that we have the following function that's not one way:
$$f(x) = x + 123$$
We know this isn't one-way since we can easily invert; that is:
$$f^{-1}(x) = x - 123$$
But from the perspective of the adversary, if we have f(1) = 124, it would still essentially "brute-force" its way in order to find the inverse, right? In other words, the adversary would input random x's into f(x) until it finds a solution of 124 rather than formulating an inverse function (like a human normally would).

Is my understanding correct?

As @Cryptostatis commented, Kerckoff's principle dictates that we must consider that the adversary knows the function.

More fundamentally, although the word “adversary” naturally suggests it must be a sentient being such as a human, remember that an adversary is in fact just an algorithm. The algorithm $A$ which on input $x$ returns $x-123$ inverts your function with probability $1$, demonstrating that your function is not one-way. How a human attacker would actually be able to "come up" with this algorithm is irrelevant, what matters is that such an algorithm exists.


Implications of identical round keys in AES (Rijndael) When reading up on the Rijndael key schedule, I learned that the master key itself is used as a round key directly before the key schedule generates additional round keys. When a 256-bit key is used, the first half of the key goes to the first AddRoundKey and the second half goes to the second. This means that, if the 256-bit master key is composed of a single 128-bit value repeated twice, the first and second round key will be the same. I assume the cipher is not designed to remain secure under identical round keys, or there wouldn't be the need to use a key schedule.

Example key schedule test vectors with a 256-bit null key show round keys 1 and 2 are identical:

 key: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

rk01: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
rk02: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
rk03: 62 63 63 63 62 63 63 63 62 63 63 63 62 63 63 63
rk04: aa fb fb fb aa fb fb fb aa fb fb fb aa fb fb fb
rk05: 6f 6c 6c cf 0d 0f 0f ac 6f 6c 6c cf 0d 0f 0f ac
rk06: 7d 8d 8d 6a d7 76 76 91 7d 8d 8d 6a d7 76 76 91
rk07: 53 54 ed c1 5e 5b e2 6d 31 37 8e a2 3c 38 81 0e
rk08: 96 8a 81 c1 41 fc f7 50 3c 71 7a 3a eb 07 0c ab
rk09: 9e aa 8f 28 c0 f1 6d 45 f1 c6 e3 e7 cd fe 62 e9
rk10: 2b 31 2b df 6a cd dc 8f 56 bc a6 b5 bd bb aa 1e
rk11: 64 06 fd 52 a4 f7 90 17 55 31 73 f0 98 cf 11 19
rk12: 6d bb a9 0b 07 76 75 84 51 ca d3 31 ec 71 79 2f
rk13: e7 b0 e8 9c 43 47 78 8b 16 76 0b 7b 8e b9 1a 62
rk14: 74 ed 0b a1 73 9b 7e 25 22 51 ad 14 ce 20 d4 3b
rk15: 10 f8 0a 17 53 bf 72 9c 45 c9 79 e7 cb 70 63 85

Do two identical round keys cause any security issues in Rjndael?

Yes. less data complexity required to retrieve the master key.

Sub-keys can be represented by linear combination. try to xor between 2 consecutive sub-keys, you will find relations.

The paper (Low Data Complexity Attacks on AES) shows in observation 3 (page 8) a relation in consecutive sub-keys that can be exploited.


What is the best mode of operation for file encryption with Threefish512? In Cryptography Engineering Bruce recommends using "rand IV CBC mode" but the copy of the book I have is from 2003 and I am unsure if this is still a recommended practice with all the recent attacks discovered on various CBC implementations.

Is there a better choice then CBC mode?

I am writing a program that will be using a block cipher to encrypt a file locally. This is for a personal academic project.

Assume the following

The block Cipher I am using is Threefish512 so GCM is not viable as it is only defined for 128-bit block ciphers
The block cipher I am using is not supported by any modern crypto libraries (I am aware of) so I will be implementing this mode of operation myself
The file is relatively small and the encryption/decryption of it is only done periodically so security is preferred over speed and parallelization ability
The computer doing the encryption has not been physically compromised
I have access to truly random numbers for IV generation
This encryption will not be part of direct network communications so an attacker will not have access to input whatever they want into the cipher.
A mode that offers authentication is preferred
The details required to implement this mode of operation are in the public domain and not encumbered by any software patents

You should use an authenticated encryption mode.

My personal current favorite is SIV mode, originally introduced by Rogaway & Shrimpton (2006) and standardized (for use with AES) in RFC 5297.

The major advantage of modes based on the SIV construction (such as SIV mode itself, as well as e.g. GCM-SIV) is that, unlike most other encryption modes, their security will not fail catastrophically even if the nonce/IV is accidentally reused.  This eliminates one of the few remaining "weak points" of modern authenticated encryption modes.  CBC mode also has this property to a limited extent, which I believe is the main reason why Schneier's book recommends it, but SIV is much better in that regard, and, as an authenticated encryption mode, also resistant to a much wider range of attacks.

The main disadvantage of SIV mode is that it's a two-pass mode: encryption requires first computing a MAC over the plaintext, and then using that MAC output as a "synthetic IV" to encrypt the data.  If you want to encrypt large files, you may wish to use a "chunked SIV" mode.  There is, as far as I know, (unfortunately) no standard for that, but the basic idea is to:

Split your file into chunks of, say, 1 MB.
Encrypt each chunk using SIV mode, and concatenate the resulting ciphertexts.
For each chunk, include any relevant parameters such as the total size of the file, the chunk size used, the number of the current chunk and, importantly, the "synthetic IV" of the previous chunk as associated data.  (At a minimum, if you don't know the size of the file in advance, each chunk should have as associated data its number, the previous chunk's synthetic IV and a flag indicating whether or not this is the last chunk.)

This "SIV chaining" should ensure that, if every chunk of the encrypted file can be successfully decrypted, this not only guarantees the integrity of the individual chunks, but also of the entire file (i.e. that no chunks have been added, removed or switched around).


Is garbled circuit a post-quantum primitive? I understood garbled circuit can hide some function $f$ jointly by multi parties.
With quantum computer, can we see the circuit inside it?

Garbled circuits are not really a primitive, but more of a protocol.

Furthermore, garbled circuits are generally concealing their semantic values thanks to a cipher such as AES, see this answer to get more details on the whole protocol and the tools it relies on.

So, in order to break garbled circuit, you want to be able to break AES (or whatever cipher used to conceal the values), but the best speed up you might get against AES (and other secure block ciphers) through quantum computer would be thanks to Grover's search algorithm and would be of order $O(\sqrt{n})$, which shouldn't be a problem for AES-256, but could be a problem for AES-128. See also this paper, and its references, to learn more on quantum attacks against AES.

Hence garbled circuits shouldn't really be impacted by quantum computers, even more because you could actually plug a post-quantum cipher (when we got those) in the protocol and keep going.


Can the premaster secret generated by SRP be used as a secure private key? It seems like the pre-master secret generated during the SRP protocol would make a good source to generate a shared private key using a secure hash to compress it down into a 128/256  symmetric key.  The random values that get hashed into it seem to make it good for that purpose.

From the RFC:

  SRP also supplies a shared secret at the end of the authentication sequence that can be used to generate encryption keys.

It seems from my quick look over the RFC that that shared secret is the premaster secret, so you are correct.


How to ensure confidentiality of an encrypted but public message given that computation power increases? Say I encrypt a message with the public key of a party whom I want to contact with and then send the ciphertext over an insecure channel.

Naturally, an adversary who listens to this channel can obtain the ciphertext.
This adversary can simply wait some years for computation speed to increase and then might launch a brute force attack once it becomes feasible.

What methods do we have to prevent such attacks?

This adversary can simply wait some years for computation speed to increase and then might launch a brute force attack once it becomes feasible.

TL;DR: we don't need to protect against brute force attacks because we can choose a key size large enough to withstand those kind of attacks.

Computation speed is often linked to Moore's law. That used to say that the number of transistors / the size of the transistors doubles every two years or so. Moore's law, however, hasn't held for the last 6 years or so and is slowing down (and Intel's 10 nm roadmap is slipping as we speak, slowing it down even more).

Let's assume that computational speed doubles every two years as well. It obviously doesn't as the speed of memory / cache operations doesn't double every two years, but OK. In that case, after 10 years you would gain a speedup of 2 * 2 * 2 * 2 = $2^5$. That means that an AES-128 bit key would be $2^5 = 32$ times easier to break. You could say that AES would not offer 128 bits of security but 123 bits of security because ${2^{128} \over 2^5} = 2^{123}$. However, 123 bits of relative security is still plenty to disallow brute force.

There are other physical limits that prevent brute force, for instance, power requirements to perform the calculations. It requires 1/100th of the power consumption of the world to attack a 128-bit symmetric key, if each try uses the absolute minimum of energy required to perform the calculation. You'd better have a nuclear fusion reactor sitting next to your CPU.

So does that mean that - for instance, 128 bit AES - is enough for the foreseeable future? Not necessarily.

First of all, a fully operational quantum computer, with enough reliable, interconnected qubits, could use Grover's algorithm to bring down the security strength to $2^{64}$. Although such a quantum computer is still a very distant possibility it could be that such a QC would be fast enough to perform that many operations. You should switch to AES-256 if you're afraid of this situation. However, this won't work for many asymmetric ciphers such as RSA. You would need to switch to another algorithm that protects against attacks using quantum computers; so called post-quantum cryptography / PQC.

Furthermore, neither AES nor RSA cannot be proven to be secure. So it is theoretically possible that an attack on AES can be found that allows attacks that are faster than brute force (and do not use impossible amounts of memory). In that case, AES-128 and even AES-256 could become insecure. Fortunately, these algorithms have withstood years of attacks and we know much more about cryptography and crypt-analysis than we did in the entire human history, so finding an attack will be very hard.

Then again, modern crypto has only existed for about 50 years and many algorithms have been broken (let's assume 1970 or so to be the emergence of publicly available crypto) so it might be wise to assume that crypt-analysis will advance even more. Crypto is a relatively new field after all.

Practically speaking you may just want to monitor the advisories on key size of the different agencies in the world. One website that does this is https://keylength.com and it helpfully links to the documents issued by the agencies themselves.

Or you could go all the way and implement quantum-based key establishment and use a one-time-pad to encrypt your messages. This is provably secure against brute force attacks. It's very cumbersome though, and initial implementations fell quite ungracefully against side channel attacks.


Unbalanced Feistel network function I am trying to understand how an unbalanced Feistel network works. I came across this image:
It says that the function takes $b$ bits to $y$ bits. Which works on the first step, however clearly doesn't on the next one.
What am I not getting?
If you always apply the function to the side with $b$ bits would that break the cypher? I am guessing it does.

Let formalize it

Round function $R:\{0,1\}^b \to \{0,1\}^y$ (This is bad naming, $F$ was better here as in DES)

Input to each round is $b+y$ bit register/array $I$.

Output of each round $O = (R(\texttt{MSB}(b,I)) \oplus \texttt{LSB}(y,I)) \mathbin\| \texttt{MSB}(b,I)$

Therefore $O$ is again $b+y$ bits register/array as an input to next round.

$\texttt{MSB}(b,I)$ the Most Significant $b$ Bits of register $I$.
$\texttt{LSB}(y,I)$ the Least Significant $y$ Bits of register $I$.

Example
Let $I=\texttt{[0,1,1,1,0,1,0,0,1,0,0,1,1,0,0,1]}$ be 16-bit register then

$\texttt{MSB}(3,I) = \texttt{[0,1,1]}$, and
$\texttt{LSB}(12,I) = \texttt{[1,0,1,0,0,1,0,0,1,1,0,0,1]}$

Note that here we used binary representation for $I$, not the array repsentation.


Reduction to the discrete log problem Let $G$ be a group of prime order $p$ and generator $g$.
Let $msk_i = (x_i, y_i) \in Z_p^2$ be two master secret keys and $mpk_i = (g^{x_i}, g^{y_i})$ the corresponding master public keys, $i \in [0, 1]$.
Let $dpk = g^{x_i} \cdot g^{H(y_i)} \in Z_p, i \in [0, 1]$ and $H$ is a hash function, be a derived public key from one of the master public keys.
We want to know if $dpk$ is derived from the first or the second master public key, i.e., if $i=0$ or $i=1$. This problem is equivalent to the discrete logarithm problem, right? How can I make the reduction?

This problem is equivalent to the discrete logarithm problem, right?

As written, the problem is informationally secure; that is, you haven't given enough information for anyone (even a computationally unbounded adversary) to solve it.
Here is a simplified version of the same problem: I am thinking of two numbers; one of them is 42; is that the first number I'm thinking of, or the second?
I suspect that you're giving the adversary more information (and whether the problem is reducible to DL would depend on what that more information is)

Update (now that you have revised the question): it's fairly obvious that your problem is no harder than DL (that is, with a DL oracle, it is straight-forward to solve your problem).
Going back the other way, it would appear to depend on what the hash function $H$ is.  For example, if $H(x)$ is defined to be the lowest bit of $x$, that is, $x \land 1$ (which is stretching the definition of hash function a bit), then an Oracle that solved your problem with that specific $H$ could be used, given $g^z$, to recover the lsbit of $z$ (by passing the public keys $(g^1, g^z)$, $(g^0, g^z)$, and $dpk = g^1$); given an Oracle recovering the lsbit, it's straight-forward to read off the bits of $z$ sequentially.
On the other hand, if $H$ is constrained to be a real hash function (say, SHA-3), it's far less clear how such an Oracle could be used.  One issue is that, when you submit a query to the Oracle, $dpk$ is constrained to correspond to one answer or the other; given that you have no knowledge of $z$, you can't compute a reasonable guess of $H(z)$ (or $H$ of any nontrivial linear function of $z$), and there is no other obvious way to proceed.
Now, given that the protocol is secure (assuming DLogs is hard) for the silly $H(x) = x \land 1$, it sounds plausible that it's also secure for $H(x) = \text{SHA3}(x)$; however it wouldn't appear we know how to prove that.


Single-scalar multiplication with sign bit I want to know if there's an "easy" timing-free way to compute the sign of $y$-coordinate of $r G$, for a secret scalar $r$ and $G$ the generator of an elliptic curve.

We have several choices for scalar multiplication: 1) use a Montgomery ladder, which provides the $x$-coordinate, but tells you nothing about the $y$-coordinate; and 2) other methods such as multiply-and-add on the Edwards curve.

Montgomery ladders are lovely, because it's not too hard to get something which is pretty safe against timing attacks, so for ECDH it's an obvious choice. However, signature schemes require that you know the $y$-coordinate, which leads to very fiddly implementation requirements, like timing-free table lookups for windowed scalar-mul.

My question is whether there's a middle choice: using Montgomery for the $x$-coordinate, and some other method to obtain the sign of the $y$-coordinate, which can then be used by the verifier, avoiding the need to implement a timing-safe double-scalar-mul operation. I'm thinking of some kind of "differential sign-only" operation on the Montgomery curve.

In particular, I'm aware that the choice of "sign" is arbitrary: any half-sized subset of $Z_p$ can be designated as the "positive" set of $y$-coordinates. With this free choice of definition for the sign, is there a choice which makes the sign of $r G$ easy to determine, using a "simple" algorithm?

Using $x$-coordinates only, given a point $G = (x_0,y_0)$ on an elliptic curve $y^2 = x^3 + ax + b$ and a scalar $r$, the Montgomery ladder outputs the $x$-coordinate of $rG$.  However, a closer look at the algorithm shows that the other accumulator used in the computation contains the $x$-coordinate of $(r+1)G$.  Letting $x_1$ the $x$-coordinate of $rG$ and $x_2$ the $x$-coordinate of $(r+1)G$, we have that

  $y_1 = \dfrac{2b+(a+x_0x_1)(x_0+x_1)−x_2(x_0−x_1)^2}{2y_0}$

is the $y$-coordinate of $rG$.  Given $y_1$, its sign can readily be obtained.

See e.g. Éric Brier and Marc Joye, Weierstraß elliptic curves and side-channel attacks. In D. Naccache and P. Paillier, Eds., Public Key Cryptography, vol. 2274 of Lecture Notes in Computer Science, pp. 335-345, Springer-Verlag, 2002.


ECFP harder than ECDLP? Given two points $P$ and $Q = \sum_{i=1}^{n} x_i.P$ over $E_p(a, b)$ for $x_1,x_2,...,x_n \in \mathbb F_p$. The Elliptic Curve Factorization Problem (ECFP) is to find the points $x_1.P,x_2.P,...,x_n.P$

Is ECFP harder than ECDLP ? Can anyone provide me the proof ?

It's not harder.

Solve the DL problem to get $x$ in $Q=x.P$.
$Q = \sum_{i=1}^{n} x_i.P = (\sum_{i=1}^{n} x_i).P= x.P$

=> any set of $x_i$ that sums to $x$ (modulo the group order) is a solution to ECFP.