Is multiple hashings of a cryptographic hash function an acceptable way to increase complexity? Is nesting/re-hashing a viable way of slowing down a fast cryptographic hash function (such as SHA-256) to slow down brute-forcing attacks on shorter passwords? The use of longer passwords would of course be ideal, since it would lead to an exponential growth in brute-force difficulty, but is the use of multiple rounds an acceptable way of achieving linear growth in computational cost?

suppose an example: SHA256(SHA256(password)) would be twice as computationally expensive as SHA256(password), and so, a function with a difficulty parameter could be defined as:

function hash(String password, int difficulty)
{
String result = password;
while(difficulty >0)
{
result = SHA256(result);
difficulty--;
}
return result;
}

Are there any security risks/weaknesses with this approach? thanks.

Iterating a hash function such as SHA-256 does raise the cost of brute-force preimage attacks to recover passwords from password hashes, and in fact this technique appears in most password hash functions, usually with some variation in the input to the hash function in each iteration.  See, for example, PBKDF2 for a widely used password hash function that does only this.

However, it does not exponentially increase the cost of a brute force preimage attack.  It only linearly increases the cost, because if you iterate SHA-256 2x instead of 1x, the attacker must do 2x as many SHA-256 evaluations.

The cost here is measured in the area*time product of an attack, not how long an attack takes in wall clock time: an attacker with $2n$ CPU cores can compute an attack on 2x-iterated SHA-256 in the same time an attacker with $n$ CPU cores can compute an attack on 1x-iterated SHA-256.  To attack your iterated SHA-256, a smart attacker will buy computers with many CPU cores on a die to attack hashes in parallel, e.g. with GPUs or custom ASICs.  This is essentially what Bitcoin miners do.

The cost factor you can impose on the attacker by this method is bounded by the time you're willing to wait for your CPU to compute the password hash function once.  But there's another way you can impose cost on the attacker, which is by making the password hash require a lot of memory as well as time.  Area on the die dedicated to memory can't be used to attack multiple passwords in parallel like area on the die dedicated to extra CPU cores can.

Sequential memory-hard password hashes were introduced in scrypt to force attackers to spend either a linear amount of memory or (say) a quadratic amount of time to compute the same function you compute.  Since on your laptop or phone you typically have gigabytes of memory available, you can easily spend a lot of it to evaluate a single password hash in a tolerably short time.  This is how modern password hashes such as scrypt and argon2 work to raise the cost for an attacker without hurting legitimate users.


Why do memory-hard functions rely on a time-space trade-off? I was reading about memory-hard functions recently. In those papers I read, they almost always introduce a time-space trade-off like this:

$$
S(n) \times T(n) \in \Omega(\mathrm{Poly}(n))
$$

I understand memory-hard functions are trying to impose heavy memory usage to counter ASIC attacks. But I don't understand why heavy memory usage must be measured with a time-space trade-off.

There are problems proven to be memory-heavy (at least the most memory-heavy in its class). Search PSPACE and EXPSPACE will return a list of results.

Computational complexity tells us that if a problem requires a lot of memory to run, then it also requires a lot of time to run. Wouldn't these problems be better used as memory-hard functions than those with a time-space trade-off?

In order to create such a function you fill up memory with results of some computation; the memory-hard function then reads these values to further the computation later on.

Rather than saving the values, one could theoretically re-calculate them when needed. So the memory is not really a hard requirement. The memory hard functions are however build in such a way that they require much more computation without memorization of the intermediate values. This is the time / memory trade off.


Example of a cut-and-paste attack on CBC I am reading the cryptography book by Stamp and there is a cut-and-paste attack on $ECB$ and this is easy to follow because $ECB$ is relatively simple, the problem is that I would like to see an example of this in $CBC$ mode. Is there an easy example to show this?

Attacking CBC is much harder than ECB. In many cases there is no viable attack. Properly implemented CBC with a secure underlying block cipher is secure.
There have been successful attacks against padding in CBC, though non were anywhere as simple as attacking ECB.
Look at: https://en.wikipedia.org/wiki/Padding_oracle_attack
https://en.wikipedia.org/wiki/POODLE

There are also attacks on implementations of CBC with predicatble IVs e.g:
https://www.netsparker.com/blog/web-security/how-the-beast-attack-works/

CBC has lost favor not because it is insecure in itself but because it is easy to implement poorly and there have been many attacks. If you expect anything remotely as simple as attacks on ECB I am happy to inform you these do not exist nor are expected.

Edit: I seem to have missed the point of the question, it was about manipulating cipher text.
CBC is probably the least malleable of the common block cipher modes(harder than ECB or CTR) and yet without a authentication of some sort a MAC, or GCM or such CBC can still be manipulated, specifically if you have wiggle room and are willing to create a junk plain text block at your cut and paste boundary. If you know the plain text of a given block, you can replace it with a plain text of your choice by manipulating the previous cipher text blcok. calculate the xor diff between current plain text and desired plain text and apply it to previous cipher text block.
This will cause the previous block to decipher into gibberish and the target blcok to be deciphered into whatever you want.


Implementation of oblivious transfer with symmetric primitive? I'm now reading this paper Extending Oblivious Transfers Efficiently. I understand how to reduce an OT cost.
OT extension is a method that replaces an OT with many base-OTs.
But I'm still not sure how to implement each base-OT.

How is this possible?
Any references?

I prefer more recent construction.

You can take a look at LibOT, which is a C++ implementation of several OT extension protocols.
In the Readme you can find a list with many base and extension Oblivious Transfer protocols.

A protocol that people use a lot is the Simplest OT (although it was announced that the security proof has a bug by one of the authors at the TPMPC2018 workshop).

Another popular option is PVW, the protocol by Peikert, Vaikuntanathan and Waters.
It has two variants.
One DDH-based and another LWE-based.
The first one is particularly easy to understand and implement.


Signature Generation Time vs Verification Time When comparing the RSA-PSS signature algorithm with an elliptic curve based algorithm such as EdDSA, it is clear that signature verification takes less time for RSA than for EdDSA. For signature generation the situation is vice versa. I am asking myself whether there are use cases were a fast signature verification is an important requirement and were RSA would be actually the preferred choice?
Remark: I know that these elliptic curve based algorithms are generally more secure and have shorter keys then EC based algorithms. Thus, from these perspectives, EdDSA would be more appealing.

I am asking myself whether there are use cases were a fast signature verification is an important requirement and were RSA would be actually the preferred choice?

Well, as you already mentioned the comparison is a bit tricky. For 128 bit security you'd use ECC-256 and RSA-3072 (and using 3072 is on the low end). For most RSA implementations 3072 seems at the high end.
However, the main place where quick verification is important in PKI. Generation of signatures below certificates is generally only performed once, while verification of certificate chains happens all the time. Generally you'd try and cache verified / trusted certificates, but remember that all receivers (such as browsers) must initially verify the certificates none-the-less.
Note that smart cards also may use a PKI using more simplistic Card Verifiable certificates. For smart cards the smaller ECC keys and signatures are an important factor: both IO and RAM is usually limited. So in that case ECC may be more efficient than RSA. There are often other properties than raw CPU time to consider.


Formal security of recycled random blinding in a Paillier scheme This question is a follow-up/variant on a previous question.

Supposing that we are trying to generate a large number of (indistinguishable) ciphertexts of a given plaintext and want to avoid the costly exponentiation of standard re-encryption:

$c \gets c \cdot r^n \mod n^2$ (with $r \in \mathbb{Z}_n$ random)

We could pre-compute a large pool of exponentiated values $r_i^n, i=1...p$, then for each re-encryption, take the last re-encrypted ciphertext and multiply it by $k$ randomly chosen $r^n_{\sigma(1)}, ..., r^n_{\sigma(k)}$.

What would be the security (both practical and theoretical) of such a method?

The size of ${p}\choose{k}$ for manageably high values (say $p = 1000$ and $k = 20$) makes the odds of two blinding random variables $R = \Pi_{i=1..k} r_{\sigma(i)}$ being equal, negligibly low in general (and even more so if we only consider successive pairs of such values).

An attacker could possibly raise their chance of finding a collision by comparing every possible products of the resulting ciphertexts together, but even assuming all ciphertexts available to them are indeed generated from this method and setting aside the very large computing cost, the chances of any two products being equal still seem negligibly low.

Am I missing any other possible attack vector? Does a formal security proof seem achievable?

Edit: Possible proof outline

Estimate (comparatively small) chance of accidental collision between $R^{(i)}(c)$ and $R^{(j)}(c')$, respectively $i^{th}$ and $j^{th}$ re-encryption of ciphers $c$ and $c'$ (maybe treating separately cases $c = c'$ and $c = c'$).
Estimate chance of accidental collision between any two products of $R^{(i)}$: $\Pi_{i = 1...m} R^{(a_i)}$ and $\Pi_{j = 1...n} R^{(b_j)}$, which requires:

$\{a_i\}_i \cap \{b_j\}_j = 0$ (any case where that is not true could be reduced to the previous case)
$\Sigma_i a_i = \Sigma_j b_j$

The main part would therefore be to compute the number of $a_i$ and $b_j$ verifying conditions 1 and 2, given a maximum number of re-encryptions $s$ of a maximum total number of plaintexts $t$. This seems achievable.

Does that seem like a sufficient proof, however?

Edit 2: Actually, condition 2 above could be made even stronger. If we note $r^(i)_1, \dots, r^(i)_k$, the $k$ random values selected by the $i^{th}$ re-encryption, for a collision to be more likely than between two random values, we must have:

$\{r^{(a_1)}_1,\dots,r^{(a_1)}_k,r^{(a_2)}_1,\dots,r^{(a_2)}_k,\dots,r^{(a_n)}_k\} = \{r^{(b_1)}_1,\dots,r^{(b_1)}_k,r^{(b_2)}_1,\dots,r^{(b_2)}_k,\dots,r^{(b_m)}_k\}$

Proof ad absurdum: if there is one value $r^{(i)}_j$ in one set but not the other, then the product of the values in that set is $C * r^{(i)}_j$, with $r^{(i)}_j$ statistically independent from the other set and, for all purposes the two sets are statistically independent.

Edit 3: in all the above, it would probably make computations easier to use a draw with replacement instead (and therefore consider $n^k$ combinations instead of $n\choose k$).

You have to worry not just about a pair of blinding values being equal, but more complex relationships between them.  Thus, finding a proof of security for this approach looks non-trivial to me.

Let me elaborate.  Suppose $R_j$ is the $j$th blinding variable you use.  If $R_i = R_j$, that's a problem, but as you say, that can be made very unlikely.  However, that's not the only potential problem.  If there exist indices $a,b,c,d$ such that $R_a R_b = R_c R_d$, then you might also have a problem, and this happens with higher problem.  At least, this will be a difficulty for a proof of security, as this relationship is detectable by an adversary and allows some kinds of distinguishing attacks.  If you make $k$ and $n$ large enough, you can rule out even this kind of multiplicative relationship, but you might still have to worry about higher-order multiplicative relationships, and it's not entirely clear to me how you'd address this challenge.

Perhaps you can deal with this somehow and prove something with some additional insights, but I think the above phenomenom will be a non-trivial complication.

You subsequently revised the question to propose a proof strategy.  Your revised proof strategy won't work.  It requires showing that there's unlikely to be a collision between products of the $R$'s.  However,  you won't be able to show that, because it's not true: if you consider products of very large size, it's overwhelmingly likely that some such collision does exist.  You can't avoid that by choosing $k$ and $n$ to be larger.  So, the proof strategy you suggest in the revised question isn't going to work.  This is more delicate than you might have realized, and it's not clear to me how to prove that your idea is secure (or whether a proof is possible).


Deterministic encryption for a limited space: using HMAC as IV I need a deterministic encryption scheme. Objectives:

Same plaintext is always encrypted to the same ciphertext.
Related plaintexts are encrypted to unrelated ciphertexts. (For example, attacker that knows two ciphertexts cannot learn whether corresponsing plaintexts start with the same prefix.)
Minimum space overhead.
Authenticated encryption, of course.

There are also some conditions that can make it easier:

I will encrypt small chunks of data (few dozens of bytes). It is OK to store them in RAM and then start the encryption.
The data will be padded to the same length all the time. So, we can conclude that the length of the data is some constant.
Not high performance requirements.

My first idea was to derive IV from plaintext using HMAC and then use some authenticated encryption that requires just unique (potentially predicable) IV, like AES-GCM. This requires both IV and authentication tag to be stored alongside the encryption.

But I have an idea how to reduce the space overhead even more: Use (H)MAC of plaintext as both IV and authentication of the message. I know this is generally dangerous scheme close to encrypt-and-mac, so I specify further requirements for primitives to mitigate its risks:

The encryption will not leak anything when decrypting attacker-manipulated data. Stream ciphers like AES-CTR look suitable here, because there are no risks related to padding oracle. It just “decrypts” any attacker-provided garbage to another garbage (rejected by MAC check later) without any side channel if the AES-CTR implementation is correct.
The encryption requires just unique IV, but it does not have any other requirements. Thill, AES-CTR looks suitable here.
The MAC does not leak any data. HMAC (potentially truncated to 128b) looks suitable there, because failing to do so would at least weaken preimage resistance of the underlying hash function.
Encryption uses a key completely unrelated to authentication key, of course. (This requirement might not be strictly needed when using, say, AES-CTR with HMAC-SHA256. However the requirement makes reasoning about security easier.)

The whole schema looks somewhat exotic to me, but I believe that I have resolved risks arising from the unusual design.

Is there any existing work that aims to do the same? Is there any research that would tell me anything about security of this scheme?

Let L be your constant data length, choose a non-negative integer $\sigma$, choose a

FPE scheme over strings of length $\sigma$+L, and have $s$ range over strings of length $\sigma$.

encrypt$\hspace{-0.02 in}\big(\hspace{-0.04 in}\langle k\hspace{.02 in},\hspace{-0.03 in}s\rangle ,\hspace{-0.02 in}m\hspace{-0.03 in}\big) \;\;\;\; = \;\;\;\; $ FPenc (  k  ,  s || m  )

Decryption of c with $\langle k\hspace{.02 in},\hspace{-0.03 in}s\rangle$ is as follows:

if  length(c) ≠ $\sigma$+L  then output $\bot$, else set  d = FPdec(k,c)

if the left $\sigma$ bits of d are s then output the right L bits of d, else output $\bot$

Security should hold even if the adversary chooses $s$; you making it part of the key (in particular, random and secret) might reduce the impact of an attack on the underlying FPE scheme.

Depending on your use-case, you may be able to support a tweak.  The right FPE scheme depends on how 2$^{\sigma+L}$ compares to your upper bound the number of distinct [queries which are not just the opposite direction to an earlier query] (for any single tweak, if applicable).

The  low-query , medium-query , high-query  regimes are handled by

Generalized Feistel , swap-or-not , sometimes-recurse shuffle  respectively.

(I don't know whether-or-not they mention tweakability, but there's a simple generic

way to make any encryption scheme tweakable, which I can describe if you'd like.)

The main reason for using FPE rather than just a MAC is that

it essentially removes the adversary's control over the effects

of a successful forgery (thus perhaps allowing a shorter tag).

For example, with AES-CTR on a known plaintext, the adversary can

choose exactly what the decryption result will be if they guess the right tag.

A much-less-important reason is that forgery probability is in

fact slightly lower, since the guesses are nearly-independent.

Should I formalize either of those things?

If your scheme can be stateful, then you can further make it so that after any

attempted altering of what's sent (whether it's a replay or a re-ordering or just

a fresh cipher-block, and whether-or-not the attempt succeeds at forging),

[decryptions after the decryption of the initial tampering]

are indistinguishable from being independent with

$\big[\big[$probability  $1\hspace{-0.05 in}-\hspace{-0.03 in}\left(1/\hspace{-0.03 in}\left(2^{\sigma}\right)\right)$  of outputting $\bot \big]$    and

$\big[$probability $1/\hspace{-0.03 in}\left(2^{\sigma}\right)$ of outputting a random L-bit string$\big]\big]$ .

Should I explain how to do that?


Attacks on the RSA Cryptosystem I was reading some articles about attacks on RSA system and I wonder about some generalization of the following theorem.

  Theorem (Coppersmith).

  Let $N=pq$ be an $n$-bit RSA modulus, where
  $p<q<2p$. Then given the $\frac{n}{4}$ least significant bits of $p$
  (that is $\approx$ half of LSB of $p$) or the $\frac{n}{4}$ most
  significant bits of $p$ (that is $\approx$ half of MSB of $p$), one
  can efficiently factor $N$.

I wonder what is going on, if we know for example $\frac{n}{8}$ MSB of $p$ and $\frac{n}{8}$ LSB of $p$.

Second idea, what is going on, if we know for example $\frac{n}{8}$ MSB of $p$ and $\frac{n}{8}$ LSB of $q$.

Is it enough for factoring $N$ in effective way? Or maybe with some other numbers instead of pair $(\frac{n}{8}, \frac{n}{8})$ (of course assuming, that both numbers are greater than $0$ and less than $\frac{n}{4}$)? Was there some research in this field?

Yes, what you have is enough to recover p in both cases.

In the first case you just need to write the proper equation to be then solved thanks to Coppersmith method to find small roots of univariate polynomial.
As explained by Alexander May in pages 40 and 41 of his thesis what you ask is always doable if the unknown bits are consecutive (and you have at least $\frac{n}{4}$ known bits).

You just need to write the correct polynomial and let Coppersmith's method find the solution. The preconditions to using Coppersmith's method are:

$f_p(x)=0 \pmod p$ at the point we want to evaluate (i.e., for the middle bits).
$f_p(x)$ is monic (i.e., the leading coefficient of $f$ is 1).

First, let's start writing $p$ in terms of $x$. Let $MID(p)$ represent the middle bits of $p$. So $p = MSB(p) + MID(p) · 2^{n/8} + LSB(p)$**. Now let's rewrite this as a function of $x$. Let $g_p(x) = MSB(p) + x · 2^{n/8} + LSB(p)$. We have to make this function monic. To do this, we can multiply $g_p(x)$ by $(2^{n/8})^{-1} \mod N$. We can't do it $\mod p$ since we don't know how to compute inverses $\mod p$ as $p$ is unknown. Ok, so let's rewrite our functions,

$$
f_p(x) =g_p(x)(2^{n/8})^{-1} \mod N = x + MSB(p)\cdot (2^{n/8})^{-1} + x + LSB(p) (2^{n/8})^{-1}
$$

Now all that's left before computing Coppersmith's method is to check that $f_p(MID(p))=0 \mod p$.

$$
f(x)=MID(p)+MSB(p)(2^{n/8})^{-1}+LSB(p)(2^{n/8})^{-1}=p(2^{n/8})^{-1}
$$

Note that this can be rewritten as: $pC$, and any number multiplied by $p$ in $\mod p$ is $0 \mod p$ i.e., $pC = 0 \mod p$.

I successfully tested a solution for the problem you described using sage, the solution is available here.

In the second case, as poncho pointed out, it is trivial to recover the $LSB(p)$ knowing the $LSB(q)$, just note that: $LSB(p) = N * LSB(q)^{-1}\bmod{2^{n/8}}  $

In case your unknown bits of p are not consecutive, then it's not so easy and you probably will need more bits: see this paper by Herrmann and May that basically states that $log(2)n \approx 0.7n $ bits of $p$ are always enough to solve the equation but the complexity is exponential in the number of different not consecutive unknown bit blocks.

** I left the notation in terms of MSB(p) to be consistent with the first author for this answer, but I think showing that the preconditions for applying that Coppersmith hold is easier when we think of the MSB(p) as the bit values shifted by some $2^{n/k}$ where $k$ is some constant. This notation can be seen in referring to the middle bits $MID(p) \cdot (2^{n/8})$.


Vector dot product in Microsoft SEAL using the CKKS scheme I'm trying to use the Microsoft SEAL library in order to do Matrix multiplication. That's why I'm trying to find a way to compute the Dot Product of 2 vectors.

My issue is that the CKKS encoder in SEAL encodes entire vectors. So if I had a 2D vector of floats I get a 1D vector of Plaintext (and then a 1D vector of Ciphertext after encryption).

The operations that I am able to do are: addition, component-wise multiplication, exponential, and rotation. In order to do a dot product of vectors I need to multiply the components of the first vector by the components of the second vector and sum them up. If I want to multiply 2 matrices, I can transpose the second matrix and multiply the rows together but I am unable to compute the sum of the elements inside the Ciphertext. Is it possible to get the sum of those elements in the Ciphertext? Should I change my approach?

As suggested by Hilder Vitor Lima Pereira in the comments and KyoohyungHan on Github in the issue https://github.com/microsoft/SEAL/issues/138, it is possible to sum the elements with rotations:

  For example,
  {1, 2, 3, 4} is encrypted in a ciphertext.
  You can get encrypted {3, 4, 1, 2} using homomorphic rotation by index 2.
  With homomorphic addition, you have encrypted {4, 6, 4, 6}.
  After that, you can get encrypted {6, 4, 6, 4} using homomorphic rotation by index 1.
  Finally, you have encrypted {10, 10, 10, 10} with homomorphic addition which is the sum of the element in a ciphertext.


Verifiable computation on signed data Consider the following setting.

Alice receives a chunk of data from Victor, together with a cryptographic certificate of authenticity of some sort (eg hash signed with Victor’s private key).

Bob now wants to know the result of some computer program applied to the data. Alice is not willing to disclose the raw data to Bob, but is happy to perform the computation herself and send him the result. The program was not known at the time Victor certified the data.

Is there a scheme that will allow Bob to verify that the computation was in fact performed as agreed, on the data certified by Victor?

One of the many verifiable computation schemes would be the way to go.

Something like zkSNARKs would allow a prover, Alice in this case, to prove that she performed a computation correctly without revealing the inputs to her function. These schemes require Alice to initially send a commitment of her input to the verifier. In your setup, the chunk of data Victor signs may be a commitment to the original data he sent.

To learn more about zkSNARKs, I recommend the already linked Winter School, as well as the following primer provided by Zcash: https://z.cash/blog/snark-explain.html.

Edit Just encountered this work that is relevant: ADSNARK: Nearly Practical and Privacy-Preserving Proofs on Authenticated Data (https://eprint.iacr.org/2014/617)


Should I use independent symmetric keys for each client should I use keys derived from a master key? I have several clients that I communicate with from a central location. All connections are encrypted using static symmetric keys that are hard-coded in each client config file. I use a different key for each client because it is possible that someone gains access to the key of a client. In that case I want the attacker to be unable to access connections established by other clients.

Until now I was creating client keys manually by typing characters at random on my keyboard. I thought creating keys manually is not a good idea because in addition to being tedious it is error prone and somewhat insecure. So just now I was writing a key generator program that creates random keys for me.

But in the meanwhile another idea hit my brain: I can have just one master key and derive all client keys from it! For example suppose my master key is '123456', I can derive the first client key like this:

SHA256('123456'|'client1')

Is that OK?

Is it better to continue writing my key generator program and use separate and completely independent keys for each client or is deriving all keys from a master key acceptable?

Whatever approach I use, I need all client keys at a central controller  location, so if an attacker gains access to this central location he has all the keys anyway, thus seems there is no advantage to using independent random keys for me.

P.S.: My master key is not something like '123456'; It is really/sufficiently strong!

Yeah, sure, you can derive keys from a master key. This is often performed for schemes using symmetric encryption primitives. And yes, including the ID of the client is generally the way to do this.

SHA-256 is not a brilliantly secure KDF - but in general it will do. You'd better use a real Key Based Key Derivation Function though. Currently HKDF is all the rage, which uses HMAC underneath. HMAC in turn can be configured using a secure hash such as SHA-256.

When starting from a secure master key you can directly use HKDF-expand (skipping HKDF-extract) where available.

Note that transport security requires extra care. In general you may want to bold on perfect forward secrecy (ephemeral Diffie-Hellman) or other key derivation techniques that create session keys from your client keys. You may also need a form of authenticated encryption using HMAC or an authenticated cipher such as AES-GCM.


Explain the 'Breaking 104 bit WEP in less than 60 seconds' paper Could you explain the 'Breaking 104 bit WEP in less than 60 seconds' paper, without skipping too much technical details.

Could you an answer questions, like: how is '1.24/256' a significant difference compared to '1/256'? And how this seemingly small difference could lead a '104-bit WEP key' to a reduced required computational effort that is approximately 2^20 RC4 key setups.

'The algorithm is based on the following ideas. Andreas Klein, a German researcher, showed that there is a correlation in RC4 between Keybytes 1 to i-1, the keystream and the keybyte i. If the keybytes 1 to i-1 and the keystream are known, it is possible to guess the next unknown keybyte with a probability of about 1.36/256 which is a little bit higher than 1/256. We were able to show that it is also possible to guess the sum of keybytes i to i+k with a probability of more thatn 1.24/256.'

According to the paper, it takes up to 53 seconds for enough data to be transferred for the attack to be attempted. Then it takes 1-3 seconds with 50% probability on a 1.7 GHz Pentium-M to perform the crack (presumably this actually means between 1 and 6 seconds for 100% probability?).

I would do a back of the napkin calculation how long the same attack would take against a "proper" wifi network using the same hardware (or even better, on a laptop with a decent GPU for 3D games), and then say something like this:

"It takes less than 60 seconds to crack WEP and X years to crack WPA with a 12 digit password."

I would not say anything like "104 bit" or go into properly long alpha-numeric passwords because you'll just confuse people with stuff like that. It's bad enough you even need to tell them that "WEP" and "WPA" are different, you already lost some people by mentioning two acronyms they've never heard of.

I would sum it up by also saying:

"WEP was designed by idiots. WPA was designed by experts."

Which is a bit harsh on the WEP guys but is basically true. They probably had no idea how insecure their protocol was until long after everyone started using it (to be fair, security wasn't really their goal either).


Distinct MAC and Key for AEAD? I am implementing some of the algorithms in RFC 7518 and I noticed that AES_CBC_HMAC_SHA2 contains the following paragraph:

  The secondary keys MAC_KEY and ENC_KEY are generated from the
     input key K as follows.  Each of these two keys is an octet
     string.

  MAC_KEY consists of the initial MAC_KEY_LEN octets of K, in order.
  ENC_KEY consists of the final ENC_KEY_LEN octets of K, in order.

  The number of octets in the input key K MUST be the sum of
     MAC_KEY_LEN and ENC_KEY_LEN.  The values of these parameters are
     specified by the Authenticated Encryption algorithms in Sections
     5.2.3 through 5.2.5.  Note that the MAC key comes before the
     encryption key in the input key K; this is in the opposite order
     of the algorithm names in the identifier "AES_CBC_HMAC_SHA2".

Why would the encryption key be different than the MAC key? The examples I see in wikipedia show that the same key is used for both.

My understanding is that because in JWE only the message is authenticated, it means that the key is available for tempering and since the MAC key and the MAC are in a known location, it should be possible to forge messages.

Am I incorrect in that assumption? Why did the RFC authors chose to split the keys instead of reusing it?

The examples I see in wikipedia show that the same key is used for
  both.

Doing so is fine in most constructions, however "most" is not "all". Also the graphics could be read as "derive a key from the given input key somehow".

  Why would the encryption key be different than the MAC key?

Cryptographically speaking, it's cleaner to use different keys for the different primitives, as it definitely prevents subtle interactions due to the key-reuse and thus makes formal proofs about security claims easier.

Also there are cases where you actually have to use different keys for the MAC and the encryption scheme, the most well-known example being the combination of CBC and CBC-MAC which allows for modification of (nearly) the whole message on key-reuse.


What are the major advantages of SPHF for PAKE? I am working on Password Authenticated Key Exchange (PAKE). I noted some PAKE schemes were built upon the smooth projective hash function (SPHF). I am confused why SPHF can be used to design PAKE?

I can understand the definition of SPHF and I know it is a special case of designated-verifier ZK. But what are the main advantages of SPHF for PAKE?

SPHF are a very versatile tool, and they have a large number of applications. Their application to PAKE stems from three main properties:

first, they allow for low-interactivity PAKE. Note that this is very desirable, since latency is one of the main source of inefficiency when communicating with a server on the web. To see it, consider a construction with a designated-verifier proof: intuitively, each player could just prove to the other that, say, some commitment contains the right password. The parties could then perform a standard key exchange after verifying the proofs. However, making this formal requires in particular several rounds of interactions. SPHFs improve that because for PAKE, it is not needed at all that each party proves to the other that he knows the right password: we only want to ensure that if both parties know the same password, they get the same strong key. Intuitively, this fits perfectly the SPHF definition: an SPHF gives you some specific kind of designated-verifier proof where the prover and the verifier end up having the same random key in the statement is true, and independent keys otherwise. To make that a real proof, the prover then sends his key to the verifier, who checks that this is the same as the one she got. But in the PAKE application, this last check is not needed: the hash values can directly be used as the strong key, without any further verification step. Hence, this allows for single round PAKE (for more details, see this paper).
Second, they can be built from well-studied standard assumptions, namely, DDH (and it's variant, such as DLIN). In contrast, the natural alternative approach to obtaining a low-interactivity PAKE (which, as I already argued, is very desirable for efficiency reasons) would rely on non-interactive zero-knowledge proofs, which are not known from such well-studied assumptions (existing efficient NIZKs require pairing-based cryptography, or the random oracle model).
Third, they are very algebraic, which is a strong bonus both for optimizing efficiency (since all kinds of tricks, such as batching, become available) and analyzing security. Hence, SPHFs lead to the most efficient PAKEs in the standard model (with only 6 group elements sent by each party, in a single round) with the highest security notion (UC security, which means security even in an arbitrary concurrent setting, as well as full adaptive security for some more recent constructions).


Is there a relation between passive/active attacks and IND-CPA/IND-CCA? I've seen some papers drawing a connection between IND-CPA and passive attacks and IND-CCA and active attacks. Can someone explain how IND-CPA relates to passive attacks and IND-CCA relates to active attacks if this is indeed the case?
The most recent example of such a paper that I can recall is this: https://eprint.iacr.org/2020/1533
Another example is this excerpt from the preface of Introduction to Modern Cryptography, 3rd edition (http://www.cs.umd.edu/~jkatz/imc.html):
"We have divided our treatment of symmetric-key encryption into two parts:   Chapter 3 deals with security against “passive” attacks (i.e., CPA-security), while Chapter 5 addresses “active” attacks (i.e., CCA-security and authenticated encryption)."

IND-CPA and IND-CCA are formal security models. "Active" and "passive" are informal descriptive terms.
"Passive" usually refers to an adversary who simply observes a system under its normal operation by honest users. "Active" refers to an adversary who "interferes" in some way, causing situations that cannot arise under honest usage, usually by providing "unexpected" or "impossible" cryptographic data.
CPA is a "passive" attack since the adversary just observes honestly generated ciphertexts. The adversary chooses the plaintexts, but that is not considered an "active" attack -- plaintexts themselves are not cryptographic, and the encryption algorithm is still applied honestly to those plaintexts.
CCA is an "active" attack since the adversary can cause maliciously generated ciphertexts to be decrypted. This is something that can never happen under the normal operations of a system by honest users.
The paper that you reference considers itself a "passive" attack because it only involves decrypting ciphertexts that are the result of honestly running (an adversarially chosen sequence of) the encryption scheme's algorithms.


Using zk-snarks to check if value is greater than another Can I use Zk-SNARKS to prove that a given secret value is greater than another public value. for Example to prove that secret_value >10 . if so How would such a circuit look

I am using snarks.js which uses circuit file .

To do range proofs with zk-snarks, you have to compute an inequality over an arithmetic circuit. The way this is done is by subtracting the two numbers and then checking if the result is negative.

For example - say you want to see if 3 < 10.

You calculate 3 - 10 = -7
Do a bit decomposition of -7 using 2's compliment. The result is 100111.
The first bit of the result is 1, so output 1, signifying that yes, 3 is smaller than 10.

Zokrates has inequalities built into their DSL, so you can use this out of the box.

While this is doable, using proof systems that are catered specifically to range proofs is often beneficial. For example, Bulletproofs have a batching mechanism for range proofs, so if you do enough of them, its proof size becomes comparable to Zk-Snark protocols. Since bulletproofs do not require a trusted setup, this can end up saving you a lot of computation time overall.

Current implementations of bulletproofs include a rust implementation, a haskell implementation, and this summary).


Is it possible to convert a selective secure broadcast encryption scheme to an adaptive secure broadcast encryption scheme? I was reading the paper, entitled "Multiparty Key Exchange, Efficient Traitor Tracing, and More from
Indistinguishability Obfuscation", by Boneh et al. On page 23, the authors have claimed the following.
"Remark 6.2. We note that for private linear broadcast, there are only a polynomial number of
recipient sets, meaning selective and adaptive security are equivalent."
How can we prove this Remark? Is it possible to transform a selective secure private linear broadcast encryption scheme to an adaptive secure scheme (for the system which can accommodate at most a polynomial number of users)?

There is a generic reduction from breaking selective security of a protocol $\mathsf{P}$ to breaking its adaptive security: the adaptive reduction for $\mathsf{P}$ simply guesses (at random) the information $w$ (in your case, the recipient set) that the adversary commits to in the selective experiment. Therefore, if $w$ comes from a universe $\mathcal{W}$ (which in your case is the set of recipient sets) and if $\mathsf{P}$ is at least $\epsilon$-secure then $\mathsf{P}$ is also at least $\epsilon\cdot|\mathcal{W}|$-secure. Since the universe $\mathcal{W}$ in the case of private linear broadcast is only of polynomial size, the adaptive security of $\mathsf{P}$ follows.$^*$
I think this idea is folklore, but the earliest formal statement I found goes back to [BB] (Theorem 7.1); you can read more about it in [J+]
[BB] Boneh and Boyen, Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles, Eurocrypt 2004
[J+] Jafargholi et al.,  Be Adaptive, Avoid Overcommitting, Crypto 2017
$^*$ In most cases the universe is of exponential size and this lead to an exponential loss in security. But there are examples where this is the best we know!


AES-256-CBC with random IV - storing same plaintext as same ciphertext I am encrypting some information stored in a column of a MySQL database.
The column can contain repeated values, let's say the table has 7 rows and the column to be encrypted has the following values:

"a", "b", "a", "c", "b", "b", "c"

I would like to know if is insecure to encrypt just one time each different value (each one with a random IV stored along with the ciphertext) and to reuse the same ciphertext for the same plaintext.

Let's say that the encryption of "a" with a random IV (IV1) gives "z", the encryption of "b" with another random IV (IV2) gives "x" and the encryption of "c" with another random IV (IV3) gives "k". Would it be insecure to have all the "a"s encrypted as "z", all the "b"s encrypted as "x" and all the "c"s encrypted as "k"?

"z", "x", "z", "k", "x", "x", "k"

I often read that it is a weakness to have the same ciphertext for the same plaintext, but I was wondering if this weakness is no longer present if you use a random IV each time to encrypt the data.

Thanks for your help.

I often read that it is a weakness to have the same ciphertext for the same plaintext, but I was wondering if this weakness is no longer present if you use a random IV each time to encrypt the data.

The weakness is still present. It would be mitigated if, for equal plaintexts, you generated different random IVs when encrypting. Using different IVs for equal plaintexts would then yield different ciphertexts.

Why would you want different ciphertexts? Consider the scenario where you have a database with two columns, a VARCHAR username and a BOOLEAN has_some_horrible_disease. Suppose you encrypt the has_some_horrible_disease column for privacy purposes using the scheme you describe. One day an attacker compromises the database and has access to all the data. Suppose the attacker knows that username "johnsmith" has a value of "true" for has_some_horrible_disease (this is not farfetched, all they have to do is e.g. create an account and set their data to the target values).

The issue is that you just leaked the has_some_horrible_disease values for every single user! Why? Because the encrypted value for user "johnsmith" is the same for every other user who has has_some_horrible_disease set to "true". In other words there's a 1-to-1 mapping from encrypted value to cleartext value. If you used a random IV this would not be the case, every value in has_some_horrible_disease would be unique to that row (with extremely high probability).


Encrypted cerficiate signature for server certificate and intermediate certificate in packet capture If we view the certificate chain using Firefox, we can see the certificate signature of "server certificate" and its "intermediate-CA" right after the "certificate signature algorithm" in the certificate field

In the packet capture, this is returned by the server:

1) server certificate, its public key, its certificate signature algorithm, and followed by some thing encrypted (I guess this is the certificate signature, no?)

2) intermediate CA certificate, its public key, its certificate signature algorithm, and followed by some thing encrypted. (I guess this is the certificate signature too, no? )

My question, which key is used to encrypt the certificate signature of "server certificate" and "intermediate CA"?

If server private key is used to encrypt certificate signature for both server certificate and intermediate CA, then server's public key can be used to decrypt and view their certificate signature

If intermediate CA used its own private key to encrypt the certificate signature, then must use the intermediate CA public key to decrypt and view its certificate signature - however, the server will not have the private key of the intermediate CA, then how can this happen? Unless when configuring the certificate chaining in the server, the imported intermediate CA already has the certificate signature encrypted?

Appreciate if someone can shed some light.

The intermediate certificate is signed by its issuer(a root CA or another intermediate CA), using the private key of the issuer's certificate.

The server certificate is signed by the intermediate CA at the lowest level of the certificate chain.

  when configuring the certificate chaining in the server, the imported intermediate CA already has the certificate signature encrypted?

Yes, when you want a certificate for your domain, you ask for it from an intermediate CA. After the CA verifies that you're the actual owner of the domain, they give you a certificate signed by the CA's private key. Then you can configure to use it on your server.

The intermediate certificates are simply available to the public, they are sent by the server generally for clients that don't have them installed.


Which public key cryptosystems are not based on number theory? Are there any public key cryptographic systems whose hardness assumptions don't involve number theoretic problems?

Yes. The McEliece cryptosystem using Binary Goppa codes has withstood cryptanalysis to date. Its hardness is based on decoding. I should note that it has been broken for certain classes of codes.

Another common example is the Merkle-Hellman knapsack cryptosystem. Unfortunately it was broken. It is likely possible to build a secure cryptosystem based on the knapsack problem. I wanted to at least mention this line of work.


If $((p-1)*(q-1) -1)$ divisible by $e$ ($e$ is odd number) , then $\text{gcd}(e,(p-1)*(q-1)) = 1$ If $((p-1)(q-1) -1)$ divisible by $e$ ($e$ is odd number) , then $\text{gcd}(e,(p-1)(q-1)) = 1$. ($p,q$ are prime numbers ) Is this true, if yes why, if not why not ?

Is this true?

I'd generalize it, and replace $(p-1)(q-1)$ with $X$; that is, if $X-1$ is divisible by $e$, that is, if $X-1 = k \times e$ for some integer $k$, then $\gcd(e, X) = 1$. Is this true?  If it is, then your original statement is also true (because if it holds for all $X, e$, it also holds for all $X$ that is of the form $(p-1)(q-1)$ and for all odd $e$.).
As a further hint, we can also observe that $\gcd(e, X) = \gcd(e, X \bmod e)$ (that's the central observation that makes the Euclidean method for evaluating $\gcd$ work).
With that, it should be fairly straight-forward to proceed...


Why does OpenSSL append extra bytes when encrypting with aes-128-ecb? Plaintext:

Attack at dawn!!

Hex:

41747461636b206174206461776e2121

Key:

abcdefghijklmnop

Hex:

6162636465666768696a6b6c6d6e6f70)

Through calculations done both by hand and with various sites online, the result should be:

379693884e25f00f6e8aaa43df4db541

The result is the same length as the input, byte-for-byte.

I tried to recreate this result using OpenSSL with the following:

echo 'Attack at dawn!!' | openssl enc -aes-128-ecb -K 6162636465666768696a6b6c6d6e6f70 -nosalt -out out.bin

The output is:

379693884e25f00f6e8aaa43df4db541
8e64ce873f174dbb2423fcd814580e15

The fact that the first 16 bytes of the OpenSSL result is the same the by-hand calculations shows me that I'm on the right track.

My question is: What are the remaining "extra" 16 bytes for?

First, your use of 'echo' gets you:

~ % echo 'Attack at dawn!!' | hexdump -C
00000000  41 74 74 61 63 6b 20 61  74 20 64 61 77 6e 21 21  |Attack at dawn!!|
00000010  0a                                                |.|
00000011

Note that there are 17 bytes there, not 16. echo adds a newline character. To stop that, use the -n flag:

~ % echo -n 'Attack at dawn!!' | hexdump -C
00000000  41 74 74 61 63 6b 20 61  74 20 64 61 77 6e 21 21  |Attack at dawn!!|
00000010

If you use the -v flag with openssl enc, it will tell you how many bytes were read:

~ % echo 'Attack at dawn!!' | openssl enc -v -aes-128-ecb -K 6162636465666768696a6b6c6d6e6f70 -nosalt -out out.bin
bytes read   :      17
bytes written:      32

So that would have been an indicator of something being wrong. The echo problem isn't the only one, though; we still have two blocks of output despite only having one block of input:

~ % echo -n 'Attack at dawn!!' | openssl enc -v -aes-128-ecb -K 6162636465666768696a6b6c6d6e6f70 -nosalt | hexdump -C
bytes read   :      16
bytes written:      32
00000000  37 96 93 88 4e 25 f0 0f  6e 8a aa 43 df 4d b5 41  |7...N%..n..C.M.A|
00000010  8e 64 ce 87 3f 17 4d bb  24 23 fc d8 14 58 0e 15  |.d..?.M.$#...X..|
00000020

The second issue is that OpenSSL uses PKCS#7 padding to ensure there are full blocks. In this padding scheme, padding is always applied. So, in the case of a full input block, another full block of 0x10 bytes will be added as padding, which means you'll have two blocks of output (which is what you see above).

The -nopad option for openssl enc disables padding (but it will throw an error if your input isn't a multiple of the block size):

~ % echo -n 'Attack at dawn!!' | openssl enc -aes-128-ecb -K 6162636465666768696a6b6c6d6e6f70 -nosalt -nopad | hexdump -C
00000000  37 96 93 88 4e 25 f0 0f  6e 8a aa 43 df 4d b5 41  |7...N%..n..C.M.A|
00000010


What is the hash of this cipher: TLS_RSA_WITH_AES_128_CCM In TLS 1.3 supported ciphersuite,  I find the following ciphersuite:

  TLS_RSA_WITH_AES_128_CCM

Can any one tell me what is the hash function used in this ciphersuite? how could you know that (reference please).

In draft 14, which is not the latest draft at the time of writing there are two places where a hash is used: the one for signature generation / verification using the private key / public key pair of the leaf certificate and the one used as configuration parameter for HKDF (session key derivation)

For signature generation / verification

TLS_RSA_WITH_AES_128_CCM doesn't exist, only  TLS_DHE_RSA_WITH_AES_128_CCM exists which is similar but uses a different key agreement protocol. RSA for key agreement was explicitly deprecated for TLS 1.3. In the RFC the ciphersuite can be represented by TLS_AES_128_CCM_SHA256; beware that the DH key agreement scheme - if that is used instead of ECDH - differs ever so slightly though (disclosure: sorry, I did that).

RSA uses the supported_signature_algorithms extension to select the hash configuration parameter within the signature generation function. This is specified clearly in section 4.2.2.  Signature Algorithms.

For key derivation

The hash is after the (EC)DHE key agreement operation to derive the session keys. This will always use HKDF, as specified in appendix A.4:

  Cipher suite names that lack a "HASH" value that are defined for use
  with TLS 1.2 or later use the SHA-256 hash algorithm by default.


PRP representation size I'm now studying the block cipher substitution-permutation network construction and realized that it uses several small pseudo-random permutations instead a big one for saving memory (or that is one of the reasons).

Why does the PRP with input/output of $n$ bits utilize $\log(2^n!)$ memory? (When saving a full table of $\mathrm{Domain}\to\mathrm{Range}$)

I thought it should utilize $n\cdot2^n$.

Each one of your first two sentences has a mistaken premise: you're starting from some assumptions that aren't actually true.

DES does not use small PRPs for saving memory.  It doesn't use small PRPs at all.  The DES S-boxes are not PRPs.  The DES F-function is not a PRP.  A SPN does not use several small PRPs for saving memory.  A SPN doesn't use PRPs at all.  The S-boxes in a SPN are not PRPs.

A PRP does not necessarily require $\lg(2^n!)$ memory.  Actually, most PRPs have short keys that fully determine the encryption mapping, and the short key can be stored in much less memory.  That is in some sense the entire point of a PRP.

You might wish to restate your questions in a way that removes those implicit assumptions.  Also you might wish to review the definition of a PRP again, and read some more textbook material on PRPs to familiarize yourself with the concept a bit further.  Perhaps you are confusing a PRP with a random permutation (one chosen uniformly at random from the set of all permutations on $n$ bits).  If so, here's an exercise for you to ponder: how many permutations are there on $n$ bits?  Now what happens if the take the logarithm (base 2) of that number?


Encrypt letters separately? I am trying to encrypt the word Hello using RSA. When encrypting Hello’s integer representation, is each letter encrypted separately, or is the whole thing encrypted? Furthermore, am I correct in assuming that Hello is to be represented in binary form for RSA encryption?

For the purposes of your high school project, I suppose either one is fine. As you mentioned, one possibility is to convert the message to a bit-string using ASCII, and then interpret the bitstring as an integer and treat it as the message to be encrypted. If you need to "show your work" on paper or slides, then writing it in decimal is reasonable.

However, as @otus mentioned, this method is never used in practice nowadays because it falls short of what we require of modern cryptosystems, for various reasons. You can Google something like "textbook RSA" or "plain RSA" to find out more, and I would suggest that it would be a good idea to at least mention those issues in some way in your project.


Rapid partial block decryption of compute intensive full encryption Given a block of data D: Is there a encryption/decryption scheme that would allow me to perform a resource-intensive (compute/time/memory) encryption of the full data set with a key k, but allow for a rapid decryption of arbitrary constant-length parts (say 64 bytes) of this data set?

Encryption key k is known to the decrypting instance.

Example: Data set is 65536 bytes and will be encrypted by key k. This encryption can be O(n), O(n²)

Now consider the encrypted data to be an array of 1024 x 64 byte data chunks: Can I decrypt an arbitrary chunk D[i] (for i [0,1023]) in O(1) ?

The following mostly solves the problem as expanded in comment, but not quite: decryption is not $O(1)$.

We use some purposely slow hash function $H_w$ (where $w$ is a workfactor parameter for e.g. PBKDF2-HMAC-SHA-256, Scrypt, Argon2, Baloon..).

We define parameter $s$, the encryption overhead in bits per chunk; and $t$ which controls the average number $2^t$ of invocations of $H_w$ for (the first) encryption of a chunk. Decryption does just above one invocation on average, and seldom many, when we assume $0<t<s-6$. Example parameters can be $s=32$, $t=20$.

Chunk $c$ is enciphered using AES-CTR, IV of $c\ll8$ (which for up to 4KiB chunk ensures no IV reuse), and an AES key $k_c$ (of say $b=128$ bits) determined as follows:

Using auxiliary fast Key Derivation Function, both encrypting and decrypting parties compute $\operatorname{KDF}_k(c)$ of $2b$ bit (where $k$ is the overall encryption key), and split the outcome into $\widetilde{k_c}$ and $k'_c$ each $b$-bit. The auxiliary KDF can be HMAC-SHA-256. The final $k_c$ is determined from $\widetilde{k_c}$ and $k'_c$ as follows.
The party that encrypts

sets $k_c\gets\widetilde{k_c}$;
tests if $H_w(k_c)\bmod2^s=0$, and if not sets $k_c\gets k_c+1\bmod2^b$ and retry (assimilating integers modulo $2^l$ and $l$-bit bitstrings per big-endian conventions);
computes $n=k_c-\widetilde{k_c}\bmod2^t$ and includes that 48-bit $n$ as a prefix of the ciphertext chunk;
sets $k_c\gets k_c\oplus k'_c$;
now has the final $k_c$, and encrypts the chunk.

The party that decrypts

extracts $n$ from the ciphertext chunk's prefix;
sets $k_c\gets\widetilde{k_c}+n\bmod2^b$;
tests if $H_w(k_c)\bmod2^s=0$, and if not sets $k_c\gets k_c+2^t\bmod2^b$ and retry (which should happen rarely);
sets $k_c\gets k_c\oplus k'_c$;
now has the final $k_c$ (always the same as used for encryption), and decrypts the chunk.

For large $k$, the observation of $n$ from ciphertext leaks no useful information to an adversary, assumed with no access to $k$, $k'_c$, and the final $k_c$ (the system is also protected from leaks related to $H_w$, $\widetilde{k_c}$, or intermediary values of $k_c$, e.g. by timing attack). The CTR IV unique per AES block ensures that multi-target search of $k_c$ do not apply.

Possible improvement: we can add one bit of overhead set on encryption to tell if $H_w(\widetilde{k_c}+n)\bmod2^s=0$, which occurs in most cases, and decreases the decryption overhead dramatically.

Note: a former version had no $k'_c$, and $n$ could leak some information. This revised version can thus be safely used with $b=128$, rather than the original $b=192$.


Predicting value of E(k,0) for Block cipher with random and secret key Some mode of operation of block ciphers rely on the fact that E(k,0) is an unpredictable value when k is random and secret (with 0 denoting the all-zero binary string). Why is this a reasonable assumption?

A block cipher, according to its design purpose, is assumed to be a pseudorandom permutation. This means when the key $k$ is chosen at random, $E(k,\cdot)$ can be viewed as a random permutation. Then, $E(k,0)$ is indistinguishable from a random value of the block length, hence unpredictable.


Is Using Digital Signatures to prove identity a zero knowledge proof? Suppose Alice publishes a book with a public key in it, and later wants to prove that she wrote the book. She could sign challenge messages with her private key, and others could verify those signed messages. Alice is proving she knows a private key without revealing anything about it.

Is this an example of an interactive zero knowledge proof?

Or does this example somehow not apply to zero knowledge proofs?

This is not zero knowledge. In particular, you give away information in the form of signatures on challenges. This is something that the verifier doesn't have and so it is something that is "learned".

This can be meaningful for two reasons. Let's say that I want to prove to YOU that I wrote the book, but I don't want you to be able to convince anyone else that you interacted with the person who wrote the book. With this protocol, it's possible to prove that you interacted with the book author, but this isn't possible with real ZK. Another issue is that the challenge may actually be generated maliciously so that it provides a meaningful signature.


secure "related-key" stream cipher Consider a stream cipher $E(k)$ which takes a key $k$ to produce a pseudo random keystream.

It should have the property that you can easily generate a set of at least 3 different keys $\{k_m, k_0, k_1, \cdots\}$ such that the key stream generated by the master key $E(k_m)$ is the same as XOR-ing all key streams of the other keys $E(k_0) \oplus E(k_1) \oplus \cdots$

Is this property a security risk by itself, or could such a cipher be used to speed up an encryption scheme with nested encryption, like onion routing?

If it could be secure, are there already any ciphers with such a property?

If you consider symmetric encryption schemes instead of just stream ciphers, you're looking for "key-homomorphic encryption". There has been some work on lattice-based fully key homomorphic encryption schemes (see here).


How secure is HMAC SHA256 I have a message (UUID) in this form 406a5830-2a6a-11e6-bdf4-0800200c9a66. I also use a secret key for example 0987YGN.?NBVFRTY876JOPOIUHJ$$bvcfghjKFDFGH876TH$. Every 3 seconds I use the java function below to crypt the UUID+Time with the secret key using the SHA 256 function. I publish the new result on the internet. As I have a new hash every 3 second, it's easy for everyone to collect a big numbers of hash.And as the difference between every UUID is always 3000 ms, maybe this could make it easier for the hacker to crack the key. My question is: Would it be possible for a person to guess the secret key or the message I am using? Is it possible to calculate the probability that this system get hacked ?

import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;
import org.apache.commons.codec.binary.Base64;

public class ApiSecurityExample {
  public static void main(String[] args) {
    try {
     String secret = "0987YGN.?NBVFRTY876JOPOIUHJ$$bvcfghjKFDFGH876TH$";
     String message = "406a5830-2a6a-11e6-bdf4-0800200c9a66"+System.currentTimeMillis();

     Mac sha256_HMAC = Mac.getInstance("HmacSHA256");
     SecretKeySpec secret_key = new SecretKeySpec(secret.getBytes(), "HmacSHA256");
     sha256_HMAC.init(secret_key);

     String hash = Base64.encodeBase64String(sha256_HMAC.doFinal(message.getBytes()));
     System.out.println(hash);
    }
    catch (Exception e){
     System.out.println("Error");
    }
   }
}

As I have a new hash every 3 second, it's easy for everyone to collect a big numbers of hash.  And as the difference between every UUID is always 3000 ms, maybe this could make it easier for the hacker to crack the key.

You might be reassured to read up on the security requirements that MACs are designed for.  Chapter 9 of the Handbook of Applied Cryptography is a good, freely available source.  (Section 9.2.2 is the most relevant.)

But to make this short, good MACs are expected to resist adaptive chosen text attacks, where the attacker doesn't just see the tags, they get to:

Choose messages of their own liking;
Cause you to compute these messages' tags;
Pick messages based on what they learn from earlier ones.

A MAC is considered broken if an attacker in that scenario can learn enough to successfully forge tags for other messages than the ones they caused you to authenticate.  That's a scenario much, much more adverse than the one you describe, where they only passively see tags (and no messages).

So as long as you can keep the key secret, you probably have much bigger security concerns than this.


If $H(x)$ is a one-way function, is $f(x)=H(x)\cdot x^{-1}$ a one-way function? Assume $S$ is a domain. $S' \subseteq S$ and all elements in $S'$ are invertible.  $H:S'\rightarrow S$. If $H(x)$ is a one-way function, is $f(x)=H(x)\cdot x^{-1}$ a one-way function?

Let ${y=x^{-1}}$. if ${f(x)}$ is a bijective function. then we can avoid ${H(x) \cdot y= H(x) \cdot y'}$, where every ${x}$ has unique ${f(x)}$


Non-malleable file encryption using AES XTS 256? I'm looking to do file encryption of a bunch of individual files, some small, some quite large.  The files will be write-once/read-many, so I could use CBC, however, since the read-access needs to have seekability, XTS seems a better fit.  One issue, as I understand it, is that XTS (or CBC for that matter) is malleable... i.e. if the encrypted cipher text is modified, an attacker could potentially do some targeted things to files.  So I was thinking surely this problem is already solved but it wasn't clear to me what the standard was, if any.  Performance is a concern, so one thought I had was simply running a CRC on each XTS sector and including the CRC result in the plaintext for encryption of that XTS sector (e.g. just expand each sector by the 4 octets).  Thus, if anything in the sector was modified by an attacker, the decrypt would fail (i.e. the CRC wouldn't likely match).  Is there a smarter way, or a standard that's "fast"?

EDIT: it occurs to me that if the files are rewritable (which currently they are not) a CRC on each cluster in XTS mode is still open to an attack where an attacker can guess at the plaintext and write a cluster to a known location in the file and see if it matches the cluster that's already there.  Only way to prevent that is to have a random IV per block as well, that changes per write, I think.

As Paŭlo Ebermann notes in a comment above, the time cost of a proper MAC calculation is almost certainly negligible compared to the cost of reading or writing the data on the disk.

Applying a MAC to each encrypted sector (and the sector number used to derive the IV) will fully protect your data against most forms of tampering.  The main drawback of this method, of course, is the need to store the MAC outputs somewhere so that they can be verified when the data is read back.  But, of course, the same drawback applies to your proposed "encrypted CRC" method as well.

As for the security of using an encrypted CRC as a MAC, it probably depends on details of the way the encryption is done (and I'm not aware of any security analyses of such a scheme in combination with XTS mode).

In particular, if the sector data was encrypted using CTR or OFB mode (or something similarly malleable), then the linearity of CRCs would allow bit-flipping attacks to be done in a way that does not change the CRC checksum.  As Wikipedia notes, this was one of the main weaknesses in the (by now thoroughly broken) WEP protocol, which used an encrypted CRC for integrity protection.

On the other hand, if one were to encrypt both the data and the CRC using a wide-block encryption mode like CMC or EME, this would probably be secure, at least if the CRC was long enough to resist brute force.  Then again, in that case we could presumably achieve equivalent security just by replacing the CRC with a block of zero bytes of the same length, and checking that they're still zero after decryption.  And it would presumably still be slower than XTS plus a proper MAC.

Note that one form of tampering that even proper per-sector MACs will not prevent is a "reversion attack" where the attacker replaces the entire contents of a sector with previously captured ciphertext from the same sector, in effect reverting the corresponding plaintext data to an earlier version.  To prevent such attacks, you could for example compute an additional MAC (preferably of the Carter–Wegman type, such as VMAC or Poly1305, since those can be efficiently updated when part of the input data changes) over the per-sector MACs, and verify that global MAC when the disk is mounted.

Of course, even such a global MAC will still not protect you against whole-disk reversion attacks, where the entire content of the disk is replaced by an earlier copy of it.  In general, there is no way to prevent such attacks unless some data (like a copy of the global MAC) can be securely stored somewhere outside the disk itself.

Also, avoiding accidental MAC verification failures e.g. in the event of a power loss during a write is possible but rather tricky.  Basically, it would require some kind of a secure intent log where you first write an (encrypted and MACed) record of the data you intend to write and the way this will affect the global MAC, flush it to disk, and only then perform the actual write to the rest of the disk.  Done properly, that should ensure that, at any given point in time, either a) the rest of the disk is in a consistent state and properly MACed, or b) the intent log is consistent and properly MACed, and the rest of the disk can be brought to a consistent and properly MACed state by replaying the planned changes recorded in the intent log.  Of course, if you do all that, as a nice side effect you'll also gain extra resiliency against accidental (as well as deliberate) data corruption.


BGW Theorem 2- Does this proof work? I was reading the original BGW paper. Great paper. I'm confused about Theorem 2, though.

The Theorem states, "There are functions for which there are no n/2-private protocols."

The proof is simply that two players cannot compute an OR without one of them leaking information.

But the way I see it, that isn't an MPC problem, that's a problem with the function being evaluated. Normally, the security of MPC is evaluated on the basis of whether it accurately simulates a trusted third party who receives inputs, evaluates the function and distributes outputs. Even with a trusted third party, evaluating an OR would always leak information about one of the inputs to the other party.

Similarly, couldn't you just argue by the same logic that if you evaluate the function $f(x_1, ... x_n)=x_1$ for arbitrarily high number of players $n$, then this leaks information about player 1's input?

So you could argue, by the same argument that "There are functions for which there are no 1-private protocols."

Or am I misunderstanding their proof?

As Geoffroy Couteau already pointed out, this is not about the output of the OR-function revealing information about the other player's input (as indeed it also does in the trusted third party setting).

The setting is that of 2 players Alice and Bob having access to a bidirectional secure (and noiseless) channel. For simplicity, consider the asynchronous setting, so where we players alternate sending messages to each other. (The argument extends to the synchronous setting.)

Since both players have access to all information on the channel, we can essentially view their communication as one after the other appending information to a publicly visible transcript (e.g. picture both players in a room, one after the other writing a message on a blackboard).

Suppose we could compute the OR-function privately, and consider an execution of this protocol where both player's input bits are 0. At some point during this protocol, one player, say Alice, is first to learn the computed output of the function. Consider the transcript $T$ up to this point. A few observations:

Since Alice's input bit is 0, the output of the function will be equal to Bob's input bit. Thus, Alice is able to learn Bob's input bit from $T$ and her own input and random tape.
$T$ should not give Bob any information about Alice's input bit, since Alice was the first to learn the other player's input bit.
Therefore, $T$ could also have occurred (from Bob's perspective) if Alice's input bit had been 1, otherwise he is able to distinguish based on the transcript and learn Alice's input bit.
If Alice's input bit had been 1, she should not have learned Bob's input bit from $T$.

Points 1 and 4 are clearly inconsistent given observation 3, hence such a protocol cannot exist.


Where do Windows applications get entropy from? Where does the entropy that cryptographic .NET libraries use for encryption come from? I know with Linux you can use /dev/random, but does a similar pool exist within Windows?

Update: Since I wrote this post, CryptGenRandom has been deprecated. Apparently it is now recommended to use BCryptGenRandom from the "Cryptography Next Generation" API.

(Confusingly, it has nothing to do with bcrypt.)

Yes, Windows has something similar. It can be accessed through CryptGenRandom.

  With Microsoft CSPs, CryptGenRandom uses the same random number generator used by other security components. This allows numerous processes to contribute to a system-wide seed. CryptoAPI stores an intermediate random seed with every user. To form the seed for the random number generator, a calling application supplies bits it might have—for instance, mouse or keyboard timing input—that are then combined with both the stored seed and various system data and user data such as the process ID and thread ID, the system clock, the system time, the system counter, memory status, free disk clusters, the hashed user environment block. This result is used to seed the pseudorandom number generator (PRNG). In Windows Vista with Service Pack 1 (SP1) and later, an implementation of the AES counter-mode based PRNG specified in NIST Special Publication 800-90 is used.

Technically this is closer to /dev/urandom than /dev/random, but in practice the fact that you get cryptographically random numbers rather than "pure entropy" does not matter.


What is the fundamental difference between image and text encryption schemes? I don't know where to ask this question, I hope I am in the right place to ask about this.
So, what exactly is the fundamental difference between image and text encryption techniques?
link 1
link 2
link 3
I mean there are a lot of researchers (for example on the above links) that said AES, DES, RSA, etc. are not suitable for encrypting images because of image characteristics (high redundancy, high correlation, and large volume). Some of them imply that it will have a long encryption time because of the size and the low security it provides since the data originally has a high correlation. Hence they develop image encryption schemes using chaos theory, optical transform, random grids, DNA coding, compressive sensing, and so on.
Is the diffusion or confusion technique fundamentally different? If it is, how exactly does it differ from text encryption's confusion and diffusion? If it is not, why not just use text encryption by modifying AES or DES so that it takes an input of an image and output it as an image? I haven't found any articles that literally describe what differs between image encryption and text encryption techniques/methods.

TLDR: None worth academic interest.

All modern encryption techniques intended for digital computers are applicable, and secure, for all kinds of digitized data, including text and image. There is no need for such encryption specialized to image or text. Argument: the modern baseline for encryption security is resisting Chosen Plaintext Attack, and that model assumes the attacker can choose the plaintext, including image in whatever format.
We can encrypt image, or pretty must anything digital, with e.g. AES-CTR or Chacha. These are widely available on most computer platforms, there is no known attack against them (baring side-channel attacks and IV reuse, which really are attacks on the implementation), and with a competent implementation, speed is faster than most processing peripheral to image processing, like compression, transmission, storage.
From a sampling of papers on image encryption (those at MDPI are free access), most have precisely no advantage over standard techniques: these paper's technique typically is slower and comes with weak security claims (often, relying on some standardized algorithm or metric; that's even though, assuming the existence of secure encryption, we demonstrably can't make a polynomial-time algorithm that recognizes good from bad encryption by examining ciphertext and plaintext). Reasons for why these papers are published (often, for a fee) are discussed there. Whatever these reasons are, peer-reviewed IACR publications seldom if ever buy them: I've only found preprints with this query.
Still, there are a few legitimate reasons to special-case image:

It calls for special techniques for the most efficient data compression (before encryption), in order to exploit the correlation between nearby pixels and characteristics of the human eye. There is an interaction with encryption, in that we must be careful that the compressed size does not leak exploitable information.
When we want the ciphertext to be a meaningful image: steganography, and Thumbnail-Preserving Encryption (where plaintext and ciphertext are images, and the ciphertext a thumbnail of the plaintext).
When we want decryption by analog means, such a superposition of transparencies. That's visual cryptography, a legitimate (if limited) field of research.
If we also wanted encryption by analog means. That's the goal of optical image encryption. It has been theorized in this (extremely cited) article (1995), and demonstrated experimentally (1996). I find several reports that it is practically broken in a ciphertext-only setup believable. There are countless variations, many simulations only with bogus security argument.


Encrypting h(k) for defeating partition oracle attacks Is encrypting $h(k)$ (or even just $k$) and verifying it before checking the MAC enough to defeat partition oracle attacks and thus make the whole scheme robust/committing (without depending on properties of the cipher, unlike 0-padding)?
update 1:
basically $E_k(h(k)\mathbin\|m)$ or $E_k(k\mathbin\|m)$ where $E$ is an AEAD mode like $(x)chacha20poly1305$. The $k$ is derived from a password from a pkdf like argon2/scrypt/etc. At the start it is computed on both ends but then the party decrypting the ciphertext also checks if $h(k)$ (or just $k$) is correctly appended before the message.

The partition oracle attack works if the oracle returns information like the tag is correct or not. Without a response, there is no Oracle at all. The information can also be obtained from side-channels, too.
The partition oracle simply speeds up the password attack by grouping the passwords. The passwords are selected from a possible set of password list $\mathcal{D}$ and the corresponding key is generated by a PBKDF. The corresponding keys are grouped under a ciphertext that can be correctly decrypted.  Here one must note that the correctly decrypted ciphertext doesn't need to have some meaningful plaintext at all. The attacker only requires that under the grouped keys, the ciphertext has valid or invalid tag information returned back to them. This attack works since GCM and Poly1305 are non-committing, i.e. it is computationally feasible to find a pair of keys and a ciphertext (with its tag) that decrypts under both keys.
For the update 1

basically $E_k(h(k)\mathbin\|m)$ or $E_k(k\mathbin\|m)$ where $E$ is an AEAD mode like $(x)chacha20poly1305$. The $k$ is derived from a password from a pkdf like argon2/scrypt/etc. At the start it is computed on both ends but then the party decrypting the ciphertext also checks if $h(k)$ (or just $k$) is correctly appended before the message.

If one uses $E_k(h(k)\mathbin\|m)$ or $E_k(k\mathbin\|m)$, then two cases can occur;

The tag is not valid. This means that the oracle must return the $\texttt{tag invalid}$ response. Now, this is the core of the partition oracle attack. They sent the server a ciphertext that has a valid tag for the $k$ passwords. Returning invalid simply eliminates the $k$ passwords from the passible known password list $\mathcal{D}$.
If the communication is one-way, then there is no need to return any tag. But this really depends on the protocol. A usual protocol must respond.

The tag is valid. In this case, we return to your modifications. Now you will respond as the message format not valid. Viola, the partition oracle still get the information that the current tested $k$ password contains the valid password since the tag passed.

Of course, for both cases, there are false negatives for the attacker to eliminate. Those have a low probability to occur.
The main mitigation is using a committing AEAD that is not standardized yet or use HMAC with one key in as Encrypt-Then-HMAC. And remember using a strong password is always recommended.
For the update 2

The first block that also contains $k$ or $h(k)$ would be decrypted before checking the MAC tag (as an exception, unlike the following blocks). This is in order to verify whether the $k$ or $h(k)$ that is encrypted in the message matches the k that we are decrypting with before verifying the MAC tag (in order to not leak information about whether the MAC tag is invalid). If the encrypted k or $h(k)$ does not match the decryption k then the decryption aborts (before any MAC tag is checked at all)

I this case, I don't see any way that partition oracle attack will work. The attacker can still group but the probability of a random text to have the hash of the key is $1/2^{256}$ if SHA-256 is used. Therefore no feasible attack.
The standard online password attack will still work. Therefore the usual advice of having passwords with good strength is still applied.
I did not like the idea of encrypting the key under the same key, though we don't expect a problem with AES or ChaCha20. Someone can correct me if I'm wrong about this.


How robust is RSA-FDH against distribution bias? Suppose we want to use the RSA-Full Domain Hash (-FDH) signature scheme. This essentially works precisely like textbook RSA but instead of signing $m$ directly, we sign $H(m)$ with $H:\{0,1\}^*\to\mathbb Z_n^*$ being reasonable model-able as a random oracle (we need the ROM for the security reduction).

Now my question:
Are there any known attacks when $H$ exhibits a minimal (1-bit) bias?

In particular consider $H$ where $m$ is mapped to the first $\lfloor \log_2(n)\rfloor$ of SHAKE128(m), ie where we generate a hash output as long as $n$ but always zero the MSBit out.

Motivation: If we had such a bias for the generation of $k$ in (EC)DSA, this would probably allow for an attack and I talked in the past about how RSA-FDH is one of the applications of XOFs.

Fix a number of bits $t$, e.g. $t = 2048$; consider RSA-FDH with $t$-bit modulus $n$, so that $2^{t - 1} < n < t$.  Fix a hash $H\colon \{0,1\}^* \to \{0,1\}^{t - 1}$.  Can we use $H$ for RSA-FDH, even though the literature on RSA-FDH typically posits a hash $G_n\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$?

It is not hard to define a hash $G_n\colon \{0,1\}^* \to \mathbb Z/n\mathbb Z$ with near uniform distribution using a double-length hash $H_0\colon \{0,1\}^* \to \{0,1\}^{2t}$ by $G_n(x) = H_0(x) \bmod n$; the modulo bias at this scale is negligible, just like in EdDSA's use of SHA-512 to select $k$ from $\ell \approx 2^{252}$ possibilities.

If our signature scheme were randomized, we could do rejection sampling, as phayes suggests in another answer, and attain an exactly uniform distribution—indeed, if we wanted anonymous signatures so that signatures under two keys are indistinguishable without the keys, we would have to do rejection sampling, though on the signature rather than the hash, to thwart anglophone statisticians from counting German tanks.  But this question is about the deterministic RSA-FDH.

As far as I can tell, this specific question—where $H$ covers only about half of $\mathbb Z/n\mathbb Z$—has not been addressed in the literature.  But very similar questions have been:

Tight security can be proven for deterministic Rabin–Williams signatures using $H$[1].  Although there are barriers to applying the same proof to RSA, it seems unlikely that the space covered by $H$ is one of them: they rather have to do with differences between squaring and (e.g.) cubing.  (Questions like this are part of why [1] used a single $H$ with $t$-bit codomain instead of a key-dependent $G_n$.)
Tight security can be proven for PSS signatures using a randomized hash whose most significant bit is always zero[2].  Here the randomized hash is $$P_r(m) = 0 \mathbin\| w \mathbin\| (r \oplus H_2(w)) \mathbin\| H_3(w),$$ where $w = H_1(r \mathbin\| m)$, and $H_1$, $H_2$, and $H_3$ have the right widths to make it all work out.  The proof given by Bellare and Rogaway requires $|r| \geq 128$ to provide meaningful security.
Tight security can be proven for a randomized version of FDH[3] where the randomization is appended to, rather than embedded in, the signature, like in phayes' system: a signature $(r, s)$ on $m$ under $n$ satisfies $$s^e \equiv G_n(r \mathbin\| m) \pmod n.$$  Bizarrely, this tight security works even if $|r| = 1$, even though it can be proved that deterministic RSA-FDH cannot admit such tight security[4], although that proof works only for large exponents which leaves open the possibility of tight security for $e = 3$[5] (paywall-free).  This state of affairs raises all sorts of questions about the significance of these reductions[6].

The Bellare–Rogaway 1996 proof[2] that a $q$-query forger for a trapdoor permutation signature scheme $f(s) = G_n(m)$ can be converted into an algorithm for inverting $f$ on a point $y$ works by running the forger with a derived random oracle $G'_n$ that returns $y$ on a randomly chosen one of the $q$ queries, and otherwise defers to $G_n$.  If the forger succeeds in finding a forgery $(m, s)$, there's about a $1/q$ chance that it found the preimage $s$ for our chosen point $y$ rather than for the $q - 1$ options we sent to $G_n$, and thus that $s = f^{-1}(y)$ is the desired preimage.

If we replace the equation by $f(s) = H(m)$, the reduction simply doesn't work to compute $f^{-1}(y)$ for $y \geq 2^{t - 1}$, which happens with probability less than 1/2 if $y$ is uniformly distributed in $\mathbb Z/n\mathbb Z$, so the same inversion algorithm has about a $1/(2q)$ chance of success instead.  Formally this would suggest you need to add another bit to the modulus to attain the same security—but in practical terms that bit is likely inconsequential (some practical key generation algorithms vary with a slop of a bit anyway[7]), and it remains unclear what the significance of the tightness gap is at all here when adding a single bit of randomization enables proving a theorem that eliminates the gap.

In brief, it is hard to imagine that using a hash covering only up to $t - 1$ bits, where $2^{t - 1} < n < 2^t$, could meaningfully hurt the security of RSA-FDH.  Certainly there are no known attacks like there are against biases is per-message secrets in Schnorr- and DSA-type signatures.


Authenticated encryption using libsodium's crypto_box_curve25519xsalsa20poly1305 It seems that crypto_box_easy, generates a random nonce and appends it to the cipher text in libsodium.
I understand using the same nonce with the same key can be catastrophic with  salsa20poly1305, as such is it bad practice to re-use the same public/private (static) curve25519 keys when using crypto_box_easy?
Is it safe enough to assume that libsodium will ensure a random nonce is always used, or should curve25519 keypairs be regenerated on each use?

crypto_box_easy() doesn't generate a random nonce. But as documented, using a random nonce is safe, and can be done using randombytes_buf(nonce, sizeof nonce);. It's still the application's responsibility to include that nonce in the payload.

Alternatively, the more recent secretstream API automatically creates and attaches a nonce, and can encrypt a sequence of messages without having to care about the nonce at all.

(that being said, this is a programming question, so cryptography.stackexchange may not be the best place for it)


Cipher for human interpretation Please suggest algorithms to encrypt and decrypt text messages that can be easily performed by human in a considerably short time. It doesn't have to be really secure, but sufficient to fool unskillful third parties.

I think Caesar cipher meets your requiremnts, check it out here Caesar Cipher


Key length requirement in a simple XOR implementation I don't have much previous experience at all with cryptography, this is pretty much the first time I've tried anything similar.

I'm trying to implement an extremely simple XOR encryption system in ComputerCraft for fun, here is the code:

local function xorEncrypt(data, key)
    local klen = #key local
    s = ""
    for i = 1, #data do
        s = s..string.char(bit.bxor(string.byte(data, i), string.byte(key, i % klen)))
    end
return s
end

The only thing I need to know is, in this case, will the messages still be able to be decrypted if the key that I use is shorter than the data I am encrypting?

This cipher system is the original Vernam cipher.
(In the original Vernam cipher, the key was stored on a loop of paper tape that repeated over and over).

Like all practical encryption systems, the Vernam cipher has a secret key that it uses over and over.

ciphertext[i] = plaintext[i] bit_xor key[ i % keylength ]

This cipher can be seen as a variant of the Vigenère cipher, and has the same security.

Anyone with the secret key can decrypt a ciphertext message to recover bit-for-bit the original plaintext (no matter what the keylength is) with:

plaintext[i] = ciphertext[i] bit_xor key[ i % keylength ]

  Though the cipher is easy to understand and implement, for three
  centuries it resisted all attempts to break it; this earned it the
  description le chiffre indéchiffrable (French for 'the indecipherable
  cipher'). ...
  Kasiski entirely broke the cipher and published the technique ...
  In 1863 Friedrich Kasiski was the first to publish a
  successful general attack on the Vigenère cipher.

-- Wikipedia: Vigenère cipher

The people at the Cipher Exchange say the Vigenère cipher can be solved by pencil and paper methods with enough ciphertext -- ciphertext 15 times the length of the key.
The same techniques can be used to break this cipher, given the same amount of ciphertext.
(Some of those techniques are mentioned at "
What is the limit of plaintext required to break the Vigenère encryption?
").


Algorithm or closed form solution that lets me directly compute the $n^{\text{th}}$ state of an LFSR? I have a large linear feedback shift register with a known state and taps.

Now I want to compute the state of the LFSR after $n$ iterations.

The problem: $n$ is in the order of $2^{256}$ so just brute forcing is not an option. Is there an algorithm or closed form solution that lets me directly compute the $n^{\text{th}}$ state?

If the initial state is $b_0,b_1,\dots,b_{k-1}$ and the recurrence relation is $b_k = \sum_{i = 0}^{k-1} a_ib_i$, then in linear-algebraic terms we have
$$ \begin{pmatrix}
b_1 \\ b_2 \\ \vdots \\ b_k
\end{pmatrix} = U \begin{pmatrix}
b_0 \\ b_1 \\ \vdots \\ b_{k-1}
\end{pmatrix}, $$
and more generally
$$ \begin{pmatrix}
b_{n} \\ b_{n+1} \\ \vdots \\ b_{n+k-1}
\end{pmatrix} = U^n \begin{pmatrix}
b_0 \\ b_1 \\ \vdots \\ b_{k-1}
\end{pmatrix}, $$
where of course
$$ U = \begin{pmatrix}
0 & 1 & 0 & \cdots & 0 \\
0 & 0 & 1 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & 1 \\
a_0 & a_1 & a_2 & \cdots & a_{k-1}
\end{pmatrix}. $$
And $U^n$ can be computed efficiently by standard exponentiation algorithms.


ASN.1 encoding off RSASSA-PSS default parameters I am not totally sure the question belongs to crypto and not stackoverflow but nevertheless...

The problem is the encoding of the RSASSA-PSS default algorithm identifier parameters in an X509 certificate.

During a test case we generate a certificate with the default parameters for PSS and try to import that certificate into an hsm.

The jca wrapper library around the pkcs#11 driver of the hsm rejects the certificate with an exception ala

Wrong parameters for an RSAandMGF1 algorithm identifier

The certificate in question is generated with bouncy castle and can be verified with openssl. The problem is that the algorithm identifier parameters in the certificate is a empty sequence.

RFC3447 A.2.2.3 states the following:

The parameters field associated with this OID in a value of type
AlgorithmIdentifier shall have a value of type RSASSA-PSS-params:

  RSASSA-PSS-params ::= SEQUENCE {
      hashAlgorithm      [0] HashAlgorithm    DEFAULT sha1,
      maskGenAlgorithm   [1] MaskGenAlgorithm DEFAULT mgf1SHA1,
      saltLength         [2] INTEGER          DEFAULT 20,
      trailerField       [3] TrailerField     DEFAULT trailerFieldBC
  }

and a few paragraphs later:

  If the default values of the hashAlgorithm, maskGenAlgorithm, and
  trailerField fields of RSASSA-PSS-params are used, then the
  algorithm identifier will have the following value:

     rSASSA-PSS-Default-Identifier  RSASSA-AlgorithmIdentifier ::= {
         algorithm   id-RSASSA-PSS,
         parameters  RSASSA-PSS-params : {
             hashAlgorithm       sha1,
             maskGenAlgorithm    mgf1SHA1,
             saltLength          20,
             trailerField        trailerFieldBC
         }
     }

     RSASSA-AlgorithmIdentifier ::=
         AlgorithmIdentifier { {PKCS1Algorithms} }

So it seems that bouncy castle is following the ASN.1 definition and returning an empty sequence for the default values. But if I read the last part it seems to me they still require the default values to be set and it seems the library we need to use enforces this.

So before writing a support ticket I just wanted to ask if I did miss something in the rfc or the certificate is really not valid.

Bouncy Castle is correct. Bouncy Castle contains a BER/DER encoder that changes ASN.1 objects into encoding by explicitly coding it that way - manually, as far as I understood. As this structure is represented using the distinguished encoding rules (DER) the structure should be empty. DER uses the minimum number of bytes to encode values.

DEFAULT ASN.1 values - just like XML default values in XSD schema's - should be filled in when the structures are parsed. So the HSM should automatically replace the values when parsing the data. If it doesn't contain a fully featured ASN.1 parser it may be that this needs to be coded explicitly (making this relatively vulnerable to implementation mistakes).

As I'm currently at home I'll use the venerable "A Layman's Guide to a Subset of ASN.1, BER, and DER" instead of directly quoting from the ITU-T X.690 / ISO/IEC 8825-1 specs:

  Contents octets are the same as the BER encoding, except that if the value of a component with the DEFAULT qualifier is the default value, the encoding of that component is not included in the contents octets.

Note that that quote is for the encoding of a SEQUENCE.


Finding Vigenère cipher key(s) How can we find the key used with a Vigenère  cipher in small number of steps?

If we have text like:

Peit Wokm! Mhfa fepatgb ets bvvrvxmea ebte bae twkd qiqi

and we have key information like Key =  ‘ ? a ? i ’, then how I can understand this and solve this to make the complete key?

You've been given the key length, plus half the characters in the key text. By the look of things, the ciphertext even contains word spaces and punctuation, which will help a lot.

Start by decrypting the text using the characters you already know:

> Peit Wokm! Mhfa fepatgb ets bvvrvxmea ebte bae twkd qiqi
  .a.i .a.i  .a.i .a.i.a. i.a .i.a.i.a. i.a. i.a .i.a .i.a
< .e.l .o.e! .h.s .e.s.g. w.s .n.r.p.e. w.t. t.e .o.d .a.i

Assuming the plaintext is English, it seems likely that the first character of the key is t, since this would decrypt the 5th and 8th words to was and the. Let's see how that changes things:

> Peit Wokm! Mhfa fepatgb ets bvvrvxmea ebte bae twkd qiqi
  ta.i ta.i  ta.i ta.ita. ita .ita.ita. ita. ita .ita .ita
< We.l Do.e! Th.s me.sag. was .ncr.pte. wit. the .ord .axi

Actually, you can stop here. It's already obvious what the message says.


Is there any hash function for which a preimage of a fixed element is always known? I'm wondering if there is any collision-resistant hash function $h^s(\cdot)$ satisfying that there is a fixed value $c$ such that, for each $s$, a value $x_s$ satisfying $h^s(x_s) = c$ is known. This would not contradict the collision-resistance property, nor preimage-resistance, but I have not been able to come up with any construction of this kind.

Does anyone know if this is possible, and if so, can point me to a particular construction?

Thanks

Some context...

I'm working on an exercise which asks to analyze the security of Merkle–Damgård transform when no $IV$ is used (or, equivalently, when it is set as the first block of the message). If a hash function like that I mention can be constructed, then I can build collisions on this construction.

Take any standard hash function family $\{h_s(\cdot)\}_s$, a point $c$ and a list of inputs $(x_s)_s$ and define $h'_s : x \mapsto h_s(x)$ if $x\neq x_s$, and $c$ otherwise. As you said, it does not contradict collision resistance or preimage resistance - in other words, you can prove that if $(h_s)_s$ is a family of (say) collision-resistant hash functions, then so is $(h'_s)_s$. If you have a collision on Merkle-Damgård applied to $(h'_s)_s$ without $IV$, then you are done. The existence of any collision-resistant hash function implies the existence of a hash with the properties you want, via this trivial method.


Number of cryptographic operations required to perform a MitM for 4DES Suppose DES is applied 4 times with 4 different 56-bit keys ($k_1$ to $k_4$). By using meet-in-the-middle attack, what is the number of cryptographic operations required for known-plaintext attack?

The given answer:

For each pair of $k_1$ and $k_2$, we need 2 encryptions and 2 decryptions.
There is a total of $2^{112}$ pairs. So the total required is $2^{114}$ cryptographic
operations.

I don't understand why there are 4 operations for each pair of keys. I thought each half of the attack requires ($2^{56*2} = 2^{112}$) operations so the total number should be only ($2^{112} * 2 = 2^{113}$) operations. What am I getting wrong here?

In MitM for 2DES, in a tabulation phase we compute and keep $2^{56}$ 64-bit values and their associated key, then in a search phase we compute up to $2^{56}$ 64-bit values and search these in the table. There's a hit about once in $2^{64-56}=2^8=256$ searches, that is about $2^{56-8}=2^{48}$ hits, and all except one are false hits. We need to eliminate false hits with a few extra DES operations: typically two, testing an extra plaintext/ciphertext pair². Further, a fraction of the 64-bit values have been obtained $k>1$ times in the first phase, and when we hit one of these in the search¹, the number of DES operations required to eliminate the false hit is $1+k$. All these details increase the number of DES operations by less than 1% from the base $2^{57}$ (for full search, or $3\times2^{55}$ on average), and some expositions neglect that detail³.

But if we implemented MitM for 4DES by precomputing $2^{112}$ 64-bit values, each 64-bit value would be obtained an average of $2^{112-64}=2^{48}$ times, thus in the search phase we'd be swamped in false hits: rather than rare (once in 256 searches) that would be the norm, and eliminating a false hit would need an average of $1+2^{48}$ extra DES. This is an unreasonable amount of extra work.

A simple line of though to attack 4DES is to attack using normal MitM the block cipher 2BIG, where BIG is a block cipher with double the key size and block size of normal DES (that is 112-bit key and 128-bit block size) obtained by applying 2DES with the 112-bit key on each 64-bit half of a 128-bit block, requiring two DES operations. MitM will theoretically³ break 2BIG in about $2^{113}$ evaluations of BIG (for full search), thus about $2^{114}$ evaluations of DES.

¹ Assuming we kept all the corresponding keys in the tabulation phase, which is required if we want to be sure the find a solution.

² When we get a confirmation with that second plaintext/ciphertext pair, most often we have hit the right pair of 56-bit key halves. But probability of the contrary remains about $2^{-16}$, so we want an extra check using a third plaintext/ciphertext pair, at a cost 2 DES operations.

³ There's an elephant in the room: even against 2DES, much more against 4DES, basic MiTM requires so much RAM and RAM accesses that the cost of DES operations is comparably negligible.