Why is it important to generate a pseudorandom permutation from a pseudorandom function? Most of the papers on block cipher constructions, especially the ones which discuss constructing block ciphers of arbitrary lengths or small domains, the techniques are designed based on building a PRP from a PRF. The ones that are based on Luby-Rackoff etc.

Why is it that the input message first to be processed by a pseudorandom  function and then followed by a pseudorandom permutation?  Why cannot we construct PRP straight from input message?

If you applied a PRF directly to the message to obtain cipher-text, you would not have the guarantee that you could actually decrypt the message.

Suppose the PRF maps $n$ bit inputs to some $m$ bit output.

The mental model of a PRF is as follows. You have have a gnome in a black box. When you hand him a string from the input space, he flips a coin $m$ times and outputs the result of these flips concatenated together. He then records this in his notebook so that if you pass the same $n$-bit input to him again, he can give you the same output.

If you think about this model carefully, you'll realise that there's actually nothing to stop two inputs mapping  to the same output. You just have to be lucky enough for a collision to occur. Due to the birthday paradox, this happens more often than you'd expect and there will typical be quite a lot of collisions.

Thus, if we try to encrypt our message directly with a PRF, there's no guarantee we'd be able to invert it!

A PRP is a PRF with the additional restriction that for every input value maps to precisely one output value and that every output value maps to precisely one input. With a PRP we're guaranteed to have an invertible function, which is precisely what we need to construct a block cipher.

In the PRP mental model, the gnome has a list of all possible output strings of length $m$. Every time he is passed an input he hasn't seen before, he selects an item from the list of output strings at random. He then removes this item from the list (so it can't be re-used) and writes in his notebook the input string and which output string he mapped it to. If he ever sees the same input again, he can then give the output he's recorded in his note book.

We can see that this construction is quite a bit more complex than the PRF set-up. The Luby-Rackoff construction is so neat because it gives us a nice way to convert a secure PRF in to secure PRP. There is a similar result for going to a PRF from a PRG, which is called the Goldreich-Goldwasser-Micali construction.

The end result being if you can build a secure pseudo random number generator you can also build a secure block-cipher. This is a neat result, which is why it's so often referred to in the cryptographic literature.


Why can’t the public key exponent in RSA be negative? I am looking at why certain public keys in RSA can't be used, such as:

2 and all other even numbers (since $\gcd(\phi,e)$ must equal 1)
1 (since the cipher text would equal the message)
0 (since the cipher text would be 1. Also because 0 has no
multiplicative inverse)

Let's say we have a message $m = 10, e = -3, N = 55$ then encrypting the cipher text would be: $m^{-3} = \frac 1 {1000} \mod 55$. Can we only use integers when writing in terms of a modulus?
Why can the public key exponent not be negative?

(Perhaps this is more of a maths question....Sorry)

Edit: Also, why can’t the public key exponent be greater than $\phi(N)$?

Why can the public key exponent not be negative?

Technically, it can be.  There's just no point to using such negative exponents in general, since for every valid negative RSA exponent, there is an equivalent positive one that is easier to calculate with.

Specifically, for any exponent $e$, message $m$ and modulus $n = pq$, changing $e$ by any integer multiple of $\lambda(n)$ $=$ $\operatorname{lcm}(p-1, q-1)$ does not affect the ciphertext $c = m^e \bmod n$.
This is because $\lambda(n)$ is the exponent of the multiplicative group of integers modulo $n$, and therefore $m^{\lambda(n)} \equiv 1 \pmod n$ for all $m$ coprime to $n$.  Thus, $$m^{e+\lambda(n)} = m^e \cdot m^{\lambda(n)} \equiv m^e \cdot 1 = m^e \pmod n.$$

(If $m$ happens to share a factor with $n$, then $m^{\lambda(n)} \not\equiv 1 \pmod n$.  However, since RSA moduli are squarefree, it is true that $m^{\lambda(n)+1} \equiv m \pmod n$ for all $m$, and so the conclusion $m^{e+\lambda(n)} \equiv m^e \pmod n$ still holds.  In any case, as noted below, having $m$ share a factor with $n$ is incredibly unlikely for RSA moduli of practical size.)

  Let's say we have a message $m = 10, e = -3, N = 55$ then encrypting the cipher text would be: $m^{-3} = \frac 1 {1000} \mod 55$. Can we only use integers when writing in terms of a modulus?

Yes, we only use integers in modular arithmetic.

But that turns out not to be much of a loss, since we can still calculate modular inverses, i.e. solutions $x$ to the equation $x \cdot m \equiv 1 \pmod n$.  For example, for $m = 8$ and $n = 55$, we have $7 \cdot 8 = 56 \equiv 1 \pmod{55}$, so $7$ is the inverse of $8$ modulo $55$.  Finding such modular inverses can be efficiently done using the extended Euclidean algorithm.

Alas, this doesn't quite work for all numbers.  For example, $10$ has no inverse modulo $55$, since $10$ and $55$ are not coprime; they both share the factor $5$.  But for real-world RSA moduli, which are products of two very large primes, it's extremely unlikely that you'll ever randomly stumble across another number that shares a factor with the modulus.  (And if you do, you've just factored the modulus by pure luck!)

Thus, if we really wanted to use RSA with negative exponents $e < 0$, we could just assume that any messages will almost surely be invertible modulo $n$, and calculate $$m^e = m^{-1 \cdot -e} \equiv (m^{-1})^{-e} \pmod n,$$ where $m^{-1}$ denotes the inverse of $m$ modulo $n$.  As long as $e$ is otherwise a valid RSA exponent (i.e. coprime to $\lambda(n)$, and not equivalent to $1$ modulo $\lambda(n)$), the math would work out just fine.

But there's still no point in using such negative exponents, since we can always convert any negative (or over-large) exponents into equivalent positive ones in the range $2 < e < \lambda(n)$ just by adding a suitable integer multiple of $\lambda(n)$ to them.  This does require knowing $\lambda(n)$, which implies knowledge of the factors of $n$, and thus of the private key.  But the code that generates the key will know that anyway, and can thus ensure that the exponents lie in the proper range.

In particular, while it would be mathematically possible to work with negative RSA exponents, I'm not aware of any practical RSA implementations that would include the extra complexity needed to support them.

  Also, why can't the public key exponent be greater than $\phi(N)$?

Technically, it can be, but again, there's no point in using exponents larger than $\lambda(n) < \phi(n)$, since using an over-large exponent would just waste CPU time for no good reason, compared to using an equivalent smaller exponent.

In particular, some RSA key generation standards require the exponents to be positive and less than $\lambda(n)$, and most RSA implementations will only accept positive exponents (and may require them to be less than $n$).  See this related question for more information.


How does one practically calculate the non-linearity of a multi-output boolean function like the AES s-box? I am working on multi-output boolean function i.e. a function that takes an $n$-bit input and gives an $m$-bit output for all possible inputs (i.e. $2^n$ inputs).

To be more exact: I am trying to do a cryptanalysis of the AES 8x8 s-box, with the goal to learn the whole procedure of finding/calculating non-linearity.

Doing some research, I learned that I need to find the minimum hamming distance from all $n$ variable affine functions. Sadly enough, I don't  really grasp all of the math which would be required to find the non-linearity.

In the end, I’ld like to be able to calculate the Linear Approximation Table of the AES s-box. Can someone please explain how to build a LAT of the AES Sbox. How can I practically calculate the non-linearity of a multi-output boolean function like the AES s-box?

Before we start with vectorial Boolean functions, let's recall the definition of the nonlinearity of a Boolean function:

$$\mathcal{NL}(f) = \min_{a \in \mathbb{F}_2^n} d_H(f, \ell_a \oplus b),$$

where $\ell_a \oplus b$ represents the affine Boolean function defined by the bitvector $a$: $\ell_a(x) = a \cdot x$ ($\cdot$ is the dot product).
The above equation pretty much defines the nonlinearity of a Boolean function as the minimum Hamming distance $d_H$ to some affine function.

This distance $d_H$ can be expressed using the Walsh-Spectrum of $f$.
That is, $d_H(f, \ell_a) = 2^{n - 1} - \frac{1}{2}\mathcal{W}_f(a)$.
To see why this is true, the definition of the Walsh transform should help:
$$\mathcal{W}_f(a) = \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x) \oplus \ell_a(x)}.$$
(and note that $(-1)^{g(x)} = 1 - 2g(x)$, $\sum_x g(x) = w_H(x))$)

Minimizing the distance hence corresponds to maximizing the Walsh-Spectrum:
$$\mathcal{NL}(f) = 2^{n - 1} - \frac{1}{2} \max_{a \in \mathbb{F}_2^n} \left|\mathcal{W_f(a)}\right|.$$

Why the absolute value? Remember that we're measuring the distance to affine functions and note that $d_H(f, \ell_a \oplus 1) = 2^{n - 1} + \frac{1}{2}\mathcal{W}_f(a)$.

Why is this useful? Well, it turns out there is a rather efficient algorithm to compute the Walsh-Spectrum of some Boolean function. See for example here.

Now that we can compute the nonlinearity of a Boolean function, it's easy to define that of a vectorial Boolean function $F$:

$$\mathcal{NL}(F) = \min_{a \in \mathbb{F}_2^n} \mathcal{NL}(F \cdot a).$$

In other words, the nonlinearity is the minimum of the nonlinearities of the Boolean functions which are linear combinations of the coordinates (outputs) of $F$.

Given what we know about the nonlinearity of Boolean functions, we can compute this as

$$\mathcal{NL}(F) =  2^{n - 1} - \frac{1}{2} \max_{a \in \mathbb{F}_2^n, b \in \mathbb{F}_2^m} \left|\mathcal{W}_{F\cdot b}(a)\right|.$$

Sometimes the expression in the absolute value is called the Walsh transform of $F$:
$$\mathcal{W}_F(a, b) = \mathcal{W}_{F\cdot b}(a)$$

To compute this, you can use the fast Walsh-Hadamard transform (FWHT) algorithm again.
Note also this corresponds directly to the LAT (depending on conventions, the term $2^{n - 1}$ is added or not).


Decrypt authenticated cipher while still encrypting Normal AES-GCM generates an authentication tag at the end of encryption. I want to decrypt it while it is still being encrypted. This would be useful to send, encrypt, receive and decrypt a large file (for example) in one go.

This would also be useful for other things like for video streams or encrypted calls. How could I do that? Switching to CBC seems like a bad idea.

AES-GCM can be used as a as stream cypher by splitting the input to multiple blocks along with a nonce. However using AE for each block may not be an efficient technique.

See this topic
Also read this post.


Reed Solomon secret sharing and as a one-time symmetric key? Shamir's Secret Sharing is just a special case of Reed-Solomon where only one coefficient is used to store the secret instead of the entire polynomial.

Sarwate however, suggests that the latter can be done by sacrificing information theoretic security:

  The second aspect of Reed-Solomon coding schemes considered in the
  McEliece-Sarwate paper is that it is not necessary to fill up $S(x)$
  with $m-1$ randomly chosen symbols.  In fact, the secret can be all
  $m$ symbols $s_0,\ldots,s_{m-1}$ instead of just $s_0$ being the
  secret.  One advantage is that we can use a smaller finite field.  If
  the secret is $1000$ bits, say, and $m=10$, Shamir's scheme would
  operate over $\mathbb F_{2^{1000}}$ and each share of the secret would
  also be $1000$ bits long. $10$ kilobits ($10$ one-kilobit shares)
  would be needed to  recover the secret.  On the other hand, a
  Reed-Solomon coding scheme could divide the secret into $10$ $100$-bit
  symbols and operate over $\mathbb F_{2^{100}}$.  Also each share would
  be $100$ bits long, and, as before, only ten such short shares would
  be needed to recover the secret.  This reduction in the field size
  does come at some cost in security.  If only $9$ shares are available
  to a cabal and they guess at possible values of the tenth needed
  share, they can come up with a  "short list" of only $2^{100}$ values
  that the $1000$-bit secret might have.  Shamir's scheme in a similar
  predicament would have a list of $2^{1000}$ possible values of the
  secret, thus providing perfect security.  The trade-off between
  reduction in security and ease of implementation as well as storage of
  each share of the secret is something that needs to be evaluated for
  each application.  The most secure scheme has shares that are as long
  as the secret while the Reed-Solomon scheme can be used to reduce the
  share size at the cost of reduced  security.
  source

Has anyone else agreed with Sarwate on this? Is it proven to be true?

Suppose you have a $10,000$-bit secret which you split into $100$ $100$-bit shares. Being in possession of $99$ shares can you really not learn anything about the $10,000$-bit secret even if parts of it are known or can be guessed? With complexity less than $2^{100}$.

And wouldn't it imply that this can be used to encrypt? The last share can be withheld from source of data and be effectively its encryption key.

Suppose the 10 000-bit message is uniformly distributed and we split it with a $t$-of-$n$ scheme.

With Shamir's secret-sharing where each share is 10 000 bits apiece, if you have only $t - 1$ shares, the $t^{\mathit{th}}$ share has $2^{10~000}$ possible values with uniform distribution, and so the conditional distribution on the secret given $t - 1$ shares can (and does) have 10 000 bits of entropy.
With a conventional erasure coding scheme like Reed–Solomon where each share is 100 bits apiece, if you have only $t - 1$ shares, the $t^{\mathit{th}}$ share has only $2^{100}$ possibilities to determine what the secret could be, so the conditional distribution on the secret given $t - 1$ shares can't have more than 100 bits of entropy—in other words, you can narrow the secret down to a minuscule fraction of the possible subspace.  (If it had fewer than 100 bits of entropy, then it wouldn't be a very efficient erasure code.)

The question you might ask is: Which subspace of the message space does the erasure code use?  Here's a simple 2-of-3 scheme, sometimes called RAID-5: divide the secret into 5000-bit halves $s_1$ and $s_2$, and use $s_1$, $s_2$, and $s_1 \oplus s_2$ as the shares.  A single share reveals a lot about the original message!  So, not very useful for encryption.

What about Reed–Solomon?  We interpret a $t\ell$-bit message $m = (m_0, m_1, \dots, m_{t-1})$ as a degree-$(t - 1)$ polynomial $m(x) = m_0 + m_1 x + m_2 x^2 + \cdots + m_{t-1} x^{t-1}$ over $\operatorname{GF}(2^\ell)$, and evaluate it at $n$ distinct points, say $\{0, 1, \alpha, \alpha^2, \dots, \alpha^{n-2}\}$ where $\alpha$ is a generator of $\operatorname{GF}(2^\ell)$.  Note that the first two shares in this perfectly reasonable choice of Reed–Solomon code are $m_0$ and $m_0 + m_1 + m_2 + \cdots + m_{t-1}$.  Still not very useful for encryption.

‘But you just chose the evaluation points pathologically!’  Well, OK, but let's say you used $\{\alpha, \alpha^2, \dots, \alpha^n\}$ for fixed $\alpha$.  There's a trivial known-plaintext distinguisher for a ciphertext $(c_1, c_2, \dots, c_{t-1})$ and key $c_t$ where $c_i = m(\alpha^i)$: simply evaluate the polynomial at the evaluation points and compare to the putative ciphertext.

What if $\alpha$ were part of the key too?  Well, then $\alpha$ is one of the at most $t - 1$ roots of the degree-$(t - 1)$ polynomial $m(\alpha^i) - c_i$ for each $i$, which we can compute in a known-plaintext attack by standard root-finding.

What if we randomize the first message block too?  Well, there distinguisher still basically works except we have to see whether $m(\alpha^i) - c_i$ (here $m$ is taken to have zero constant term) is the same randomized first block for all $i$.  We could randomize all but one of the message blocks, but then we're just back to Shamir's secret-sharing.

There's another way: We could apply an all-or-nothing transform (AONT), and then use one of the shares as a secret key.  With an efficient erasure code, this is obviously as secure as the AONT itself.  (AONTs were not developed until well after the McEliece–Sarwate note.)

There's still a practical problem with using this as a cipher: How does the recipient get the key if it is determined by the plaintext?  Maybe you actually want a public-key cryptosystem, but it's not clear to me how to get one out of this—although you can get one out of other error-correcting codes, also due to McEliece, where you encapsulate a secret key in the syndrome of a random error under a hidden Goppa code, and derive a key by hashing the error.

So, this idea is mainly useful for storing a message that is already randomized like a large secret key, where knowledge of part of it doesn't help.  Of course, if we want to make sure that the subspace of messages covered by an incomplete set of shares is at least (say) 256 bits for modern security, we might as well just make the secret be 256 bits itself and use a key derivation function to derive a larger key from it.  For storing longer structured secrets, the McEliece–Sarwate is slightly more efficient than just encrypting them, splitting the ciphertext with Reed–Solomon, and splitting the key with Shamir.

Maybe there's a broader use for the McEliece–Sarwate observation but it's not obvious to me!

The standard caveat about secret-sharing applies too: Whenever you reconstruct the secret, someone has to have the whole secret in one place to use it, and could sequester it away.  So if you ever use it, there's a single party with unilateral access to whatever power the secret grants.  Many applications for which secret-sharing might be tempting are better served by higher-level multiparty computation like threshold signatures where no party ever has unilateral power of some central secret.


Why IV does not have to be secret yet has to be random The IV used in schemes such as CBC has to be random and unpredictable. But at the same time it does not have to be kept secret.

If the IV does not have to be secret, why does it have to be random then? I fail to make sense out of these seemingly contradicting requirements.

I have seen descriptions of attacks which exploit the non-randomness. So, I would understand why randomness is needed. However, things get confusing when the requirements specify that the IV does not have to be secret !This seems to defeat the whole purpose of randomness.

Somebody help clarify this please.

OK! This won't be the best answer I can give, but since I know a fair bit about this subject, CSPRNGs (Cryptographically Secure Pseudo-Random Number Generators), also known as Dertemistic Random Bit Generators (DRBGs).

Now your question asked about CBC, so I'll come onto that second, first I want to give a slightly less technical/broad answer, I'll give you an example of where the importance of IVs are crucial.

Let's assume we had a STREAM CIPHER (asin RC4, which is in itself full of problems, but that's not what you asked). In WEP, RC4 was using IVs extremely badly, but let's assume there's a bunch of alterations you can make to RC4 to make it significantly stronger (albeit, less elegant).

In this circumstance, because we have a stream cipher, the vulnrability to plain-text-attacks is very high, that's because if we use the same key more than once, then the relationship between any two texts using that same key is known , this means that if we can guess the plain text, this is often the case in practical everyday transmissions, then firstly we know EXACTLY what the key stream is and from there, finding out the initial key is pretty trivial.

So we NEVER want to use the same key twice for any encryption... Block Ciphers, Stream Ciphers, whatever.

OK So an IV can be used in many ways, the reason I bought up WEP was say you were using a 64-bit key, then to make sure no two "keys" were the same, the IV would act like a nonce, that is, the effective key used for key-scheduling would be (IV|Secret), now as I said, this particular implementation was awful but here's the point.

WE NEVER EVER WANT TO HAVE THE SAME KEY TWICE... There's plenty of ways of achieving this.

Now in WEP implementation of RC4, using (IV|Secret) as the initial key where "Secret" is 40 bits and "IV" is 24 bits, this means there's only 2^64 possible keys, however more importantly if we use the same "secret", then there's only 2^24 (16,777,216) different keys you can create from the same secret... since the 40 bit key is just 5 random bytes chosen or derived from the user. 16,777,216 is a laughably small number and infact, we will find two instances of (IV|Secret) that match half the time inside about 4300 key-streams, providing the "secret" doesn't change. So that was one example of using an IV failing spectacularly.

So if we imagine that our key for any encryption is HMAC-SHA256(IV,Secret), then we can afford for the IV to be the same size as the Secret, as there will be 2^128, that is over 3 * 10^38 and there will also be this many possible IVs, so even if we KNOW the IV and it's being used more or less as a nonce, although HMAC-HASH(IV,Secret) is better than simply using HASH(IV|Secret)... once we have done this, we can PUBLICLY REVEAL what the IV was. Presuming we use a good CSPRNG and a good HASH function, then to attempt a known-plain-text-attack, we would not take a single guess and reveal a fair amount of info, instead we would have to use over 3*10^38 guesses.

This isn't ideal but the point is.... the IV does not to be secret because the IV is there to make sure realistically known-plain-text attacks are significantly more complicated... in my example it becomes 2^128 times more complex to launch a known-plain-text attack OR partially-known-plain-text attack.

In a nutshell one of the primary functions of IVs is to make sure no two encryptions are the same or at very least, finding two the same is exponentially more difficult.

If you want more clarity, just ask. This isn't exactly a well written essay, but I thought I'd have a crack at shedding some light on this question. If needed, I could write a much more technical answer.


Disk/File modes of encryption and authentication Secure disk/file encryption has been actively studied over the years. Beside XTS and CBC-ESSIV, are there any other modes of encryption that are commonly used? Which could be the most secure mode?

Due to the non-existence of integrity and authentication mechanisms, what are good methods to prevent a malicious person from modifying the data?

I am looking for a practical scheme that meets security and does not significantly impact performance.

Beside XTS and CBC-ESSIV, are there any other modes of encryption that
  are commonly used?

No. Just look at software like Veracrypt (XTS only) or dmcrypt.

There was a third notable scheme for this purpose, LRW, but it's deemed not secure enough:

  The issues of LRW were:

  a) An attacker can derive the LRW tweak key K2
  from the ciphertext if the plaintext contains K2||0n or 0n||K2. Here
  || is the concatenation operator and 0n is a zero block.[3] This may
  be an issue for software that encrypts the partition of an operating
  system under which this encryption software is running (at the same
  time). The operating system could write the LRW tweak key to an
  encrypted swap/hibernation file.

  b) If the tweak key K2 is known, LRW
  does not offer indistinguishability under chosen plaintext attack
  (IND-CPA) anymore, and the same input block permutation attacks of ECB
  mode are possible.[4] Leak of the tweak key does not affect the
  confidentiality of the plaintext.

(from https://en.wikipedia.org/wiki/IEEE_P1619#LRW_issue)

  Which could be the most secure mode?

Depends on your requirements.

Both modes:
If the attacker can monitor changes of the data made by you (sounds like the attacker stole your computer, added something between harddisk and mainboard and gave it back), or at least get multiple copies at different point of times:
The attacker can do some traffic analysis, eg. he/she can detect if some block changed back to some data it had in the past. Ie. if you have a block has A, you change it to B, and later back to A (the same block, not different ones), then the attacker knows that the current content was there in the past too.
There's no real protection against this, but as said above, the attacker needs to monitor changes. Just stealing the laptop or anything like that is not enough (and if you get it back, don't trust it anymore, as simple as that. There are thousands of things that could be done while you weren't watching, many of them worse than just sniffing encrypted content).

XTS:
An attacker with similar monitoring capabilites, and also the possibility of changing blocks too, can roll back changes.
With the same A-B-A as above, (of course) the attacker can change your A block back to the B it was before (without knowing the unencrypted content, but still).
Just as reminder, overwriting the ciphertext is always possible, resulting in garbage after decryption. But here, it's not garbage, it's your own outdated content.
Tree-like integrity/authentication schemes (see below) mitigate this, but to be acceptable fast it needs to be integrated in the file system.

CBC-ESSIV:
It's always possible to change specific bits in the plaintext (even without monitoring changes or anything), if the attacker is willing to destroy another block for each changed block (=half of the blocks).
Again, tree-like integrity/authentication schemes mitigate this.

...if you want my opinion, XTS+auth.

  what are good methods to prevent a malicious person from modifying the
  data?

What you should NOT do:
Take every 4096byte-block (or some size like that), use eg. 4076 byte for data and 20 for an HMAC. Because
a) it doesn't solve parts of the problems above (eg. for XTS, replacing a block with it's old content means the old HMAC is there too ... failed); and
b) it's a mismatch with what OS+programs usually want. If the OS reads 8192 bytes (2*4096), you need a third block because the first two contain 40 byte HMACs and just 8152 byte data. A 4096 block for 40 byte... Then, when the OS wants the next part of the file, you either need to read the same block again (even slower, because non-sequential) or implement some sort of caching, which gets very cumbersome.

What you should NOT do either:
Collect the HMACs in own blocks. 4096/20 is about 204, so each 204 data blocks are followed by one block full of HMACs.
a) This does not solve the replacement problem either (the attacker can just replace a chunk of 205 blocks), and
b) It's even slower, because for every block you read/write, you also need the hash block which is far away (non-sequential to it's best).

What you could do on block-only-level (more secure but still slow):
Start like the solution above (full hash blocks), but also insert a second level of hash blocks (err, MAC blocks) for each eg. 200 hash blocks, a third level for each 200 second-levels, and so on, until you have one top block.
With this, replacing single blocks or any larger parts always can be detected, unless the attacker changes everything, ie. the whole disk content, back to it's old content etc. (this part can't really be solved with crypto. It's like exchanging the whole hard disk with one containing your old data. To mitigate this, you need to store the top block securely outside if the hard disk).
Problem is, again, slow because of non-sequential access. And calculating where the X-th data block is becomes a bit cumbersome because of the levels.

It won't get more secure. But depending on what you want to do, the slowness problem can be solved too: Don't do it just with blocks, without knowing their purpose, but integrate the hash tree into the file system.
There's no need to fetch additional blocks for the hashes, because they can be in the same place where filenames etc. are stored too. And knowing what blocks belong to the same file, detecting the programs access patterns for proper caching, etc.etc., all can be applied to the hash part too.


Bad/Crackable Encryption Example? I've been tasked with building up some security exercises (basic CTF training kind of stuff) for work. This should contain a bit of crypto, but my knowledge in this space has been limited to using the right tools, not trying to roll my own, etc, so coming up with an example of bad crypto, but believably real, has been tough.

Specifically one of the flags would be encrypted, say a simple sentence, in a way that would be crackable, allowing for recovery of the plaintext with a bit of know how and some burned cpu.

Could someone point me to an example like that?

Thanks for any input.

Start with the Caesar Cipher.  It is important to know the flaws and important for students to know the history of it.  It would be quite easy to break considering the background of the learners.  You probably want to include the algorithm as well as the cipertext.

From here you can build more advanced problems since they have the basic understanding of what's going on.

LM Hash
Small Keys
WEP

Simple problems, but we must crawl before we can walk.


feistel cipher and number of rounds In feistel cipher , does it matter that number of rounds be 16 ? is using 16 rounds will give the best result ? Or using any number of rounds is the same?

in cryptography and network security by william stallings we have : "The  essence  of  the  Feistel  cipher  is  that  a  single  round
offers  inadequate  security  but  that  multiple  rounds  offer  increasing  security.
A typical size is 16 rounds."

a typical is 16 but what's the efficient number ?

There is a minimal number of rounds for theoretical security. 4 rounds are required to construct a strong pseudo random permutation (PRP) from a pseudo-random function (PRF).

In practice, cryptographers don't tend to design ciphers with a heavy PRF for the f-function but instead apply more rounds with a weaker f-function to get the requisite strength.

For this reason, there is no typical or default choice for the number of rounds in a Fiestel cipher. The optimal choice depends entirely on the internal security properties of the key schedule and F-function for the specific cipher in question.


Encryption algorithm multiple threads/cores for higher throughput There are situations where a single connection (or file) may require additional throughput available. While network bandwidth and CPU cores are available, they cannot be utilised. (Aside from means that are external to the algorithm as is)
Some examples:

VPN - when encryption is done only on the tunnel connection that internally encapsulates packets of multiple flows.

Typically, it is thought that an encryption algorithm itself is a sequential process, that relies on the previous block or bit(s) in order to accomplish effective cipher strength. This means the algorithms cannot be multi-threaded.
Is this true of all encryption? Does this apply equally to modern common algorithms (block and stream)?
Is there a way to purpose-make an encryption algorithm that works on multiple threads (cores)? Are there any existing algorithms (perhaps not common or academic only) that would work across multiples cores?
Usually, this isn't a problem, because machines may make use of multiple connections (HTTPS), but it means a single connection is limited by the cipher transform speed of a single CPU core. Also, when multiplexing is used (like VPN), this might be a particularly limiting issue.

Typically, it is thought that an encryption algorithm is a sequential process, that relies on the previous block or bit(s) in order to accomplish effective cipher strength. This means the algorithms cannot be multi-threaded.

This is only true for "heavy-handed" operations like CBC-MAC (and its variants), HMAC and CBC. For most of modern cryptography as implemented, parallelizability is both a feature an a necessity for high performance implementations.
Before jumping to the schemes that are relevant to you in this context, let me clarify why parallelism is actually a necessity. You might have heard of the AES-NI. These are instructions that perform one AES round per instruction. However, the instructions don't have a latency of 1 CPU cycle but of 3-7 CPU cycles even though they have a throughput of at least 1 instruction per cycle. Latency in this context means that if instruction B depends on the result of instruction A, B must wait for the full latency of A. So, what you need to do to optimally use your hardware is to have 8 data-independent AES operations be run in parallel which is quite tricky with request-level parallelism. So instead what schemes do, is they use a parallelizable scheme and don't compute one block of AES data at a time, but rather 8 or however many is optimal for the implementation.
But how can this be done, you surely ask yourself:

If you want CPA-secure encryption, CTR-mode transforms a block cipher into a stream cipher by encrypting a counter.
If you want a nonce-based MAC, GMAC can be parallelized - which is commonly exploited to reduce the number of reductions to compute.
If you want a full-blown parallel PRF, PMAC is the way to go, though it is not seen as often in practice due to the prominence of HMAC or single-block AES where needed.
If you want a parallel hash algorithm, you can use tree-hashing.
If you want authenticated encryption, AES-GCM can be parallelized - as it is essentially composed of GMAC and CTR.
If you want nonce-misuse-resistant authenticated encryption, the generic SIV transform and AES-GCM-SIV both require two passes but each pass can be parallelized - at least for the encryption, the decryption is natively parallel.


Attacking a cipher, not knowing what the plaintext should look like – how do you know you’ve successfully decrypted the ciphertext? I have thought hard at the risks of data being cracked, it seems to me that the biggest risk is still down to absolute security of the key.  On the presumption that the key will be kept secure then:

When hacking data how do you decide when you have successfully
decrypted it without knowing roughly what it was it the first place?
If it was a text document would you need to know what language it
was in?
Is it worth the minimal effort of making the users key more complex
before using it to encrypt the data?

OK, I am very definitely not a mathematician, self evident I guess.  I am using a library (Lockbox 3, https://sourceforge.net/projects/tplockbox) for the en/decryption and so am dependant upon the implementation being rock solid, another potential hole but I am casting no aspersions on the developers.

If one was attempting to crack the data are there mathematical mechanisms which can be used to decrypt without know anything about the data?  I'm not asking for an algorithm, a yes or no will do.

I am asking for a complex subject to be made simple, however I am only after broad answers.

To address your first question, below are two fragments of text.  One of them is gibberish I copied from /dev/urandom; the other is a literary quotation of the same number of octets.  Each sequence of octets is written with graphic US-ASCII characters verbatim, and with control characters and non-US-ASCII octets written using \xAB hexadecimal notation.  Can you tell which is which?  (I randomized the order of fragments by flipping a coin, too.)

Kas siis selle maa keel / Laulutuules ei v\xc3\xb5i / Taevani t\xc3\xb5ustes \xc3\xbcles / Igavikku omale otsida?
\xe4xz\xfd\x11?\xbb\xfa\xeb\xb3a\x02Z\xe0\xdc_\xc3\xd3\x92\xa4ssa\x1an\xab\x1aa\x15\xa8\x02\xa5r}\xbe\x8f\xbc\n\xe5\x80\xd0B\xbeH\x17\xfex\x03\xd6\x99\x1d\xde$
\x89\xb4G\xd1\xea\xfb\x13@~\x87)\xb9\xd9\xcc\x18\x81\x01\x03$\xf23\x91\xb5c\xd0\xd1\x17\x11r\xee1"!\x03UiGB\x16\xc3{\xa0

(No cheating by knowing how to read Estonian!  We can do the exercise with a different language if you do read Estonian.)

To address your second question, suppose you didn't know it were Estonian.  It is highly unlikely that any language's orthography represented in octet strings has a uniform distribution, so you might, e.g., perform a statistical test to reject the null hypothesis of a uniform distribution, like a standard undergrad-statistician's $\chi^2$ test of bit or octet frequencies.  There is no way to make it ‘more complex’—there are already $2^{256}$ possibilities, each one having equal probability.

Finally, to address you third question, your obligation to satisfy the AES-256 contract is to provide a key chosen uniformly at random from all $2^{256}$ possibilities.  Normally you do this by asking your computer to do it for you, e.g. by calling on a hardware random number generator or by flipping a coin 256 times to seed your software random number generator.

If, however, you must deterministically derive a key from a password, then you should use a modern password-based key derivation function like scrypt or argon2.  A PBKDF is expensive to evaluate, which means the cost of testing a guess for a password is high, with some variations in the cost model—older ones like PBKDF2 consider only time cost on a sequential machine, whereas newer ones like scrypt and argon2 consider area*time cost on an arbitrarily large piece of silicon that may have many CPUs or lots of memory.  In some sense, a PBKDF behaves almost as if the password space were larger and the entropy of the password selection process were larger, because the expected cost of an attack is as much higher as if the entropy of the password selection process really were higher.


Are all homomorphic encryption schemes based on latticed-based schemes? PALISADE offers a pool of Homomorphic Encryption schemes and it is stated that "PALISADE is a general lattice cryptography library ...". My question is rather simple: are all homomorphic encryption schemes based on lattice-based cryptography?

It depends what you mean with "homomorphic".
If you mean "compact and fully-homomorphic" (i.e., one can evaluate arbitrary polytime-computable functions on the ciphertexts, and the ciphertext size does not grow with the function being evaluated), then the answer is essentially yes. All known fully-homomorphic encryption schemes with compact ciphertexts use lattice techniques. Note, though, that this requires interpreting "lattice-techniques" in a relatively broad sense. Indeed:

One can build FHE from indistinguishability obfuscation (here). In essence, this is a construction of a very different nature compared to standard lattice-based constructions. However, all known modern candidate constructions of iO use LWE somewhere (among other, sometimes non-standard, assumptions). See e.g. here, here, and here for the three latest results on this front. Also, any FHE built using this line of work would be completely inefficient in practice.
One can build FHE from different assumptions related to approximate GCD, see this work. However, while the assumption is formally different, this employs essentially the same approach and ideas, but simply instantiated in a different setting that does not directly involve lattices.

If you do not mean "compact and fully-homomorphic", then no. More precisely:

If you do not insist on compactness, there are generic methods to make any encryption scheme fully homomorphic - but the ciphertext will grow exponentially with the size of the evaluated circuit in general. See e.g. this work and this work.
If you want compact ciphertexts, but not necessarily the ability to evaluate arbitrary functions, then there are many homomorphic encryption schemes around. (Textbook) RSA is multiplicatively homomorphic. The additive variant of ElGamal is additively homomorphic when the plaintexts are small enough. Goldwasser-Micali is homomorphic for the XOR operation. Paillier is additively homomorphic over $\mathbb{Z}_n$. BGN allows to evaluate degree-two polynomials, provided that the plaintext remains small. In addition, there are generic techniques to boost these limited homomorphisms (e.g. boosting degree-1 to a subclass of degree-2 polynomials), see e.g. this work.


Which algorithm should be used to replace SHA512withRSA? We are working on the web application that is basically generating a self-signed certificate during the installation. It's a Java based app and for generation of the certificate we are using SHA512withRSA. Can I ask what would be the best replacement for it? Something with better encryption level and more 'modern' security?

Any help would be appreciated.

--
Best regards
macosxgeek

In standard Java libraries, SHA512withRSA designates signature per RSASSA-PKCS1-v1_5 with SHA-512. There is no known attack when used with a sufficient RSA modulus size, and SHA-512 is very secure. Given that SHA-512 has a 19-byte DER DigestInfo prefix, and that PKCS1-v1_5 signature further requires 10 bytes and 1 bit more for the modulus, we can tell from the question that the RSA public modulus size is at least 1+(10+19)×8+512=745-bit, but that's far from satisfactory.

The only truly indispensable thing to do is check that RSA public modulus size. Anything below 1024-bit is unsafe, anything below 2048-bit is to upgrade ASAP, when performance is no issue 4096-bit is reasonable, unless we care about quantum computers usable for cryptanalysis, or fairies (there's abundant literature about both).

It might be useful to also switch to RSASSA-PSS (which has a better security argument), but that's a bigger change (including in Known Answer Tests, since RSASSA-PSS signatures change randomly for the same data). It should also be ascertained that MFG1 in RSASSA-PSS does not use SHA-1; that would not be insecure, but is criticizable nevertheless, and often creeps in upgrades from RSAES-PKCS1-v1_5 to RSAES-OAEP in Java code, see this.


Inversion Free Direct Conversion between Twisted Edwards (X,Y,Z) and Montgomery (X,Z) The Wikipedia page for Montgomery curves shows how to convert points on a twisted Edwards curve to and from points on an equivalent Montgomery curve. However, their description and the original twisted Edwards curve paper use affine coordinates for the conversion.

Is it possible to convert directly from projective twisted Edwards coordinates (X,Y,Z) to projective Montgomery coordinates (X,Z) and back without expensive inversions in the underlying field $\mathbb{F}_p$? Does anybody know explicit formulas for this or a method on how to produce the projective equivalent of the description found on Wikipedia?

The ultimate goal is to convert to Montgomery points with as little cost as possible, do the scalar multiplication using cheap Montgomery arithmetic and at the end convert the point back to twisted Edwards coordinates.

The conversion formula from twisted Edwards to Montgomery form is:

$$x_{mont} = \frac{X_{mont}}{Z_{mont}}= \frac{1+y_{ed}}{1-y_{ed}} = \frac{1+\frac{Y_{ed}}{Z_{ed}}}{1-\frac{Y_{ed}}{Z_{ed}}} = \frac{Z_{ed}+Y_{ed}}{Z_{ed}-Y_{ed}}$$

If you want the affine $x_{mont}$, you need to compute the inversion. But if you just need $X_{mont}$ and $Z_{mont}$ you can skip the inversion, since the nominator is X and the denominator Z.

$$X_{mont} = Z_{ed}+Y_{ed}$$
$$Z_{mont} = Z_{ed}-Y_{ed}$$

Some additional notes:

If you use $Z \neq 1$ as input for the Montgomery ladder, this will increase the cost of this scalar multiplication by more than the cost of an initial inversion (about 10% of the ladder cost).
If you really need to minimize the cost of inversions, you might want to use batch inversions, which can compute the inverse of multiple values, available at the same time, with a cost only slightly higher than a single inversion.
At the end of a scalar multiplication you need to compute an inversion, no matter which form you use, since you want an affine output. In that case you can convert between forms for free, since you can merge the inversions into a single one.
When using the cheap X,Z Montgomery ladder and convert back to twisted Edwards, you get $Y$ and $Z$. You can recover $|X|$ from that using the curve equation (essentially a point decompression, cost similar to a field inversion), but you don't know the sign of $X$.
Variable base-point twisted Edwards isn't much more expensive than Montgomery if you can afford the memory for the lookup table.


AES 256 CBC - Storing local data, how to save IV vector? I want to use AES256 CBC for protecting small data (<100kb) against misusage for my application in the local store folder. I'm not an expert at data encrypting so I'm to try to understand it step by step.

I want to just make sure myself that I understand it well. I have a key for decrypting/encrypting and then IV which I generate for every new encrypting. And because IV is not a secret I can append it at the end of data something like that: encrypted data + IV and then during decrypting I just read the last 16 bytes and use the IV for decrypting. I'm right? Or is there any error I don't see?

My main intention is to hide data from the user and not allow them to change the data. So maybe, it would be better to use Authenticated Encryption (GCM?). What do you think? There are a lot of types of encryptions and I can't decide for any.

I'm using the OpenSSL library.

If you are using AES-CBC, You can store the IV however you like.  It is not important to keep the IV secret; you just need to make sure that an adversary cannot predict the IV in advance.

However, you have the right intuition that you should generally always use an authenticated cipher like AES-GCM.  AES-CBC is bad for other reasons too having to do with padding—AES-GCM provides a much better security contract all around than AES-CBC.  For AES-GCM, the only requirement of the nonce—sometimes also called an IV—is that it must be distinct for every message: you cannot reuse a nonce between two messages under a single key, and the consequences are fatal if you do.

That said…

  My main intention is to hide data from user and not allow them to change the data.

…it sounds like you are treating the user of your software as an enemy on their own computer.  If you're trying to do some kind of digital restrictions management (DRM) scheme, forget about it.  Not only is this hopeless—if it's happening on the user's own computer, the user can get the key anyway—but it is morally wrong to try to commandeer your users' own computers to work against their interests, and then penalize the ones who lack technical competence to work around your abuse of authority to run code on them.


Using bcrypt for MAC - is it correct and secure? Suppose there is a hashing function:

$$ph = bcrypt(sha256(m + k), salt)$$

Here $ph$ is a password hash obtaining by applying $bcrypt$ on $sha256$ result of concatenating a message $m$ with a secret key $k$. Assuming that

key $k$ is not visible to attacker;
key is a "truly" random sufficiently large string;
the work factor of $bcrypt$ is sufficiently large as well;

The question is how much is this schema secure? Can an attacker obtain the secret key $k$ by issuing messages $m$ and retrieving hashes $ph$ and how much efforts will it take? How much does the strength of this schema depend on the size of the key?

Are there any ways to improve this schema?

I thought such schema may be used for MAC. Should I use HMAC+SHA512 instead?

Although your scheme is secure - especially with a random key of 32 bytes or higher - it won't offer any benefit over HMAC. It's therefore not recommended to use such a scheme.

Also note that `bcrypt has been designed for key stretching which is deliberately not efficient. You have ample entropy in your key so there is no need for key stretching.


Are RSA signatures deterministic? If I sign the word HELLO with the mechanism "NONEwithRSA" with the same private key, will I always have the same signature?
A Java example always return different byte array :
PKCS11Provider provider = new PKCS11Provider(this);
List<PKCS11Slot> slots = PKCS11Slot.enumerateSlots(provider);
PKCS11Session session = null;

if (slots.size() > 0) {
    session = PKCS11Session.open(slots.get(0),
    PKCS11Session.OPEN_MODE_READ_ONLY);
}

PKCS11KeyStoreSpi keyStore = new PKCS11KeyStoreSpi(provider, "PKCS11");
keyStore.engineLoad(null, "PIN".toCharArray());
PKCS11PrivateKey privateKey = PKCS11PrivateKey.getPrivateKeys(session).get(0);
Signature signature = Signature.getInstance("NONEwithRSA", provider);
signature.initSign(privateKey);
signature.update("HELLO".getBytes(), 0, "HELLO".getBytes().length);
byte[] realSig = signature.sign();

Some signature algorithms are deterministic (you always get the same signature for the same private key and input), others are not. In the case of RSA, as specified by PKCS#1, the "old-style" (aka "v1.5") signatures are deterministic, while the "new-style" ("PSS") signatures are not (padding includes some random bytes).

In Java, the "NONEwithRSA" mechanism ought to select the old-style signatures, and the input data should be already hashed (a normal signature begins by hashing the input data); in your code, you use unhashed data as input, which is a bad idea for security. The "NONEwithRSA" mechanism was added to support contexts where data is hashed externally, and also SSL/TLS which insists (in its pre-1.2 versions) on using the concatenation of MD5 and SHA-1 as its "hash function". This does not explain why you get different outputs, but you are still doing it wrong.

To investigate further, convert the signature to a BigInteger and apply the public key on it, to see what the padded data looks like:

BigInteger n = ... (the public key modulus)
BigInteger e = ... (the public key exponent)
BigInteger x = new BigInteger(1, realSig);
System.out.printf("%X\n", x.modPow(e, n));

With PKCS#1 v1.5, this should look like:

1FFFFFFFFF....FFFFF0048454C4C4F

(The 48454C4C4F is the encoding of "HELLO" -- because your code puts the raw data here instead of the hash value suitably encoded in an ASN.1 structure which designates the hash function.)

Since you are using a PKCS#11, you will sign data depending on what the underlying device can do. It is possible that your device does not allow such "NONEwithRSA" mechanism, or allows it only if it already looks like a properly encoded hash value. This may be your issue after all. The debug code above should show what happens.

(Also, don't use String.getBytes() without any argument. This converts the input string with the default encoding of the current machine, which depends on how the machine was configured; for some people it will be UTF-8, others will have UTF-16 or latin-1 or something else. It is much better to specify an explicit encoding, as: s.getBytes("UTF-8"))


How is the block size of a block cipher related to how susceptible the block cipher is to a birthday attack? For example what can you say about how susceptible Triple-DES is to a birthday attack due to the fact that it has a block size of 64-bits.

If you encrypt (partially) random values then the likelyhood that you encrypt the same value is larger for block ciphers that operate of fewer bits. If you encrypt the same value with the block cipher (which is a PRP) it will result in the same ciphertext. Identical ciphertext can be used by an attacker to retrieve information about the plaintext, breaking the mode of encryption.

For example, say you'd use a 64 bit block cipher for CTR (counter) mode encryption and you'd use 32 bit for a random nonce and 32 bits for the counter. The counter will simply repeat after $2^{32}$ block encrypts. The random nonce however is succeptible to the birthday problem. This means that you'd have a relatively high chance of a collision (with one of the earlier values) after generating only a few nonces.

As you can see above, the issue with the birthday problem above isn't with the block cipher itself. The problem lies within the mode of operation in which the block cipher is used. It is wrong to say that DES or TDES are succeptible to birthday attacks. 64-bit block ciphers are just not good candidates for modes of operation where the birthday problem may occur, especially if large quantities of data are concerned.


What is the practical use of MDC Suppose that Alice wants to send a message to Bob and wants to make sure that Bob knows he has received the correct message.

She sends the pair $(x,h(x))$ for some hash function (preimage resistant, second preimage resistant and collision resistant). Bob receives a pair $(x',y')$ he calculates $h(x')$ and if he has $y'$, he concludes that the message has not been tampered with.

But the attacker could also change $y'$. So is the hash of $x$ actually sent by another means?

The goal of a MDC is to provide integrity guarantees. That is, given the value $h(x)$, it should be possible to check whether $x$ has been tampered with. The attack scenario you are describing requires authenticity guarantees, i.e., you want to be able to detect whether the tuple is actually from Alice. To achieve this, there are many possible solutions. One simple example would be to require an additional signature from Alice on the tuple (this is for the setting where Bob will need to verify the authenticity and the integrity of the tuple). In case you only require private verification, i.e., Alice stores the data somewhere and when retrieving them again wants to verify authenticity and integrity, you could simply use a message authentication code (MAC).

To your question: in many practical scenarios the hash is delivered by some other means. Yet, in many cases you also have no (cryptographic) authenticity guarantees. Take, for example, the hashes which are provided when you download files. In case you are using plain HTTP you also only can verify whether the downloaded file fits the hash, but you can not verify whether the page you are viewing is actually the page it should be.


McEliece Public Key Encryption The definition of Public Key Encryption(PKE) say that:

  A PKE scheme is a triple of probabilistic polynomial time algorithm (PPT) (Gen,Enc,Dec).

The definition of PPT say:

  In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances.

Let "Find a pair key $(pk,sk)$ (public and private key)" be the problem related with the first algorithm (Gen). In the McEliece scheme, what is a example of error of any instance of the algorithm Gen? Which will be a response "No" and What is a difference between the response "No" and the error response of the algorithm Gen?

A decision problem is to decide if something is true or not (typically phrased in terms of membership of a language). In complexity theory, decision problems are useful for understanding, and most problems can be reduced to a decision problem of some form.

However, in everyday life we are usually not trying to solve decision problems. The algorithms in a public key cryptosystem aren't trying to solve decision problems, so you cannot use the language of decision problems. It just doesn't make sense, as you have discovered.

The notion of polynomial time still makes sense, though.


A problem about Gaussian distribution in paper GPV08 These are contents from the paper Trapdoors for Hard Lattices
and New Cryptographic Constructions(GPV08). I do not know the reason about the last sentence. Why these two distributions D_{\Lambda, s, c}(x) and D_{\Lambda, s, c^{'}}(x) are identical?

The Gaussian function $\rho(x)=\exp(-\pi \| x \|^2)$ satisfies the property that if $x,y$ are orthogonal vectors, then $\rho(x+y)=\rho(x) \cdot \rho(y)$. This follows directly from the definition and the Pythagorean theorem. So, we can cancel out the contribution due to $c-c’$, which is orthogonal to every element in $\Lambda$, from both the numerator and the denominator.


Why is Blum-Goldwasser not IND-CCA-2 secure? Consider the Blum-Goldwasser encryption scheme as described on Wikipedia. I was told that it was not IND-CCA-2 secure.

I heard there was malleabilty, probably it has to do with XOR-ing. But I do not see the point. As stated in the Wikipedia article, in step 2 of the encryption, we choose a random element. So what we xor to the message looks totally different every time. How can we have malleability here?

The randomness is not enough for IND-CCA-2. If we get a message (so $L$ bits of data plus the $y$ to reconstruct the random seed), we can modify it, say flip the first bit, and ask the decryption oracle for a decryption of the modified message (which will have the same $y$!), which we will get. Then the original message can easily be obtained: we get the same key stream for the message (because we have the same $y$ in the modified message), we xor the plain text of the modified message with the modified message and we get the key stream for both the original challenge and (by construction) the modified message. So now we can decrypt the original message too.

Or in a more usual game: we choose a message $p$ to be encrypted and we get back either random or the actual encryption. We do out procedure from above and see if what we got back decrypts to our $p$, and if not, we "expose" the player as having "played" random.

In short, we can ask for a modified message decryption and get useful info. This is not allowed to happen in a IND-CCA-2 secure system.


Key Distribution vs Key Management? What exactly is the difference between "Key Distribution" and "Key Management"?

Key Distribution. Key distribution is, well, the process of distributing (cryptographic) keys to different parties. Usually this involves mechanisms which are considered "out-of-band", i.e. mechanisms that don't use the later communication channel for the transport of keys. Alternatively key distribution can be done by relying the distribution of new keys upon the safe distribution of old keys, that's what a KDC is doing.

Key management. Key management is, well, the process of managing (cryptographic) keys, the usual meaning implies management over the whole lifetime of the key. Key distribution is a part of key management, but it also includes key generation, key escrow (for backup purposes), key deletion, key revokation, key usage and key trust management. If you want to learn more about key management, the Handbook of Applied Cryptography has an entire chapter devoted to it (PDF).


possible MITM attack against servers that used to support weak DH? from reading the TLS 1.1 RFC, it looks like it would be possible to break a previously recorded TLS <1.2, 512-bit DHE ServerKeyExchange and then send it (unmodified, with the original, valid signature) to a client that still accepts TLS <1.2 and 512-bit DHE to impersonate a server that has since been fixed (disabling DHE and/or TLS <1.2 entirely) or "fixed" (using a larger DH group). TLS 1.2 seems like it would be immune to this attack, since its ServerKeyExchange signature includes the ClientRandom value. is there something i'm missing, or would this actually work?

TLSv1.1 doesn't have a different treatment of the key-exchange parameters than TLSv1.2 has. It's just a little less obvious.

Let's dig into TLSv1.1 specification.
On page 44 you'll find that ServerKeyExchange consists of ServerXXXParams params and Signature signed_params. Now on page 44 you'll actually find a definition of Signature. This definition signs sha_hash with or without md5_hash. Now look at the definition of sha_hash and md5_hash. It states that MD5(ClientHello.random + ServerHello.random + ServerParams) is the definition for md5_hash and that SHA(ClientHello.random + ServerHello.random + ServerParams) is the definition of sha_hash.

Now you've found the  random values you're looking for and hence this is the same methodology as in TLSv1.2, but there the signature is directly applied and arbitrary hash-functions can be used.


Nonce encryption with Poly1305-Chacha20 I have seen that a couple of companies (like Google, Apple HomeKit) are adding "ChaCha20-Poly1305" as an encryption option.

Poly1305 requires algorithm to encrypt the nonce. The Poly1305-AES specification uses the AES algorithm to encrypt the nonce, but also says "There is nothing special about AES here. One can replace AES with an arbitrary keyed function from an arbitrary set of nonces to 16-byte strings. This paper focuses on AES for concreteness."

Two questions:

Do all TLS cipher suites using "Chacha20-Poly1305" use Poly1305-AES? RFC7539 references AES as the nonce-encrypting algorithm, but also notes that other algorithms could be used.
Why is Chacha20 not used as the nonce-encrypting algorithm instead (Poly1305-Chacha20)?  Would this cause a security flaw?

Thank you!

Do all TLS cipher suites using "ChaCha20-Poly1305" use Poly1305-AES?

Nope, AES is indeed replaced with ChaCha20 in TLS. The Poly1305 one-time key is generated pseudorandomly using the ChaCha20 block function.  The ChaCha20-Poly1305 TLS cipher suite spec draft uses the AEAD construction from RFC 7539, which defines exactly how this works:

The ChaCha20 and Poly1305 primitives are combined into an AEAD that
takes a 256-bit key and 96-bit nonce as follows:

o  First, a Poly1305 one-time key is generated from the 256-bit key
   and nonce using the procedure described in Section 2.6.

and Section 2.6 describes how the block function is used to generate the key:

o  The 256-bit session integrity key is used as the ChaCha20 key.

o  The block counter is set to zero.

o  The protocol will specify a 96-bit or 64-bit nonce.  This MUST be
   unique per invocation with the same key, so it MUST NOT be
   randomly generated.

Interestingly, the same 256-bit key and 96-bit nonce that are used to generate the one-time Poly1305 key are also used to produce the ChaCha20 keystream during the encryption step. This would be a security problem, except for this little detail:

o  Next, the ChaCha20 encryption function is called to encrypt the
   plaintext, using the same key and nonce, and with the initial
   counter set to 1.

Essentially, the first block (block zero) of ChaCha20 keystream output is used as the Poly1305 one-time key, while the remaining blocks are used in the actual encryption. This is critical: without this separation, an attacker could determine the Poly1305 key.

You might wonder why the Poly1305 paper used AES in the first place. Poly1305 was published in 2005, around the same time Salsa20 (ChaCha20's predecessor) was introduced. I suspect Bernstein chose AES since it was considered the "gold standard" at the time, and Salsa20 had not yet received significant attention from cryptanalysts.


What is the best way to store sensitive information on the client? I am very inexperienced with cryptography and would like some advice on how to store some sensitive information on client machines.

I have some information stored in a central database on my server. A snapshot of this database is distributed along with my application. Every time the application is opened on the client, it checks for any new information on the server and downloads it via a web service. We need the information to be protected at all times, even when stored on the client. The only time it should be decrypted is while it is in memory and being used by the application.

I realize that the nature of our application means that no matter how strong our encryption scheme is, someone could still access our data by examining their machine's memory after the data has been decrypted. However, we have decided that we are OK with that scenario unless there is some magical way of dealing with this problem that I don't know about. We don't need absolute security for this data. We basically just need to raise the difficulty enough to deter most people from tinkering with it.

It seems to me that using a symmetric key is probably the best approach for this scenario. My concern is that if someone figures out the key, we'll have no way of knowing it. Even if we did manage to find out, it would be extremely difficult for us to change it since we would have so many clients using the old key. The natural way of solving this problem is to periodically change the key, but then how do we securely deliver the new key to our existing clients?

It is also worth noting that the user of the application doesn't know about this data and doesn't care about it. We can't ask for a password, require them to have a network connection, or impose any other limitations on them.

Looking forward to your thoughts on this. :)

What you want is basically impossible in this way. The crux of the matter is that if you want your application to access the encrypted data, your application needs to have the key in some shape or form.

Due to the limitations you mentioned, this key needs to be on the client machine, in the application's code or data files.

There are several ways to hide a key in the application's data.  But that is really "security through obscurity", e.g. no security at all. Because it won't protect the key against a persistent attacker who could e.g. single-step through your application's assembly code in a debugger to see how it is accessing the database.

To keep out casual snoopers, you could just compress the database before writing it to disk. To make snooper's lives more difficult, you could chop off the identifying header that most compression programs employ.

BTW, the existence of virtual machines makes snooping on an application easier and harder to detect than ever before. There are some tricks to detect wether your program is running under a debugger, in which case you could abort the program. But if that machine is virtual, the attacker could stop the VM at any time and trawl through that VM's memory at his leisure without your program being any the wiser.

Another thing to keep in mind is authentication. How does the client authenticate to the server when it wants to retrieve a database update? In other words, what is stopping an attacker from impersonating your application and requesting a complete copy of the database?


In simulation proofs of MPC, why could random oracle extract adversary's input? I am learning the simulation-based security proofs in MPC, and have read the great tutorial "How to simulate it" by Prof. Lindell.
Here's my understanding about why we need to "extract adversary's input" in writing simulation proofs against malicious adversaries (please correct if I am wrong): For a malicious adversary, it is not guaranteed to follow the protocol, so "a simulator is able to extract A's input" means "as long as the protocol does not abort, we could be sure that A must be inputting something valid (i.e. following the protocol) ". So the "extracting input" step is crucial for writing proofs against malicious adversary. If we can extract A's input, everything left are just the same as the semihonest proofs.
The example of changing semihonest OT into malicious OT with ZKP meets my above understandings, because ZKP could prove the prover's correct behaviors, and could extract the prover's input. However, when reading other proofs, I found it hard to understand why could random oracles extract inputs as well.
E.g. Proof of Theorem 1 in [1] says "SIMs builds two tables T1 = (x, φ) and T2 = ((h, t), ψ) to answer the hash queries to H1 and H2 respectively". How could SIMs know the inputs to H1 and H2? If SIMs could do that, does it mean we can extract inputs simply by asking the parties to hash their inputs, and any semihonest-secure protocols become malicious-secure ones by simply introducing an extra hash-input step (which is obviously not true) ?
I know there must be some basic mistakes in my understandings, and would be very grateful if someone could point it out. Thanks.
[1] Jarecki S, Liu X. Fast secure computation of set intersection.

This is exactly what makes the random oracle model an idealized model. If $H$ is a hash function in the standard model, an adversary can run $H$ "in its head", and this will be inscrutable to a simulator. But in the random oracle model, the only way to evaluate the hash function $H$ is through a well-defined oracle interface. The simulator gets to play the role of this interface! -- just like it is allowed to play the role of the honest parties.

If SIMs could do that, does it mean we can extract inputs simply by asking the parties to hash their inputs, and any semihonest-secure protocols become malicious-secure ones by simply introducing an extra hash-input step (which is obviously not true) ?

If the protocol instructs parties to hash some information, and that adversary does it, then, yes, the  simulator (in the random oracle model) will be able to observe that call to the hash.
But an adversary can just not call the hash function at all (and just send junk messages in the protocol), or hash the "wrong" value instead, or hash a billion "decoy" values.
The simulator will need to do something sensible in all of these cases!
In your hypothetical example, the protocol would need to contain some method for the other participants to "check" that the hash was called.
I'm not sure what this would look like in your scenario.
But it would have to give the simulator some advantage: after seeing how the adversary acted in the rest of the protocol, along with seeing the list of all random-oracle queries made by the adversary, hopefully the simulator can deduce which query was the "real" one.
I think you will find that the examples in "How to Simulate It" will have this property.
You can't just ask an adversary to query $H$ on their private input, but then do nothing with the result.
They have to interact with $H$ in a way that gives the simulator an advantage, when the simulator is allowed to observe all queries to $H$ and also observe the rest of the protocol messages too.
I'm sure you will see that in "How to Simulate It", the simulator will "cross-reference" these tables $T_1$ and $T_2$ with protocol messages sent by the adversary, in order to extract.


Which categories of cipher are semantically secure under a chosen-plaintext attack? I am trying to get my head around the circumstances under which a cipher is (or is not) semantically secure under a chosen-plaintext attack.

I can't seem to find a good reference explaining this.

I think I am missing a fundamental concept, so If I explain it as I see it perhaps someone can correct me.

Semantic security means that the adversary cannot learn anything about the plaintext from the ciphertext (except for the length of the message which is known beforehand).

I.e. the message is entirely indistinguishable from random bits.

So it seems to me that if a stream cipher is using a true PRG, it's output will always be indistinguishable from random, a chosen plaintext attack will not assist the adversary.

However if the encryption is deterministic then a chosen plaintext attack will reveal "information" about messages, as the ciphertexts can be compared to one another.

Am I missing something?

Encryption using a block cypher such as AES by passing plaintext blocks directly to the encryption function is known as Electronic Code Book mode (ECB) and is not CPA secure as (as you say in your question) it is entirely deterministic and two identical plaintext blocks will result in two identical ciphertext blocks.

To prevent this an initialisation vector or nonce can be used in  combination with a cryptographic mode such as cipher block chaining or randomised counter mode which will prevent the encryption from being deterministic and allowing the comparison of ciphertexts.


Is function Deterministic or Probabilistic in the malicious security definition? As you see, according to the attached definitions from "Efficient Secure Two-Party Protocols", the definition of the security in the semi-honest world has two cases for $f=(f_1,f_2)$.(deterministic and probabilistic)

Now, my question is, why the authors have not said anything about the type of the $f$ in the malicious world? I mean, whether $f$ has two types like in the semi-honest model or not?

No, the semi-honest definition does not have two cases; the correct definition is Definition 2.2.1, which applies to all functionalities. But if the functionality is deterministic, then the simpler definition given later in the book (yes, it is given later in the book; I am not sure why you decided to put it above it in your question) is equivalent, and might therefore be preferred when trying to prove the security of a protocol.

No similar "simplified" definition exists in the malicious model, because even if the functionality is deterministic and the protocol correctly computes it, a malicious adversary can deviate from the protocol and output something completely different from what the protocol says it should.


Is there an effective way for public key generation in homomorphic encryption schemes? Is there any way to effectively generate valid distributed public key in schemes like ElGamal or Benaloh for a number of participants? There's no need in private keys since there's no intent to decrypt messages at all, only to encrypt them securely.

As far as I know, there's no effective way to generate distributed key pair in Benaloh.

I must confess to not fully understanding your question but hopefully this will assist.

To generate a public key in Elgamal, you need a group (e.g., subgroup $\mathbb{G}_q$ of $\mathbb{Z}_p$ for large primes $p,q$) and a generator ($g$ where $\mathrm{order}(g)=q$).

A secret key is chosen from $x \in_r \mathbb{Z}_q$ and the public key is computed as $y=g^x$.

If you want to generate a public key $y$ without caring about $x$, you can use any element of $\mathbb{G}_q$.
If you want to ensure that no one knows $x$ for a given $y$, you could compute $y_i=\mathcal{H}(g)+i$ for $i=\{0,1,2,\ldots\}$ until you find a $y_i \in \mathbb{G}_q$.

For Benaloh (or Paillier), the first point is the same, the second is more complicated if you want to additionally ensure that no one knows the factorization of $n=pq$ (however there are techniques to do this).

Finally, I do not see any applications of encrypting without requiring decryption. If you simply want to obfuscate a value, there are more efficient primitives you can use. If you don't need decryption (per se) but do want to do things like plaintext equality tests, these require a decryption key!


Is precomputing AES-CTR key stream secure? Q0 : Is the precomputed key stream vulnerable to side-channel attacks like a lookup table for exemple ?
I don't think it is because a lookup table is accesed very often, that's what makes it non constant time.
Q1 : If the precomputed key stream is very large like a few MB, it may be paged out to the disk, can another program access the key stream while it is in the disk like a file ( which will allow it to decrypt the corresponding plaintext easily ) ?
Or are these pages protected by the OS ?
Is there any other security issue with precomputing key streams ( real issues or wrong hypothesisies ) ?

Q0 : Is the precomputed key stream vulnerable to side-channel attacks like a lookup table for exemple ?

Of course not; once it is precomputed it sits in memory. Even if it is accessed, no actions are performed that depend on the randomized stream - other than the XOR with the plaintext of course. In principle that could be vulnerable, but since nothing is really location dependent, I guess that the risk is relatively low.
If the energy usage of the inputs of the XOR can be monitored then you can still leak information about the bits. E.g. if a large all zero plaintext is usually expected then you might be able to see an all one plaintext. Similarly on some systems even copying data can be dangerous, independent on the contents. So yeah, it depends on the system if side channels exist and if they are applicable at all.
And of course, if you store the key stream then anything accessing it breaks the scheme. The longer you store it, the higher the risk (e.g. against direct attacks against the RAM (Row hammer) or CPU (Spectre / Meltdown). You could of course argue that you're screwed even without a key stream if those apply...

If the precomputed key stream is very large like a few MB, it may be paged out to the disk, can another program access the key stream while it is in the disk like a file ( which will allow it to decrypt the corresponding plaintext easily

Generally not, as the OS will not allow a process to access another process memory. Of course, if you e.g. have an application server or virtualized system then other protections need to be in place. Beware that this doesn't say anything about the security of the page file if another system can be loaded. For that the page file should be encrypted and many operating systems at least contain that kind of functionality (if it is enabled by default is another matter).

Is there any other security issue with precomputing key streams ( real issues or wrong hypothesisies ) ?

Loosing sync would be one of my main issues. Also, a key stream directly used for CTR mode may indicate that the implementation is not authenticated.
Finally, AES is pretty fast on most processors. I would worry if the implementer would know what they were doing. It is likely that they e.g. use a managed implementation rather than a native / CPU supplied one. I would mainly use key streams to avoid latency issues rather than throughput issues.


How to attack a "many-time pad" based on what happens when an ASCII space is XORed with a letter? I've already sent my correct solution to a homework exercise from Dan Boneh's Introduction to Cryptography class on Coursera:

"Let us see what goes wrong when a stream cipher key is used more than once. Below are eleven hex-encoded ciphertexts that are the result of encrypting eleven plaintexts with a stream cipher, all with the same stream cipher key. Your goal is to decrypt the last ciphertext, and submit the secret message within it as solution.
Hint: XOR the ciphertexts together, and consider what happens when a space is XORed with a character in [a-zA-Z]."

I managed to get the key by XORing ciphertexts #1 and #2, then XORing the result with the string " the " at each possible position.  Combined with a lot of guesswork, this gave me the first plaintext.
My question is: What would I have to do if I want to follow the hint? I know that if I XOR a space with a letter, I change the case of the letter, but then what?
I don't understand how I can recognize spaces!  Suppose I see a letter in $c_1 \oplus c_2$; how can I tell if there was a space in one of the plaintexts?

"Hint: XOR the ciphertexts together, and consider what happens when a space is XORed with a character in [a-zA-Z]."

Let's assume that the plaintexts consist only of spaces and ASCII letters.  Given the hint, that seems like a reasonable assumption to start with, even if it might turn out to be only mostly correct.

Now, take one of the ciphertexts and XOR it with each of the others.  Of course, the XOR operation cancels out the keystream, so you end up with the plaintext corresponding to the chosen ciphertext XORed with each of the other plaintexts.

Now look at each character position in turn.  By assumption, the character at that position in the chosen plaintext might be either a letter or a space.

If it's a space, then the characters at that position in the pairwise XORed plaintexts will be either letters (if the character at that position in the other plaintext is a letter) or nulls (if both of the characters are spaces).
If it's a letter, then the characters at that position in the pairwise XORed plaintexts will be random control characters (if the character at that position in the other plaintext is a letter with the same case), numbers or punctuation (if the other character is a letter with different case) or that particular letter with the case flipped (if the other character is a space).

Those two cases should be pretty easy to tell apart.  Furthermore, in the first case, you can easily get the actual characters at that position in all the plaintexts just by flipping the case of all the letters you obtained by XORing the ciphertexts together.

In this manner, you can decode all the characters at the positions where the plaintext corresponding to the chosen ciphertext has spaces.  Once you've done that, choose another ciphertext and repeat the process.  Hopefully, by the time you've done this with all the ciphertexts in turn, you will have solved most of the character positions and can easily fill in the rest.

Ps. To see why this works, it helps to know that the 7-bit ASCII character set can be divided into four 32-character blocks, like this:

Bit 4:     0000000000000000 1111111111111111 |
Bits 0-3:  0123456789ABCDEF 0123456789ABCDEF | Block:
---------+-----------------------------------+---------------------------
Bits  00 | ................ ................ | Control characters
5-6:  01 |  !"#$%&'()*+,-./ 0123456789:;<=>? | Numbers and punctuation
      10 | @ABCDEFGHIJKLMNO PQRSTUVWXYZ[\]^_ | Uppercase letters (mostly)
      11 | `abcdefghijklmno pqrstuvwxyz{|}~. | Lowercase letters (mostly)

In particular, a consequence of this structure is that, if you XOR two ASCII characters in the same row (e.g. two uppercase letters or two lowercase letters), the result will be a control character.  Similarly, XORing an uppercase and a lowercase letter will produce a character in the second row, i.e. a number or a punctuation character.  Also, as pointed out in the hint, the position of the space character at the beginning of the second row means that XORing it with any other character just flips bit the fifth bit of the character code, moving the character one row up or down.


Is AES-XTS considered safe to encrypt multiple files with the same keys? I was wondering if changing the cipher mode to AES-XTS in EncFS would be a sound idea. EncFS uses AES in CBC mode until the last 1KB block, and CFB mode for the last block if len(block) < 1KB. This ensures that len(plaintext) == len(ciphertext).

The design seems somewhat convoluted, but understandable considering those decisions were (probably?) made before any relevant standard was published.

My main concern is that AES-XTS seems to have been designed for data stored in block devices and not for a "user-space encrypting filesystem". In an encrypted user-space filesystem, each file would be a "block device" and each "block device" would use the same keys.

Apart from the obvious issue that encrypting the same file twice would result in identical ciphertexts (if not using per-file keys), how could we attack this design? :)

Thank you.

Additional clarifications/motivation

EncFS' default options

EncFS has several options when creating a volume. By default, files are encrypted using unique, unpredictable ivs; blocks are not authenticated (a per-block MAC option exists, but is disabled due to efficiency considerations); a "block" in EncFS defaults to 1024 bytes.

Why would anyone want to disable per-file ivs?

Disabling per-file ivs in EncFS raises several potential issues:

Watermarking attacks
Copy-paste attacks using blocks from different files
Since the last block may be encrypted with a stream cipher, the keystream may be reused. Or not, since some magic shuffle operations are used.
Additional information leaks

However, many people use EncFS with cloud-based storage solutions, such as Dropbox and Google Drive. Some commercial services exist there are/were based on EncFS, even disabling per-file IVs. I am not affiliated in any way with such companies.

When per-file ivs are disabled, data deduplication inside a specific volume will work very well. Identical plaintext on the same block offset will have identical ciphertext. From a bandwidth/space efficiency standpoint, this is a very desirable property. From a security standpoint, it is not.

So the question could be rephrased as: is using AES-XTS (which is less malleable than AES-CBC and more easily parallelizable, but it can leak more info since it does not chain) without per-file keys an acceptable security tradeoff, if trying to optimize a volume for a cloud storage service? Would enabling such a design be acceptable?

From a draft of the IEEE spec,

  "An XTS-AES key shall not be associated with more than one key scope.
  The reason is that encrypting more than one block with the same key
  and the same index introduces security vulnerabilities that might
  potentially be used in an attack on the system. In particular, key
  reuse enables trivial cut-and-paste attacks."

You are seriously breaking the warranty here. I take it you know this...

  "The proof from Rogaway yields strong security guarantee as long as
  the same key is not used to encrypt much more than a terabyte of data
  (which gives q=236 blocks). For this case, no attack can succeed with
  probability better than 2^53 (i.e., approximately one in eight
  quadrillion).  This security guarantee deteriorates as more data is
  encrypted under the same key. For example, when using the same key for
  a petabyte of data, attacks such as in D.4.2 have success probability
  of at most approximately 2^37 (i.e., approximately eight in a
  trillion), and with exabyte, of data the success probability is at
  most approximately 2^17 (i.e., approximately eight in a million). The
  decision on the maximum amount of data to be encrypted with a single
  key should take into account the above calculations together with the
  practical implication of the described attack, (e.g. ability of the
  attacker to modify plaintext of a specific block, where the position
  of this block may not be under attacker’s control)."

So you may have some space before the tradeoff becomes completely broken I guess.

Also, if the cloud storage system can prevent anything from being written to the user's space without first encrypting it, (or prevent anything from being decrypted that it didn't itself encrypt), then it might be able to prevent some copy/paste attacks (from users). Since all encryption/decryption/writes are done remotely from the attacking user, it eliminates some of the IEEE worries about some types of passive attacks and random data attacks.

Ok, that's my most generous answer. You're asking a question of the form, "There's this security standard. Can I throw out a major piece of it and make it useful for something else?"

And while it's super tempting to launch into comparative cryptanalysis of AES-CBC and AES-XTS with your modifications, the only responsible answer to all such questions has to be, "No, that will give you something that's broken and unverified, equivalent to just making something up from scratch. You shouldn't want that. The first rule of crypto is don't build your own crypto."

I highly recommended approaching this from scratch as, "I want a mode or protocol that accomplishes X, Y, and Z, but I don't care about attacks A, B, or C. Is there any such mode? If not, what gets closest?" Maybe there isn't, and you have to face the hard choice of deduplication or security. But hey, who knows, you might find that there's something you hadn't even considered that meets your design objectives.

Best of luck!


Are there public $p$ and $q$ numbers for use in DSA? There are many RFC documents giving large primes to use in Diffie-Hellman. However, I couldn't find standards on the $p$ and $q$ large primes used in the DSA signature scheme. This is proving to be a major obstacle in my own toy implementation of DSA, as generating these primes uses much messier math and code than the rest of the algorithm, and more places where I could make stupid mistakes that trash the security of the whole scheme.

Where can I find suitbale $p$ and $q$? They don't seem to need to be private, and frankly I'm kind of shocked that there aren't standard numbers for them to save people from needing to do the expensive calculations themselves.


Affine Cipher Cryptanalysis I am trying to perform Cryptanalysis on Affine cipher . Given Plain Text "GO" and cipher text "TH"

We know , $G =6 , O=14 , T=19 , H= 7$

By brute force method

I'm getting key $(a,b)$ as $(5,15 )$

But by known plain text attack method

$6a + b = 19 \\
14a +b = 7$

on solving the equations . im getting

$-8 a + 0  =  12  $

taking addictive inverse of $-8 = 18$

We get , $18a +0 =12$ , Now

$a= 12*$ multiplicative inverse of $(18)$

Multiplicative inverse of 18 doesnt exist then how to proceed ? Is my approach correct ?

When working with modulo arithmetic, in case of trouble, get back at what the notation used truly leans. When the question correctly derives $18\,a+0=12$, that really is a shorthand for $18\,a+0\equiv12\pmod{26}$. By definition of the equivalence..modulo notation, that is meaning $(18\,a+0)-12$ is divisible by $26$ when computing in (signed) integers $\mathbb Z$. An integer is divisible by $26$ if and only if it is divisible by $2$ and $13$. The rest will follow.

More generally, when an equation holds modulo a squarefree integer, that equation is equivalent to the combination of equations obtained by replacing the modulo by each of its prime factors. So here we get
$$18\,a\equiv12\pmod2\;\;\;\text{ and }\;\;\;\;18\,a\equiv12\pmod{13}$$
or, reducing,
$$0\,a\equiv0\pmod2\;\;\;\text{ and }\;\;\;\;5\,a\equiv12\pmod{13}$$
The first is a tautology, and the second can be solved by multiplying by the inverse of $5$ modulo $13$, that is $8$, giving $a\equiv5\pmod{13}$.

That gives two possible $a$ modulo $26$: $a$ can be $5$ or $18$. The second is obtained by adding the modulus $13$ to $5$. More generally, given $a$ modulo $u$ with $0\le a<u$, there are $v$ values for $a$ modulo the product $u\;v$ with $0\le a<u\;v$ , and these are $a+k\;v$ with $0\le k<v$.

The value of $b$ corresponding to a given $a$ is obtained by moving that value of $a$ in either of the two equations $6\,a+b\equiv19\pmod{26}$ or $14\,a+b\equiv7\pmod{26}$, and pulling $b$. Both values of $a$ yield that $b$ is $15$ (modulo $26$). That's no coincidence.

Therefore, beyond $(a,b)=(5,15)$, there is an alternate solution $(a,b)=(18,15)$. More plaintext is required to recover the full key.


Number of active s boxes How can I calculate the minimum number of active s_boxes for block cipher algorithms such as present algorithm?
I have read in that, but I couldn't understand the meaning of branch number.

Present cipher is bit based permutation cipher. The branch number is calculated based on the minimum number of hamming weight sum of input and output  in the difference distribution table(DDT) or linearity approximation table (LAT) of the sbox. in case of present cipher the 4-bit sbox , the differential branch number (BR) is 3.

to apply the differential BR on the whole present cipher , I advice you to apply mixed integer linear programming. this link contains the MILP model of different ciphers including present in sage, you can start from here.


How can I use eulers totient and the chinese remainder theorem for modular exponentiation? I'm trying to implement modular exponentiation in Java using Lagrange and the Chinese remainder theorem.

The example we've been given is:

  Let $N = 55 = 5 · 11$ and suppose we want to compute $27^{37} \pmod N$.

He doesn't give us the answer, but says:

  The most efficient way to do it is is using Lagrange's theorem, a few multiplications modulo 5 and 11 and CRT to combine both results.

Using Lagrange / Euler totient I get $\varphi(N) = 40$, which it seems I'm supposed to use calculate the congruences needed for putting into the Chinese remainder theorem.

I know I can calculate the congruences using the Extended Euclidean algorithm, but the answers need to be reduced or the run time will still be unfeasible (maybe not in this case, but for the 1024 bit numbers I'm working with, this is a huge problem).

I know they can be reduced, from a document I found while researching this,  which states:

  $$a^k \equiv a ^ { k \pmod{\varphi(n)}} \pmod n.$$

I've tried and tried and tried to follow how he does the reduction but I just don't get it. He also doesn't mention what $m$ is when he says $k = m · \varphi(n) + k'$.

As you can probably gather, my math is not so hot, so if possible maybe give a "for dummies" answer.

The example given – Let $N = 55 = 5 · 11$ and suppose we want to compute $27^{37} \pmod N$ – is not homework, so if anyone could step me through it, in particular the reductions to get to the simplified Chinese remainder theorem congruences, I would be VERY grateful.

I originally placed this question on Stack Overflow.

To step through it simply:

Step 1: we first compute compute $M^e \bmod p$ (where $p$ is one of the factors of the modulus.  By Fermat's Little Theorem, this is the same as $M^{e \mod p-1} \bmod p$ (and that's where the real savings are), and so in your example ($p=5$), we get:

$M^e \bmod p = 27^{37 \bmod 4} \bmod 5 = 2^1 \bmod 5 = 2$

Step 2: we do the same for the other prime $q$:

$M^e \bmod q = 27^{37 \bmod 10} \bmod 11 = 5^7 \bmod 11 = 3$

Step 3: using the Chinese Remainder theorem, we reconstruct $M^e \bmod pq$ from $M^e \bmod p$ and $M^e \bmod q$:

$C_p = M^e \bmod p = 2$
$C_q = M^e \bmod q = 3$
$M^e \bmod pq = C_q + q \cdot (q^{-1} (C_p - C_q) \bmod p) = 3 + 11 \cdot (1 \cdot (2-3) \bmod 5) = 3 + 11 \cdot 4 = 47$


Why RSA-sig authentication VPN need its own private key? In my understanding, RSA-sig authentication only requires its own Public Key so that the peer authenticates it using Root CA's public key. But, strongSwan VPN configuration requires its own private key. I can't understand it. Am I wrong about RSA-Sig authentication or is strongSwan using RSA encryption?

In my understanding, RSA-sig authentication only requires its own Public Key so that the peer authenticates it using Root CA's public key.

No, that is not how PKI (Public Key Infrastructure) works.  Yes, the CA does issue a certificate (authenticated by the root CA's public key), however the certificate just says "this specific public key corresponds to a private key owned by themasterplan".
That is, a certificate is a way to bind a public key (which is a series of random-looking bits) to an identity (a label that is meaningful to the reader of the certificate); it is one way to solve the question "how do we know that this particular public key is from who we want to talk to".
So, to meaningfully authenticate yourself with a certificate, you need your own private key (so that the certificate can refer to your public key); that is the public/private key that StrongSwan requires.
And, a StrongSwan service authenticates itself by sending its certificate (so that the peer knows and can verify the public key), as well as a signature (to prove that the StrongSwan implementation has the private key that the certificate refers to).


What do associated data and message numbers mean? I'm reading an article about authenticated encryption and don't understand some inputs to an encryption function. They are associated data, public and secret message numbers. Can you explain me their meanings?

As documented in the call for submissions of the CAESAR competition, an authenticated encryption scheme may have up to five inputs.

The key. This one is obvious. The key needs to stay confidential and once the key is leaked all authentication and confidentiality guarantees are lost.
The plaintext. This is also obvious. This is the message to be encrypted. It is guaranteed, that an (polynomialy bounded) attacker can't alter nor extract any information about the plaintext from the ciphertext.
The associated data. This is mainly meta data. It is guaranteed that an attacker can't alter the associated data, but may read it in clear text. Associated data is commonly used to transport IVs, headers or routing information.
The public message number. This is can be just a part of the associated data, but it also can be an additional fixed-length input. The public message number is guarenteed not to be altered, but may be read in clear text. A reuse of a (public message number , secret message number) pair may result in a complete loss of security guarantees for a given scheme. The use of this number may be to prevent replay attacks and to serve as a nonce for the underlying schemes.
The secret message number. This is a relatively new input. It is the plaintext equivalent to the public message number. Thus, the confidentiality of this number is also guaranteed. The use of this number may be to hide parts of the nonce for the underlying system from attackers or to allow (some sort of) hybrid encryption.


Learning about Feistel Cipher I'm learning about Feistel Ciphers at the moment, but having issues with the formulae, so I can't move on from it.

Encryption:

$_{+1} = _$
$_{+1} = _ \oplus ( _ , _)$

For the round function $( _ , _)$, could someone advise on what exactly I need to do? Let's say my key is $1197$, what needs to happen in between the brackets, $(_ , _)$ , full diagram screenshot attached, thanks.

I guess it makes more sense if you write the two equations like this (referring to the nice diagram in Wikipedia):
$$L_{i+1}=R_i,\; R_{i+1}=L_i\oplus F_{K_i}(R_i).$$
In each round, the round function $F$ takes as input the corresponding round key $K_i$ and the previous round's right output, then computes the output value, which is then XORed with the previous round's left output.
$F$ is usually modeled as a pseudorandom function and has many instantiations (see here for a list of Feistel ciphers, of which each specifies its own $F$ instantiation and key schedule).
This post discusses the requirements/goals for good $F$ instantiations.