Why is this cryptosystem insecure? Can someone help me see the flaw in this cryptosystem?

Note: This is homework and it is due today at 1:30pm. An answer before that is not expected; I'd just like to understand what the flaw is.

From An Introduction to Mathematical Cryptography By Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman (Springer, 2008); problem 3.10, found one click away from here:

  Alice chooses two large primes $p$ and $q$ and she publishes $N = pq$. It is assumed
  that $N$ is hard to factor. Alice also chooses three random numbers $g$, $r_1$, and $r_2$ modulo $N$ and computes
  $$g_1\equiv g^{r_1\cdot(p−1)}\pmod N\text{ }\text{ and }\text{ }g_2\equiv g^{r_2\cdot(q−1)}\pmod N.$$

  Her public key is the triple $(N,g_1,g_2)$ and her private key is the pair of primes $(p,q)$.

  Now Bob wants to send the message $m$ to Alice, where $m$ is a number modulo $N$. He chooses two random integers $s_1$ and $s_2$ modulo $N$ and computes
  $$c_1\equiv m\cdot{g_1}^{s_1}\pmod N\text{ }\text{ and }\text{ }c_2\equiv m\cdot{g_2}^{s_2}\pmod N.$$
  Bob sends the ciphertext $(c_1,c_2)$ to Alice.

  Decryption is extremely fast and easy. Alice use the Chinese remainder theorem
  to solve the pair of congruences
  $$x\equiv c_1\pmod p\text{ }\text{ and }\text{ }x\equiv c_2\pmod q.$$

  (a) Prove that Alice’s solution $x$ is equal to Bob’s plaintext $m$.
  (b) Explain why this cryptosystem is not secure.

I can verify A but am having trouble seeing where the cryptosystem is weak.
Avenues I've explored:

The modulus is factorable
The encrypted text is easily decryptable

But I'm just not seeing the answer. Can I have some help?

From the key creators point of view, notice that:$g_1\bmod p=1$ and $g_2\bmod q=1$.

Which means that $(g_1-1)\cdot(g_2-1)\bmod N=0$.

Which implies that $g_1-1$ and $g_2-1$ share a common divisor with $p$ and $q$.

To obtain $p$ we simply take $\gcd(g_1-1,N)$.

To obtain $q$ we simply take $\gcd(g_2-1,N)$, or $N/p$.

Because we have been able to factor the modulus using only the public keys and with no protocol error on the part of the implementer, this cryptosystem is insecure.


Secure and deterministic MACs which are not strongly secure? One of the practice problems I was given for an exam that I'm preparing for is as follows:

  Let $\Pi$ be a secure, deterministic MAC that uses canonical
  verification. Show how to construct a MAC $\Pi'$ that is secure and
  deterministic but is not strongly secure.

In my book, it says that if a MAC uses canonical verification, then it is a strong MAC. This seems to suggest that $\Pi'$ should not use canonical verification.

By the definition of a strongly secure MAC, for our construction, an adversary should be able to generate a new valid tag on an existing message-tag-pair that it has seen before. However, if the MAC is deterministic, doesn't that mean that each unique message only has one valid tag?

How do I approach such a construction? If all deterministic secure MACs can use canonical verification, and all secure MACs that use canonical verification are strongly secure, then doesn't that mean that all deterministic MACs are strongly secure?

A deterministic MAC can use canonical verification, but it doesn't have to.
Thus, the question allows you to create deterministic MAC without canonical verification. How can you use this to your advantage?

Hint 1:

   What if you add some auxiliary (constant) bit to the output of the  tagging algorithm of $\Pi$. How can you define the verification algorithm of $\Pi'$ to still be UF-CMA secure but not SUF-CMA secure?

Hint 2:

   This question is very similar to another question given here: Difference between INT-CTXT and INT-PTXT


Does complicating a flawed algorithm make it secure? It's a basic question I guess, but I don't know the answer and I don't think that anyone asked it.

Suppose I built a system, it relies on MD5 for security, suddenly I read am article on how easy are MD5 to crack nowadays.

Not being able to implement other algorithms, I multiply the MD5 hash by Pi, and some Fibonacci sequence then divide it by 0.5 and multiplied it by a random string that I generated using a secure generator. I obtain a totally different string

Then I use a function from my program to reverse all that I have done and then pass the original MD5 Hash to be decrypted.

The example I gave is simple, you can over complicate it as much as you like. Suppose you're a hacker, not knowing what I did to the MD5 hash, would you be able to crack it?

There's a problem with boundaries here; how much "complication" is allowed? I could argue that SHA-2 is a complication of SHA-1 because they both use a Merkle-Damgård construction and have other similar elements. Then again, they are significantly different internally.

On the other hand the addition of a single bitwise rotation did make SHA-1 significantly more secure. Of course it has now proven to be not secure enough but that was after decades of good service.

  SHA-1 differs from SHA-0 only by a single bitwise rotation in the message schedule of its compression function; this was done, according to the NSA, to correct a flaw in the original algorithm which reduced its cryptographic security.

This also shows another problem with the question: what is secure enough? Obviously SHA-1 is not secure enough, but it is at least protected against some attacks on SHA-0. SHA-2 is much more secure than SHA-1, but it is still vulnerable against length extension attacks which SHA-3 is not.

In general you cannot just apply some random function to the inner workings or output of an insecure function. Cryptographic functions need proof (or at least a well reasoned strong indication if a prove cannot be constructed) to be secure. For instance, if the bitwise rotation was only performed on the output of SHA-0 then the result would not have been secure.

So unfortunately the answer is: it depends on the change being made and - in a practical sense -  the reasoning behind it.

With regard to your scheme: it only changes the end result of the hash, using operations that - according to your own text - should be reversible. Furthermore, you require the algorithm itself to be secure.

There are two major problems with this:

you lack a clear indication why this would make the MD5 hash more secure, trying a lot of mathematical constants and operators would likely break the scheme;
keeping the algorithm itself safe breaks the Kerckhoffs principle, you should not rely on keeping the algorithm safe.

Kerckhoffs principle and the reasons for making an algorithm public is clearly explained in this answer on Crypto.


What is the purpose of key strengthening? I recently came across this term and after some research found this article which states the following:

  An alternative approach, called key strengthening, extends the key with a random salt, but then (unlike in key stretching) securely deletes the salt. This forces both the attacker and legitimate users to perform a brute-force search for the salt value

That made me wonder, what's the point of using such an approach rather than the traditional key stretching?
Are there any real applications employing this method?

The sources of that Wikipedia article show that the article describing key strengthening by Manber (adding a subsequently deleted salt) is from 1996, two years before the 1998 article that is given as the origin for key stretching describes (adding more iterations).

The idea there seems to have been to use the existing crypt() password hash exactly as-is, and make any modifications outside of it. From the Manber paper, p.5:

  The implementation of this scheme is very easy. In particular, all
  changes are made as an extra filter to the login procedure, without having to modify the encryption
  mechanism at all.

Remember that the original crypt() didn't have any means for setting the number of rounds, but was completely fixed. (It also didn't support password longer than 8 characters, so they couldn't just append the salt, but had to apply it by "scrambling" the password with the secret salt.)


Are all self-synchronizing cryptosystems necessarily self-synchronizing stream ciphers? I have a noisy communications link between two points that occasionally deletes a byte.

By "self-synchronizing cryptosystem", I mean that the receiver attempting to recover the original plaintext will be mostly successful, with at most a dozen or so corrupted letters of plaintext corresponding to each missing ciphertext byte.

Are all such cryptosystems necessarily self-synchronizing stream ciphers?

In other words:

Cryptosystems that are some block cipher mode of operation:

A few block cipher mode of operation are self-synchronizing, such as the SCFB mode and OCFB mode described by Fang Yang and Howard M. Heys; "Comparison of Two Self-Synchronizing Cipher Modes". Do all such block cipher modes end up producing a stream cipher, i.e., producing a pseudo-random bitstream and then combining that bitstream with the plaintext using XOR (or another stream-cipher operator)?

Cryptosystems that are not some block cipher mode of operation

Do all such cryptosystems end up either being effectively a stream cipher, or are non-self-synchronizing, or both?

I realize this isn't a practical question --
in practice, we MAC the message as a whole, and if anything was changed, added, or deleted, we reject the entire message.
(In practice, non-crypto networking techniques handle bit-alignment, byte-alignment, packet-alignment, etc. and then re-send or otherwise correct occasional missing bytes and assemble the complete message long before any crypto algorithms at the receiver ever see that message).

Your best bet is to use an error-correcting code to correct the errors on the ciphertext.

In general, accepting corrupted ciphertexts is a bad idea, because it can allow devastating chosen-ciphertext attacks and because unauthenticated encryption has caused major security holes in practice.

When proper authentication is in use (which should be always), any error will result in the entire message being rejected.  There are   two solutions:

Break the message into chunks, such that bad chunks can be detected and retransmitted.
Use error-correcting codes.  These allow for errors to be corrected by introducing redundancy.

These can be combined.


Is it possible to 'fake' time for TOTP? (Time-based One-time Password) TOTP (Time-based One-Time Password) Algorithm is used in Two factor authentication. I understand the algorithm and that current time is used as a variable to generate a token. Wiki page for reference: http://en.wikipedia.org/wiki/Time-based_One-time_Password_Algorithm

My question is, can current time be faked?

Suppose you have tokens T(0),...,T(n) where T(0) was generated at time = 0 and T(n) was generated at time = n.

Suppose I have the initial seed value for the algorithm, and I know current time is k, is it possible to generate T(k) without having generated T(0),...,T(k-1)?

In other words, can time elapsed be 'faked'? Or is T(k) based on every token in the set of tokens, T(0),...,T(k-1). If it is based on every previous token, does generating T(k) require at least (block of time) * (k-1) time to generate or can the process of elapsed time be fed to the algorithm to generate T(k) in less time?

Thanks.

The algorithm produces a password based on the value of the time that is input as an argument.  That value does not have to be the current time.  For the purposes for which TOTPs are generally used, there is no value in producing the password for a time other than the current time step - it won't be recognized by the validator.


Security Strength of Double Substitution Ciphers I am wondering why people are using RSA keys when some types of double substitution ciphers seem to be just as secure if not better off.

By some types of double substitution ciphers I mean one Which expands the plaintext message like so:

A: aaa
B: aab
C: aac
D: aba
E: abb
F: abc
G: aca
H: acb
ect.

(And if there is an odd length the add a d to the ciphertext.)

Then collapses the newly made ciphertext into a new ciphertext like so:

aa: A
ab: B
ac: C
ad: D
ba: E
bb: F
bc: G
bd: H
ca: I
cb: J
cc: K
cd: L

This method would render any method I know for deciphering codes useless, and I was wondering if there is a method I am missing or if this is actually a very strong method of encryption.

I am wondering why people are using RSA keys when some types of double substitution ciphers seem to be just as secure if not better off.

First of all, RSA is an asymmetric cipher while a substitution cipher is a symmetric cipher. Asymmetric ciphers are used to achieve different security needs, e.g. TLS authentication or non-repudiation of documents. Or, more closely related, the encryption for one specific person without that person having to hand you their private key.

So no matter how secure your cipher would be, it would still be a symmetric cipher and could therefore not replace RSA.

  This method would render any method I know for deciphering codes useless, and I was wondering if there is a method I am missing or if this is actually a very strong method of encryption.

Bruce Schneiers law: "Anyone can invent a security system that he himself cannot break"

As already indicated, a cipher requires a key because of Kerckhoffs principle. An algorithm that doesn't require a key will be broken as somebody will likely leak the algorithm itself in time.

Even if there was a key, I don't think your scheme would even survive the most basic of attacks such as frequency analysis. More advanced algorithms would require multiple rounds, transposition etc.

As you don't include a nonce or random input to your cipher, your cipher would already be considered broken because identical plaintext would lead to identical ciphertext. This means you are leaking information about the plaintext. This is why stream ciphers or block cipher modes of operations require either a different key for each encryption process (notably RC4) or a unique/unpredictable nonce or IV.

To get any idea of the complexity you could take a look at the book that describes The Design of Rijndael (by the authors of Rijndael, which became AES).


how to represent message as an integer between $1$ and $n-1$ I am trying to implement simple El-Gamal cryptosystem.

And I can't understand how to represent message as an integer between $1$ and $n-1$.
The only thing that comes to my mind is:
 if $n$ bit length is $k$, then divide input message m on $t | t < k$ bits and each piece of bits use as integer number.

I think It is wrong.

So how to represent message as an integer between $1$ and $n-1$?

How do you represent integers on a computer? In binary format:
$$71_{dec} = 100\,0111_{bin} $$

How do we represent letters on a computer? (Mostly) in ASCII format (and ASCII is in binary):
$$\text{A} = 100\,0001_{bin}$$

How do we represent more than one letter on a computer? We concatenate the seperate letters. We use blocks of 7 bits and not 8 bits to save space:
$$\text{Hello} = 100\,1000\,1100\,1011\,1011\,0011\,0110\,0110\,1111_{bin}$$

Now we can read this number as integer:
$$100\,1000\,1100\,1011\,1011\,0011\,0110\,0110\,1111_{bin} = 19540948591_{dec}$$

With this number we can use the normal El-Gamal algorithm. If the number is bigger than $n$, than we have to split the initial message into smaller parts. It doesn't matter how exactly you split it, but be sure that the decryptor knows how you did it so he or she can decrypt it again. Oh, but be warned: El-Gamal is not secure without additional security measures.


Tiny AES vs AES algorithm Is Tiny AES algorithm any different from the standard AES algorithm? I have come across mentions of Tiny AES at a lot of places but none which define it's architecture.

"Normal" AES implementations and tiny-AES perform the same task.

As stated in the README:

  This is a small and portable implementation of the AES ECB, CTR and CBC encryption algorithms written in C.

It's simply an implementation with low memory usage. The reason for the existance of tiny-aes can be traced back to the initial search for a replacement for DES (which would then become AES). One of these requirements were that they should have low memory usage for implementations suitable for example in SmartCards.

As stated in their paper (Second AES candidate conference, section 5) they performed tests on the different submitted AES candidates, one of which was memory usage.


What is the difference between TRNG and CSPRNG? I understand the output of a TRNG is almost impossible to reproduce, such a flipping a coin 100 times to produce a 100-bit sequence. However, it is also my understanding that a CSPRNG produces an unpredictable output.

If they are both non-deterministic are they not the same? Are they not both producing unpredictable outputs?
Do we not use both TRNG and CSPRNG to produce sessions keys?
Can we (do we?) use TRNG to produce CSPRNG?

A True Random Number Generator uses a physical phenomenon not known to be fully deterministic as origin of the discrete values (bits or integer numbers) that it outputs. That phenomenon can for example be a dice throw, thermal noise, disintegration of a radioactive substance… What detects this phenomenon can be followed by a conditioning stage to turn the output into an (at least, near) ideal sequence of random bits. The conditioning is often an integral part of the TRNG.

The archetypal conditioning stage is the Von Neumann debiaser: it groups the values at its input (such as dice values, binary output of a clocked comparator, count of clock cycles between events…) into pairs, and outputs 0, nothing, or 1, depending on if the first element in the pair is less, equal or more than the second. If the input was consisting of independent values, the output (if any) would be independent random bits with 50% probability for 0 and for 1; that is, truly uniform independent random bits (hereafter: ideal randomness).

Unless otherwise stated, a TRNG can be imperfect to some degree: it is to be expected that a statistical test distinguishes its output from ideal randomness.

A Cryptographically Secure Pseudo Random Number Generator is a deterministic (hence the pseudo) computational method to turn an input (typically short or low-throughput, and explicit unless otherwise stated) into a (typically arbitrarily long or/and high-throughput) sequence of bits that are indistinguishable from ideal randomness, with cryptographic certainty, for a computationally bounded adversary not knowing the input, assumed secret and not reused.

In a cryptographic context, a CSPRNG can be abbreviated PRNG or PRG. But in other contexts, not all PRNGs are cryptographically secure. The Mersenne Twister is an example of PRNG that is not cryptographically secure.

A Cryptographically Secure Random Number Generator (not Pseudo) is a random generator with no explicit input, and which output is indistinguishable from ideal randomness, with cryptographic certainty, for a computationally bounded adversary assumed able to attack multiple instances of the CSRNG and obtain multiple output sequences (the adversary can use one CSRNG to attack another; restart the CSRNG, in some attack model s/he can attempt to exploit side channels, inject faults in the calculations made, or/and shutdown power at any time).

The archetypal deterministic CSRNG is built from a CSPRNG and a random secret seed that is not reused (perhaps, with help of permanent memory surviving a power cycle). That is essentially the only way to build a CSRNG without some form of TRNG.

The archetypal non-deterministic CSRNG is built from a CSPRNG, and a TRNG which output is used as input of the CSPRNG at start of each sequence (including power-up). The idea is that the cryptographic strength of the CSRNG comes mainly from the CSPRNG, and the unpredictability across multiple sequences and instances comes from the TRNG.

Note: there are more complex constructions, where the TRNG's output influences the CSRNG continuously, so that hopefully, security will eventually be recovered  after a compromise of the CSPRNG state. A Unix /dev/urandom typically uses this strategy.

A TRNG can be a CSRNG. Any CSRNG must include a TRNG, or must have made use of one as the origin of some secret value at an initialization stage (otherwise, knowledge of the CSRNG structure would allow to predict its output).

It is notoriously difficult to make a good non-deterministic CSRNG even by applying the above principle and using a good CSPRNG. One reason is that in practice, TRNGs often fail, spontaneously or under adversarial influence (for example, an adversary can reduce thermal noise by putting the device in cold condition using evaporation of some liquefied gas, or remotely feed controlled events to a sensor of disintegration). If that goes undetected, the output of the TRNG can become highly predictable, and knowledge of the PRNG will allow to predict its output. Thus a practical non-deterministic CSRNG must test its TRNG, and somewhat prevent any output when it does not operate properly.

On the other hand, a deterministic CSRNG must permanently keep its state secret. Due to the possibility of side channels attacks that's difficult when the adversary has physical access, and it turns out that methods to guard against side-channel attacks require random numbers in vast quantity! Also, there is understandable prevention against fully deterministic RNGs. This adds up to make fully deterministic CSRNGs a rarity in modern high-security cryptographic designs.

Summary of terminology:

A TRNG is not deterministic. Unless otherwise stated, that's its only defining characteristic.
A CSPRNG is deterministic, has an explicit input (unless otheriwse stated), and, with cryptographic certainty, its output is indistinguishable from ideal randomness by a computationally bounded adversary if its input is random, secret, and not reused.
A CSRNG has no explicit input, at least appears not deterministic, and its output is computationally indistinguishable from ideal randomness by a computationally bounded adversary. It can be deterministic, or not. In the former case, it's a CSPRNG with a random secret key that is not reused. In the later case, it includes (or perhaps is) a TRNG.
In a cryptographic context, PRNG or just PRG is synonymous with CSPRNG, and RNG might be synonymous with CSRNG (especially when using a RNG in another construct, rather than discussing its properties). But in non-cryptographic contexts, don't assume any security property from the acronym PRNG: in many programming languages, the default implementation is not cryptographically secure.

  If they (TRNG and CSPRNG) are both non-deterministic are they not the same? Are they not both producing unpredictable outputs?

A CSPRNG is deterministic, and never is a TRNG; and vice versa.

  Do we not use both TRNG and CSPRNG to produce sessions keys?

Often we use a CSPRNG initialized with a shared secret and some other element (like a nonce) to initialize session keys, so that the session keys needs not be transmitted secretly.

If we use the output of a CSRNG or TRNG as a session key, we need to encipher the value produced on one side to transfer it to the other side, which has no way to produce the same session key independently. Further, it we use a TRNG directly, we must use one that is close enough to a CSRNG that the key can't be guessed (that's an issue for short keys).

Another practice is to use a CSRNG or TRNG (often, one on each side) as input to an asymmetric key exchange protocol (like Diffie-Hellman) to produce a shared secret session key.

  Can we (do we?) use TRNG to produce CSPRNG?

No. But we often use a TRNG and a CSPRNG to produce a CSRNG.


Key generation for AES-GCM-256 file encryption I am currently working on a file encryption software that works via AES-GCM-256 and I am looking for feedback on the encryption key generation process I intend to implement.

So far, I have come up with the following process:

User supplies password or key file.

Then, per file that is to be encrypted:

Password/key file from (1 above) is hashed via SHA256 once.
The result from SHA256 is base91-encoded and sent through scrypt (N=2^15, r=8, p=1) with a randomized 16-byte salt to derive a 32-Bit key for AES-GCM.
The file is encrypted and authenticated using AES-GCM with the key from (2) using a randomized 96-bit nonce as iv.
Scrypt-values (N, r, p, and salt) and the AES-GCM nonce (=iv) get stored (unencrypted) in the file header for decryption.

The program does make sure it doesn't process files larger than 2^39 - 256 Bits (size limit for AES-GCM encryption from NIST 800-38D).

Is this design flawed in any serious way?

In general, your concept looks OK to me. I do have a few remarks, though:

Hashing the password before feeding it to scrypt is useless
scrypt can process binary data, so there is no need for the base91 encoding step. Avoid steps that do not have a good reason
Using the slow password hashing function scrypt fo every file will result in a bad performance if you want to encrypt or decrypt a lot of files. Rather create a single masterkey from the password with scrypt and then create the file depending keys using a fast KDF like HKDF.
The biggest problem I can see: You are using a unique key for each file, but that is created by a random salt and not some file information. An attacker would be able to switch the content of two files (without altering it or learning the content) without you noticing it. To prohibit this, you should use some file metadata (preferable a unique file identifier like a file name/path) in the process. Either inject it into the key derivation process (using it as the salt) or authenticate it as additional data with AES-GCM.


Truncating the output of AES-128 I'd like to use the output of a pseudorandom function (PRF) as a one time pad.

I want to use AES-128  (as it's commonly used as a PRF). As we know AES-128 output 128 bits.

Question: Would be secure to truncate the output of AES-128 and get only 32 or 64 bits of it as one time pad to mask some 32 or 64 bits value respectively?

What you describe is exactly using AES-CTR to encrypt a 32-bit or 64-bit message.  So, yes.


May I use Random Oracle for Inversed Look-up? Consider there is a protocol in real world calling a random oracle $\mathcal{H}$ for a priavte input $k$. Then in the ideal world, after the calling of $r \leftarrow \mathcal{H}(k)$ by a honest party, can the simulator extract $k$ from $r$, if the behavior of $\mathcal{H}$ is as follows:

When $k$ is new, record $(k, r \leftarrow_R \{0,1\}^\lambda)$ in the inner storage and then return $r$;
When $k$ has been asked (by checking the inner storage), return the corresponding $r$.

I envisage to extract $k$ from $r$ also by checking the inner storage, but is it a correct usage of random oracle?

Yes, that is standard usage of a random oracle. The simulator gets to simulate the interface to the random oracle so it can record all queries made by the adversary and use this information to "invert" the random oracle.

In your example you must be sure that the simulation does something reasonable when the adversary outputs a value $r$ that is not the result of any call to the oracle.


Why are asymmetric cryptography keys more vulnerable to brute force attack than symmetric ones? I came across this paper which says that

  Asymmetric keys must be many times longer than keys in
  secret-cryptography in order to boast equivalent security.  Keys in
  asymmetric cryptography are also more vulnerable to brute force
  attacks than in secret-key cryptography. There exist algorithms for
  public-key cryptography that allow attackers to crack private keys
  faster than a brute force method would require.

I would like to know:

What makes Asymmetric Cryptography keys more vulnerable to brute force attacks?
In which cases should Asymmetric Cryptography usage be avoided?

For your first question:
The main point here (at least that comes to mind) is that of how the key is made, used, and subsequently how it is attacked. Good symmetric ciphers are designed so that the best possible attack is brute force, i.e. simply trying with each possible key, which are typically random (or as good as). With a 128-bit key you have $2^{128}$ possible keys. Trying all of these takes a lot of time.

With an asymmetric cipher however, the private and public keys have a mathematical relation between them, and asymmetric ciphers are based on problems that are computationally hard to solve. An example of this is RSA, where the keys are based on two large (and secret) prime numbers, $p$ and $q$, then multiplied to create an even larger number, $n$. The result is then used for encryption and decryption (i will not go into further details of RSA here). To crack this system the most straight forward way is to find $p$ and $q$ by factoring $n$ (which is not secret).

Checking $2^{128}$ (or $2^{127}$ on average) symmetric keys with todays computational power is simply not possible within any conceivable time-frame. Factoring a 128-bit number however, takes about a second (depending on hardware and optimization). Thus, one needs larger keys for RSA than symmetric ciphers, e.g. 128-bit symmetric keys are typically approximated to equal 2048-bit RSA keys.

For your second question:
Encryption and (even more so) decryption with asymmetric ciphers are often a lot more computationally intensive than a symmetric cipher (if i remember correctly is RSA typically about 1000 times slower than AES). This makes asymmetric ciphers impractical for encrypting large chunks of data. Subsequently, for encrypting e.g. internet traffic: asymmetric ciphers are typically used for securely exchanging keys that are used to encrypt/decrypt using a symmetric cipher.

EDIT: As rightly pointed out by @fgrieu the statement "128 to 256-bit symmetric keys are typically approximated to equal 2048 to 4196-bit asymmetric keys." is not correct, and comes from a writing-mistake on my part. The correct statement was supposed to be that 128-bit symmetric keys are typically approximated to equal 2048-bit RSA keys.


Probability of Repeated Encrypted Block In Output Feedback (OFB) Mode Is there any probability/chances of repeated encrypted block in Output Feedback (OFB) mode?
Is there any existing documentation/studies about that? If it is existing, can you please provide me a link for that documentation, I want to analyze it carefully, I can't find some documentation about the probability of repeated encrypted block in OFB, maybe it is existing but it is hard to find.

Well, if the block cipher is modeled as a random $N$ bit permutation (that is, each permutation from the set of $2^N$ bit patterns to itself is equally probable), then the answer is really quite easy (and this answer is exact): the probability that we will repeat a block within $M$ outputs is precisely $(M-1) 2^{-N}$ (for $0 < M \le 2^N+1$).

The reasoning behind this is remarkably simple.  First, when we consider the sequence $X, P(X), P(P((X)) = P^2(X), P^3(X), ...$, we see that the first pair of repeated elements must include the starting point $X$.  Here's why: if we have the pair $P^i(X) = P^j(X)$ for $i, j \ne 0$, then we have $P^{i-1}(X) = P^{j-1}(X)$ (remember, $P$ is a permutation, that is, if $P(A)=P(B)$, then $A=B$), and so if we have a pair $i,j \ne 0$, that can't be the first pair.

Now, let us compute the conditional probability that, if we haven't had a repeat after $M-1$ outputs, we get a repeat after $M$ outputs.  Now, after we have cycled through $M-1$ outputs, there are $2^N - (M-1)$ outputs we haven't generated before and $1$ output that we have that might be generated in the next step (the other outputs we have generated are impossible, by the reasoning in the above paragraph).  If we've specified $(M-1)$ outputs of a permutation, the rest of the possible outputs are equiprobable, and hence the probability that we're generate the one output that would generate a repeat is $1 / (1 + 2^N - (M-1)) = 1/( 2^N-M)$

Now, the probability that we'll generate the first repeat at step $M$ is the probability that we'll not generate a repeat after $M-1$ steps, and then repeat at step $M$.  This is:

$Prob(M) = (2^N-1)/2^N \cdot (2^N-2)/(2^N-1) \cdot ... \cdot (2^N-M) / (2^N-M+1) \cdot 1 / (2^N-M) = 1/2^N$

That is, the probability that we'll get a repeat after exactly $M$ steps is independent of the value of $M$ (as long as it is in range).

And hence, the probability we'll get a repeat after $M$ steps (or earlier) is just the sum of the probabilities that we'll generate the first repeat after $k$ steps for $1 < k \le M$, and that's $(M-1)/2^N$.

If you insist on a link, you can look at this one; this uses different logic to come up with the same result.

If the block cipher cannot be modeled as a random permutation (or a random even permutation; that answer differs only in the $M=2^N$ case), well, I don't know on any specific study; that would probably depend on the specific block cipher, and how it differs from a random permutation.


How to calculate Public Key exponent if I have p, q, Dp, Dq, QInv? I have a private key components p, q, Dp, Dq, and QInv. I need to calculate the public key modulus and exponent. Modulus was super simple p*q, but exponent I can't figure out. Have searched all the articles and often found how to go opposite way - generating public private key once you pick the exponenet.

I have been trying ModInverse from p-1 and q-1, and solve x with GCD on all the componenets, but nothing gave me the right value (I know the value I should get is x010001). Seems to be a little bit more complex that this...

Im really in to the code and less in math, so if I could get the answer which use simple math operations as 'Add', 'Sub', 'Multiply', 'Mod', 'ModInverse', 'GCD' etc. would be great!

Your public key contains two numbers. First it is a number n, which is called the Modulus and are computed through $p \cdot q = n$.
The second number is e, which is the public exponent and are used to encrypt your message m. The number e is choosen that it have the following properties:

\begin{equation}
1 < e < \phi(n) = (p-1)(q-1)
\end{equation}
\begin{equation}
gcd(e, (p-1)(q-1)) = 1
\end{equation}

$\phi$ is the euler's totient function.

The private key contains the numbers p,q and d. The number d is your private exponent and p,q are your prime numbers, which helps you do calculate n and the private and public exponent.

The private exponent have the following properties:

\begin{equation}
1 < d < (p-1)(q-1)
\end{equation}
\begin{equation}
d = e^{-1} mod~(p-1)(q-1)
\end{equation}

I am not sure, what are Dp, Dq and QInv in your configuration is, but if you have d you are able to compute e with:

\begin{equation}
e = d^{-1} mod~(p-1)(q-1)
\end{equation}

I hope it will help you. If that doesn't help may specifiy what are Dp, Dq and QInv are.

EDIT:
I think you are using the PKCS#1, which are mentioned in the comments below of this answer.

In the PKCS#1 you are also able to have a quintuple as a private key, which are p, q, Dp, Dq and QInv.

Dp and Dq satisfy the following equations:

\begin{equation}
e \cdot Dp \equiv 1~mod~(p-1) \Leftrightarrow e = Dp^{-1} ~mod ~(p-1) \\
e \cdot Dq \equiv 1~mod~(q-1) \Leftrightarrow e = Dq^{-1} ~mod ~(q-1)
\end{equation}

and the number e have a little bit different property.
The property of e is:

\begin{equation}
gcd(e, \lambda(n)) = 1~and~\lambda(n) = LCM(p,q)
\end{equation}

Additionally your d is satisfying this equation instead of that from above:

\begin{equation}
ed \equiv 1 ~mod ~\lambda(n) \Leftrightarrow e = d^{-1} ~mod ~\lambda(n)
\end{equation}

This equation should give you the right e from your giving d and $e = d^{-1}~mod~\lambda(n)$ means compute the modular inverse from d with the modulus $LCM(p,q)$.

I hope this will help you.


Why is a 2048-bit public RSA key represented by 540 hexadecimal characters in X.509 Certificates? In the public certificate, an RSA public key specified as 2048 bits long is represented by 540 hexadecimal characters. Converted to base-2, this yields 2160 bits, 112 more than the stated 2048.

That's because the public key in DER format (which is a way of expressing X.509 objects as a sequence of bytes) includes more than just the modulus.  Specifically, it consists of:

This is a collection of the following objects; that takes up 4 bytes
The first object is an integer (which happens to be the public modulus); the integer itself is 257 bytes (not 256; that's because ASN.1 integers are signed, and so there has to be a leading 00 to make the top bit zero to signify positive), as well as 4 overhead bytes, for a total of 261 bytes
The second object is an integer (which happens to be the public exponent); if you use 65537 as the exponent, this takes up a total of 5 bytes long (including overhead)

4+261+5 gives you a total of 270 bytes, or 540 hexadecimal characters.

This assumes that the encoder uses an RSA public exponent of 65537 (or some other value between 32769 and 8388607, all of which would encode in the same length); 65537 is by far the most common value nowadays, but is not mandated.

Note that this does not count the encoding that says "this is an RSA public key"; that takes up an additional 24 bytes (including overhead).  That's generally included in public keys, but apparently you're not counting that part; that would bring the length past the 540 hex characters you see.


ECM Implementation is really slow I followed the algorithms 14.4 (computes 1st and 3rd coordinates in (X,Y,Z)#k modulo n) and 14.5 (factorization using ECM) in David Bressoud's book 'Factorization and Primality Testing'. I think the algorithm is similar to Lenstra's, it uses the formula Y^2 - X^3 - aX, where the values for X,Y and a are chosen at random.

Here is my code in C++: http://pastebin.com/EnqCyJkk

I also found someone else's implementation of this algorithm, it's easier to read than mine: http://futureboy.us/frinksamp/ECM.frink

The program eventually finds factors, but it is really slow, I'm not sure if this is just a slow algorithm, I'm using the wrong parameters, or I have coded something incorrectly.

Any input would be really helpful, I've pretty much given up on this factoring obsession :/

I don't have David Bressoud's book, and so I can't say whether you made a mistake or he did.  However, the algorithm you're using might come from the preliminary steps of Lenstra's method; however, it's missing the part that is designed to actually find the factors.  In addition, as written, it can be shown (as written) to be lousy; not much better than trying random factors.

Here's the demonstration that it is a poor method:

Your method is to pick random values for $a$, $X$ and $Y$, and compute $GCD( n, P(a, X, Y))$ (where $P$ is a polynomial in the three variables $a$, $X$ and $Y$); you succeed if the $GCD$ is neither 1 nor $n$.

Another way of looking at it is that one of the necessary conditions for you to succeed is for $P(a, X, Y) = 0 \mod p$, where $p$ is one of the prime factors of $n$.  However, if we consider $X$ and $Y$ fixed, then $P(a, X, Y)$ is a cubic polyinomial in $a$ (and is not the zero polynomial); such a polynomial has at most 3 zeros modulo a prime.  That is, if we pick $X$ and $Y$ first, we have at most 3 value of $a \bmod p$ that will give us a solution; hence the probability of us picking such an $a$ is at most $3/p$.  By symmetric, this also applies to the other prime factor $q$ of $n$ (assuming that there are only two), and hence the success probability per iteration is at most $3/p + 3/q$.  This success probability is maybe a factor of 6 larger than picking a random value $r$ between 1 and $\sqrt{n}$, and checking if that's a factor (factor of 6 assuming $p \approx q$)


Random Number Generation with a Entropy pool versus Seed To give a little background I'm currently implementing a crypto library in JavaScript.

I have started porting across Linux's random number generator because its both publicly scrutinized, it is open-source, and is extremely well documented. After browsing around other implementations before settling on Linux's RNG, most of the other implementations like the Mersenne Twister and other PRNGs all use single byte seed values as their single source of entropy and to add more entropy you simply XOR the seed value with your "stream of entropy". Linux's RNG however uses a pool of entropy which consists of, as it sounds, a larger array of "seed" values in which all are considered to have a high amount of entropy. To add entropy, you simply XOR the entropy into the pool and mix it around with a few polynomials and hash it all to hide the internal state.

What I want to know is what are the benefits of using an entropy pool over a single byte seed value? It also sparks the question, considering Linux's RNG is used almost globally across the entire kernel and by every application requiring random data, is the "seed" or entropy source dependent on its use case? If only one application will be using the RNG at a time, is a single byte seed just as secure as a larger pool of entropy? Is the only reason Linux uses an entropy pool is to not give away any hints on internal seed state if other applications pull random data from it?

I guess what I'm trying to ask is what are the benefits of using a single byte seed value over an entropy pool, and is an entropy pool relevant for single user RNGs where only a single, trusted user uses the RNG?

What I want to know is what are the benefits of using an entropy pool over a single byte seed value?

There are no benefits of an entropy pool. It's a  necessity.  If anything, it's a strong  indicator of a poor true random number generator (TRNG) and hints at the construction actually being a de facto pseudo random number generator (PRNG), which I believe /dev/random to be.

The golden rule of any TRNG is that H(in) >= H(out) where H is entropy. The following diagram illustrates the Linux random number generator's entropy pool.

As the input events are totally irregular and of indeterminate frequency, H(in) cannot be calculated.  You can easily wait >60 seconds for a single random output byte to become available.  You mention that the Linux implementation is well documented.  Not for this point.  There is no quantitative assessment of input entropy that I can find in the literature.  The best is the report at the bottom, but that still accepts the developers' assessment of 1 bit of entropy/event.  It might well be far lower but as stated, irregular events cannot be given a rate.  No one has undertaken an accurate entropy measure of the jiffy events themselves. δ3s are not valid units of entropy.  Ergo the golden rule is not proven.

Thus the entropy pool acts as an accumulator and low pass filter to smooth the jiffies.  You will have had to implement this for yourself in your Javascript port.  Re iteratively hashing the pool is very much akin to the re permutations of a sponge construct during the squeeze phase, and thus another parallel with a PRNG.

TRNG are all about real entropy and it's accummulation.  Any port of /dev/random will have to address the capture of entropy from a machine, and as Javascript is more highly abstracted than the kernel, it will be harder. But a pool will be unavoidable.  You cannot easily re seed a generator's state byte by byte and bit by bit as irregular entropy events are detected.  Whether you implement a direct copy of /dev/random or some NIST CSPRNG, you'll need the pool to cheat. It's got nothing to do with the number of concurrent applications. You're confusing the entropy pool with a connection pool.

This question may be a trifle stale, but the answer is still relevant today for anyone developing a true random number generator.

Ref. François Goichon, Cédric Lauradoux, Guillaume Salagnac, Thibaut Vuillemin. Entropy transfers in the Linux Random Number Generator. [Research Report] RR-8060, 2012, pp.26.


Is storing original file size in an encrypted file header a bad idea? I'm encrypting a file using AES-256 in CBC mode. I'm padding to the 16-byte input multiple by using the PKCS#7 limit. The problem I'm currently having is that if I'm transferring or reading the encrypted file over a socket, I won't know when the encrypted file has been finished, as I'm reading it in chunks. Because of this, I won't know when to trim the PKCS#7 padding from the decrypted file chunks. (I won't know the size of the decrypted data in advance, so I won't know where to look for padded bytes and to trim them.)

One solution I've thought of would be to include the unencrypted file size in the header of the encrypted file, but I'm not sure if this is a security threat or not. Is this a bad idea?

Edit

I have kind of a strange setup. Encrypted data is stored like so:

$$s \longrightarrow e_{m} \longrightarrow d$$

The source data $s$ is passed to $e_{m}$, the encryption method, over a socket. As $e$ encrypts the data, it simultaneously writes the data over another socket to the destination $d$.

Retrieval works in the inverse:

$$d \longleftarrow d_{m} \longleftarrow s$$

The encrypted source $s$ is passed through the decryption method $d_{m}$, which decrypts it and passes the decrypted data to destination $d$.

With this in mind, how can I maintain padding with AES? The contents being transferred are files, so they are inherently and usually larger than 50 bytes of data. The problem seems to be $e_{m}$ and $d_{m}$ not knowing the size of the input data and simply encrypting block-by-block.

How can I create a decryption method which, not knowing the size of $s$, will still be able to decrypt the data and send it to $d$?

The 16-byte IV and ciphertext (which together are part of the output of $e_m$) are assumed to be intercepted by an adversary. That reveals the number $b$ of 16-byte blocks in the ciphertext. With CBC and PKCS#7 padding, $b=\big\lceil{{n+1}\over16}\big\rceil$ where $n$ is the byte size of the plaintext (the file size). Putting $n$ itself in a header thus reveals a little extra information: $n\bmod16$, which is worth 4 bits. In some cases, e.g. if what's encrypted is yes ($n=3$) or no ($n=2$), this is enough to ruin security. Thus no, it is not always safe to include the original file size in clear. But in practice, it is often assumed that the length of the data can be public; then it can be sent in clear.

There's a fix to solve the networking problem as originally exposed while revealing no more information about the length of the plaintext than implied by the use of CBC and PKCS#7 padding: in the header, put the number of blocks $b$ in the ciphertext (not counting IV), or equivalently $\big\lceil{{n+1}\over16}\big\rceil$, where $n$ is the size in bytes of the file to encipher.

But caveat emptor: the above fix is mostly of theoretical interest. While it maintains security in the yes or no case, it does not work for my_answer_is_yes ($n=16$) versus my_answer_is_no ($n=15$); or if the plaintext is a JPEG image known to be either out of focus (thus quite compressible, thus small), or well-focused (thus less compressible, thus bigger). Most encryption modes leak a lot information about the length of the plaintext, and this can be exploitable. This effect can be the basis of attacks on VOIP encryption. In most cases where the size of the data reveals information to an adversary, standard operating modes such as CBC are just inadequate.

Update following edit of the question: the networking problem as now explained could be solved by having $b$ computed from $n$ and sent in clear at the beginning of each of the 3 streams involved; the PKCS#7 padding performed by the process reading the file and sending it to $e_m$ (not by $e_m$); and the PKCS#7 un-padding performed by the process retrieving the output of $d_m$ (not by $d_m$). But then the block size (16 bytes) needs to be known by all 4 processes involved, when we would want to isolate that detail, and padding, to the two processes $e_m$ and $d_m$.

It is also possible to have the file size as the first block of the plaintext, CBC-encrypted as the rest. This allows to have everything regarding encryption, its block size, etc.. isolated to $e_m$ and $d_m$. If the length is encoded in a single dedicated block (e.g. the first of the plaintext, thus the one XOR-ed with the random IV), it does not leak more information about the size of the plaintext than implied by CBC-encryption with PKCS#7 padding, just as in the original fix.

Note: I now realize the title mentions an encrypted header, and the question mentions an unencrypted file size in the header. I've been considering the later in all except the previous paragraph.

Note: There is nothing to protect integrity of the data; that is often a very real problem.


Proving the CCA-insecurity of El Gamal encryption scheme I am trying to prove that El Gamal Encryption is not CCA-Secure.

If an adversary queried the encryption oracle for the encryption of $m=1$, he'll get a pair $(c_1,c_2)=(g^y,g^{xy}\cdot m)=(g^y,g^{xy}\cdot 1)=(g^y,g^{xy}).$ Then he could calculate $g^{-xy}$. Then he sends the challenger a pair $(m_0,m_1)$. When he gets the challenge ciphertext $(c_1^*,c_2^*)$ he can decrypt it and finds out which message has been encrypted. Hence, the adversary wins the experiment with non-negligible probability.

Does this prove make sense, or did I miss something?

Thanks in advance.

Edit

This solution does not work since the value of y does not belong to the key, but it's generated randomly for every encryption.

A right solution would be as follows:

The adversary chooses some messages $m_0=x\ and\ m_1=y$. Then he sends these two messages $(m_0,m_1)$ to the challenger and get the encryption of one of them $<c_1,c_2>$. Then he picks some z and multiplies it with the  $c_2$ so he gets a new ciphertext $<c_1, c_2 . z> $. Then he queries the decryption oracle for the decryption of the new ciphertext. So, the resulting plaintext is either $x . z$ or $y . z$. Hence he can know which message has been encrypted.

No, as written, your technique doesn't work (as there's no specific reason why the encryption oracle use the same $y$ as the challenge ciphertext).

You need a different approach.  For one, the adversary doesn't need to depend on an encryption oracle; if he has the public key, then he can encrypt anything he wants.  What he does need to do is use the decryption oracle (as that performs an operation that the adversary cannot do himself).

So, how can the adversary create a ciphertext which is not the same as the challenge ciphertext, but when submitted to the decryption oracle, would tell him the answer?


How to Check Strength of RSA Public Private Key How to measure strength of RSA public private key pair. is it enough to only measure the length of primes used to generate N? how to check that primes p,q used to make N were selected truly randomly from a given RSA public private key pair data? Any reliable method of generating public private key pairs and certificates which uses good randomness to for selecting p and q?

RSA public/private key pairs are no exception: there is no way to assess that a cryptographic key is strong by looking at its value; only ways to assess that it is weak. And lack of signs that it is weak is no good indication that it is strong. Arguments are extensions of:

A key which value leaked is totally weak, and has exactly the same value as before it leaked; hence examining the key's value can not demonstrate that the key is strong, or provide a solid indication about that.

Extension: a key that was generated by a strong method from the output of a public Cryptographically Strong Pseudo Random Number Generator which seed was chosen in an undisclosed way, is weak and indistinguishable (by definition of  Cryptographically Strong) from one generated similarly except from a truly random seed, which is strong.

It is even hard to conclude that an RSA key is weak by looking at its value (except in extreme cases, like a short public modulus, or when all but one of its prime factors can be compressed into a very small amount of information); in particular, tests concluding that an RSA key does not meet criteria expected for conventionally generated RSA keys are no proof that it is weak: an RSA key can still be strong if it has regular patterns in half the high-order bit of the public modulus $N=p\,q$, or/and some of the high-order bits of $p$ and $q$; or a private exponent $d$ significantly smaller than $N$.

So what can be done? Basically, have the key generation process competently audited. By extension, the audit should also cover how the key is kept secret, including during use.

One common modern referential for RSA key generation is NIST's FIPS 186-4, section 5 and references including Appendix B.3 (with some origins in ANS X9.31:1988); but that has limitations:

FIPS 186-4 formally allows only for 1024-bit, 2048-bit, or 3072-bit public modulus; the former is obsolete, and 4096-bit or even more is increasingly common, for reasons that are at least understandable.
FIPs 186-4 requires public exponents $e>2^{16}$ and public moduli with two primes factors, when sometime performance considerations dictate otherwise (the public key function is up to about 8 times faster with $e=3$ than with $e=65537$; for constant modulus size the private key function is up to nearly $k^2/4$ times faster in software when there are $k$ factors, and using available hardware support might require $k\ge3$).
FIPS 186-4 does not give prescriptions for a random generator complete with entropy source and testing procedures; it is thus perfectly feasible that an intentionally weakened random number generator makes an implementation honestly certified compliant to FIPS 186-4 vulnerable selectively to those in the know.
FIPS 186-4 has 5 methods (B.3.2 to B.3.6), and choice can be a burden; they vary according to several criteria

Use of any RNG (possibly non-deterministic), or of a PRNG with seed of precisely twice as many bits as the conventional security strength of the key prescribed by SP 800-57 Part 1;
Use, or not, of auxiliary conditions on the primes generated (being $p$ such that $p-1$ and $p+1$ each have a large auxiliary prime factor); notably, that complication is mandated for 1024-bit moduli, and thus unavoidable for conformant implementations that need backward compatibility. That contributes to the significant difficulty of making a marketable truly FIPS 186-4 implementation for constrained environments such as Smart Cards.
Use of probable or provable primes, for the factors of the public moduli or/and the auxiliary primes.

The precision of FIPS 186-4 is a double-edged sword: that makes it feasible to automatically prove non-conformance without false positives; but that makes it feasible to exploit a conformant FIPS 186-4 implementation using a known rigged RNG without knowing the details of the implementation.
FIPS 186-4 is totally lacking about protection against side-channel leakage and fault attacks, including during key generation, even thought that conceivably can matter in some cases (e.g. Smart Cards supposed to securely generate a key on the field).

A less common referential is ETSI TS 102 176-1 V2.0.0 (2007-11), which pays its simplicity at the price of vagueness:

  To generate the key pair two prime numbers, $p$ and $q$, are generated
  randomly and independently, satisfying the following requirements:

  the bit length of the modulus $n\;=\;p\,q\;$ must be at least MinModLen; its length is also referred to as ModLen;
  $p$ and $q$ should have roughly the same length, e.g. set a range such as $0,1 < | \log_2p - \log_2q | < 30$;
  the set of primes from which $p$ and $q$ are (randomly and independently) selected SHALL be sufficiently large and reasonably uniformly distributed.

Notice the use of e.g. in the second bullet; and that the bounds then proposed are extremely different from those of FIPS 186-4, are not met for about 1/3 of keys generated according to FIPS 186-4, and often lead to private keys that can not be moved to many implementations designed for FIPS 186-4.


AES-GCM encryption and decryption doubts I'm using AES-GCM mode in my project and I have some doubts.

public String encrypt(String plainText, String authenticationTag) throws GeneralSecurityException, IOException {
        Cipher cipher = Cipher.getInstance(ALGORITHM_MODE_PADDING);
        final int blockSize = cipher.getBlockSize();
        SecretKey secretKey = readKeyFile(...);
        byte[] plainTextByte = plainText.trim().getBytes(Charset.forName("UTF-8"));
        byte[] ivBytes = generateIV();
        cipher.init(Cipher.ENCRYPT_MODE, secretKey, new GCMParameterSpec(GCM_TAG_LENGTH, ivBytes));
        cipher.updateAAD(authenticationTag.getBytes(Charset.forName("UTF-8")));
        byte[] encryptedMessage = cipher.doFinal(plainTextByte);
        byte iv_and_encryptedMessage[] = concatIvAndCipher(ivBytes, encryptedMessage, blockSize);
        Base64.Encoder encoder = Base64.getEncoder().withoutPadding();
        String iv_and_encryptedText = encoder.encodeToString(iv_and_encryptedMessage);
        return iv_and_encryptedText;
    }

    public String decrypt(String iv_and_encryptedTextBase64, String authenticationTag)
            throws GeneralSecurityException, IOException {
        Cipher cipher = Cipher.getInstance(ALGORITHM_MODE_PADDING);
        final int blockSize = cipher.getBlockSize();
        Base64.Decoder decoder = Base64.getDecoder();
        byte[] iv_and_encryptedMessage = decoder.decode(iv_and_encryptedTextBase64.trim());
        byte[] ivBytes = extractIvFrom(iv_and_encryptedMessage, blockSize);
        byte[] encryptedTextBytes = extractEncryptedMessageFrom(iv_and_encryptedMessage, blockSize);
        SecretKey secretKey = readKeyFile(...);
        cipher.init(Cipher.DECRYPT_MODE, secretKey, new GCMParameterSpec(GCM_TAG_LENGTH, ivBytes));
        cipher.updateAAD(authenticationTag.getBytes(Charset.forName("UTF-8")));
        byte[] decryptedByte = cipher.doFinal(encryptedTextBytes);
        String decryptedMessage = new String(decryptedByte, Charset.forName("UTF-8"));
        return decryptedMessage;
    }

Questions:

I'm using a GUID as authentication tag which is binding to a user to whom the sensitive information belongs. The encrypted text and tag is stored in separate databases at separate locations. Is this OK?
From what I've read AES-GCM takes in (plain text, IV, key, associated data) and outputs (cipher text, authentication tag). Are associated data and authentication tag the same thing, because my implementation of encrypt and decrypt work when I pass same value in cipher.updateAAD(...)? How to obtain the authentication tag after encrypting?
Should I use Bouncy Castle instead of using default Java implementation?
If the data to encrypt is 16 bytes, when should I generate a new DEK for enc/dec?
One master KEK for all DEK's? For encrypting DEK's should I use same AES implementation? If not, then what to use?

1) I'm using a GUID as authentication tag which is binding to a user to whom the sensitive information belongs. The encrypted text and tag is stored in separate databases at separate locations. Is this ok?

You're not using the GUID as authentication tag, you're using it as additional authenticated data, which is OK, especially since you've already shared a key. The authentication tag is - when using the somewhat hacked Java API - output at the end of the ciphertext.

  2) From what I've read AES-GCM takes in (plain text, IV, key, associated data) and outputs (cipher text, authentication tag). Are associated data and authentication tag the same thing, because my implementation of encrypt and decrypt work when I pass same value in cipher.updateAAD(...)? How to obtain the authentication tag after encrypting?

No, see above. If you want to get the authentication tag you may want to strip it off the end of the ciphertext.

  3) Should I use BouncyCastle instead of using default Java implementation.

Not unless you want to forgo AES-NI and GCM optimizations. I'd stay away from Bouncy Castle for implementations already present in the API provided by OpenJDK / Oracle runtimes.'

  4) If the data to encrypt is 16 bytes, when should I generate a new DEK for enc/dec.

See the NIST GCM specifications; in general it depends on the authentication tag size, so there multiple answers possible.

The constant value of GCM_TAG_LENGTH is not displayed in the code of the question though, so it is unclear what the authentication tag size is in your particular case.

In the comments an authentication tag size of 128 bits was mentioned. The NIST GCM specifications are not entirely clear on that, so I asked for the sizes in this question which was answered a whole lot later.

  5) One master KEK for all DEK's? For encrypting DEK's should I use same AES implementation? If not, then what to use?

That depends on the protocol and, in the end, the use cases and threat model. But in general I'd use a KDF such as HKDF to derive keys rather than to wrap (encrypt) them. Now for that you might want to use Bouncy Castle, because there aren't any good KDF's implemented in Java itself.


Is the salt used with PBKDF2 secret? I have two network endpoints that need to use the same derived key.  Can the server send the salt to the client 'in the clear'?

Yes. Salts are only there to make a particular key derivation globally unique. They have no requirement of secrecy.


Fast Salsa20 in java? For Java I'm only aware of the Bouncy Castle implementation of Salsa20. However, that version is significantly slower than AES-CTR and ARC4.

There are plenty of libraries in C, but are there any good implementations of this stream cipher in Java?

I doubt you will find a fast implementation of Salsa20 in Java (having spent much time attempting to achieve just this).

Salsa20 mutates a 512 bit state made up of 16 x 32 bit integers, which means that implementations that don't take advantage of SIMD (on Java or otherwise) will probably not perform well - there are too many independent state parts to keep them all in general purpose registers on any common architecture, so you inevitably incur load/store overhead, which kills your throughput.

Java (Hotspot at least) does a reasonable job of optimising all the basic operations (e.g. inlining, single instruction rotate etc.) but it doesn't have the smarts to dynamically do small scale SIMD optimisations.

I've tried various approaches to get around this: simulated SIMD by packing 32 bit integers into 64 bit longs (too many additional instructions); triggering hotspot vectorisation optimisations (too much array munging overhead), and didn't find anything that worked.

By comparison: Threefish 512, despite having the same state size uses 8 x 64 bit words, so on 64 bit Java the entire state can be held in registers, and the performance is ~150% the speed of AES.

The BouncyCastle Salsa20 implementation can be pushed a bit (by registerising the state as much as possible) to get it just faster than AES, but it's still woefully slow compared to implementations on SIMD capable platforms.

XSalsa20 and ChaCha will have the same issues, as they have the same basic structure.


Need help finding keysize for Vigenere cipher I am doing a crypto challenge for breaking a Vigenere style repeating XOR encryption (https://cryptopals.com/sets/1/challenges/6).
I have looked at similar questions asked here, mainly this one: Finding a keylength in a repeating key XOR cipher But I am still unabe to determine whats the best way to find the length of encryption key.
I have a Base64 text (which I converted into hexadecimal value) that has been encrypted using repeating XOR encryption (a key of unknown size was repeated and sequentially XOR-ed across bytes of the plaintext).
The challenge suggests taking first and second keysize worth of bytes (for each keysize in some range) and counting Hamming or edit distance between them (and normalizing them by dividing by keysize). And that keysize with lowest distance should be the length of the key (no explanation is given why this should work, and I dont quite understand it). I have tried this method, but unfortunately I am not getting the correct keysize. Here's my pseudocode
for keysize in 2..100:
    a = bytes[0:keysize]
    b = bytes[keysize:(2*keysize)]
    score = hamming_distance(a,b) / (8*keysize) // mult by 8 since each byte is 8 bit and edit distance is counted by bits

(I tested this on my own encrypted message which I encrypted with keysize: 3 and it did not give me the correct result)
I have also tried calculating edit distance across several adjacent keysize worth of bytes and then averaging them (like the answer on linked post suggested), but that too didn't work.
I also tried doing Friedman's test, but later realized that this couldn't really work in my case as encrypted message consists of random binary characters, not 26 English alphabet letters.
What is the best approach for finding the correct keysize?

For the explanation to why this approach works I found an excellent answer here: repeating-key xor and hamming distance
And I managed to finally find the correct keysize using the following pseudocode:
dictionary = () // dict or hashmap which stores <Keysize, Score> as <K,V> pair
for keysize in 2..max_keysize:
    n = 0, score = 0
    while True:
         if 2*keysize >= bytes.len():
             break
         a = bytes[:keysize]
         b = bytes[keysize:2*keysize]
         score += (hamming_distance(a,b) / (8*keysize))
         n += 1
    averaged_score = score / n
    dictionary.add(keysize, averaged_score)

And finally you select keyisze with lowest averaged_score


Why can the last block contain a full block of padding in CBC Encryption? I'm trying to understand the SSL Poodle Attack and I'm wondering why the last block of a CBC Record can be full of padding? Wouldn't that mean that the useful data was already a multiple of the key size?

Maybe I'm misunderstanding something else here, as it would seem like you can pad by any number of full blocks of padding. Just don't see why an SSL Library would do that.

Thanks!

Yes, we always have to pad the message. The reason is simple: How do we know if the message has a padding or not if we don't always pad?

Let's say we pad with adding only $0$ bits. We got the (after padding) message $0101\,1100\,0000\,0000$ and a block size of 2 bytes (16 bits). Well, what was the original message? Was it $0101\,11$? Or was it $0101\,1100$? We don't know.

We can of course pad with one $1$ bit and then as much $0$ bits as needed. This works every time if the message size is not a multiple of the block size, but not anymore of it is exactly a multiple of the block size. We would not know if the last $1$ and $0$s are padding or part of the mssage. Because of this we need to pad even if the message is already in "perfect size".


Leak-proof protocol: is such a thing possible? Is it possible to design a protocol that by itself guarantees that a malicious implementation cannot leak secret data without breaking the protocol?

Setting:

Alice and Bob have a pre-shared secret key K. Using this key, Alice encrypts a bunch of plaintexts and sends them to Bob as a collection of files. The plaintexts are short-ish texts in a natural language.
Each plaintext is encrypted independently of others, and must be decryptable independently. Some sort of authenticated encryption is used.
Eve receives a copy of the collection. This is the only data she gets (i.e. no timing or other side channels). She does not communicate with Alice (but can have a previous arrangement with her, e.g. pre-share some secret keys). Alice cannot communicate with Eve directly, or otherwise send out any data except as defined by this protocol.
We want to ensure that Alice cannot manipulate the encryption, without consequences detectable by Bob, in such a way that Eve can obtain information about the secret key. We assume that transmission is 100% reliable, so if Bob can't decrypt some of the files, he will conclude that Alice is a bad actor.
Also, obviously, we don't want Eve to obtain the plaintexts. It's tolerable if Eve can detect multiple copies of the same plaintext.

It seems that any kind of randomness in the protocol has to be excluded.

For example, if we use an encryption scheme with random IV which is prepended to the ciphertext, Alice can just encrypt the secret key K using another secret key known to Eve, Ke, and apply it instead of IV (IV := E(Ke, K)). Instant leak!

If our protocol adds randomness to the plaintext itself (before encryption), Alice still can manipulate the encryption result by choosing the random value. In the worst case she will have to use brute force, changing the random bits until specific bits of the ciphertext assume the values she wants. On average, she will need about 2n iterations to leak n bits of data. If, say, 1000 encryptions is a small enough number to be unnoticeable on any modern equipment (even "weak" such as a smartphone), then Alice would be able to leak ~10 bits of data per encrypted file.

The next thought I tried is to use deterministic encryption with Synthetic IV based on plaintext (similar to SIV-CTR construct). Besides obvious drawbacks caused by the low entropy of the natural-language plaintexts, this scheme still does not preclude Alice from leaking if she can manipulate plaintexts in a way not obvious to Bob. For example, she can try adding spaces at the ends of text lines, or insert some non-spacing Unicode chars, until she gets desired bit pattern in the ciphertext. (I don't know how to estimate the effort she'll need to leak n bits per ciphertext. Is it still O(2n), as in previous case?)

The last option seems better than others, because the manipulations are detectable by Bob, at least potentially. But this detection happens outside the domain of the protocol, and is not reliable. Are there other possibilities?

It doesn't work without further restrictions.

For simplification, let's assume Alice encrypts a bunch of files but doesn't have to send all of them to Bob. She can still decide to re-order the files or leave out some.

Then she can encode the secret shared key between Alice and Bob in the least significant bits of the ciphertexts without changing the files. She is only rearranging them so that Eve can extract the key. But if Bob checks the integrity of each message, it holds.

If more files are transmitted than the keylength, this works. Otherwise, more than one bit has to be encoded in less messages. And in order to get enough decryptable ciphertexts more files might have to be encrypted.


Possibility for same Private Key Generation in identity-based encryption In private key generation of IBE scheme, private key is generated as follows: $SK_{ID}=s.H(ID)$
Suppose two servers use the same curve domain parameters.
If PKG on server A generates private key $SK_{ID}=s.H(ID)$
PKG on server B generates private key $SK_{ID}=b.H(ID)$
for the same ID.
If there are more than 100000 servers, will there be possibility for generating same private key?

I assume $s$ and $b$ are the main master secret key components of two IBE servers.

If $s=b$, then $SK_{ID,s}=SK_{ID,b}$ provided that the curve parameters and the hash function $H$ are the same. Now, the question is what's the probability of two IBE servers generating the same master secret key components. This depends on the actual scheme and the field it is defined over.

In IBE, mostly pairing-based groups are used. We usually have $s,b\in \mathbb{Z}_{r}$ where the curve is defined over $\mathbb{F}_q$. For example, $r$ is set to be a solinas prime for Type A pairing in PBC. The default values for Type A pairing are $|q|=512$ and $|r|=160$. So, the probability of at least two of $n$ servers generating the same master secret key is essentially the Birthday Problem and can be computed as such:

$$\begin{eqnarray}
p(n) & = & 1 - \frac{r!}{r^n\left(r-n\right)!}\\
& = & 1 - \frac{\prod^r_{i=r-n+1}i}{r^n}\\
& = & 1 - \prod^r_{i=r-n+1}\frac{i}{r}
\end{eqnarray}$$

The probability is roughly $3\cdot 10^{-39}$ in your case. Here's the groovy script I calculated it with. The result is $3\cdot 10^{-42}$ under the assumption that $|r|=170$.


Why Camellia paper declares that it is faster than Rijndael while it is actually much slower? I'm writing an assignment on Camellia cipher, reading the [NTT paper][1] they declare a speed at least comparable with Rijndael, but, searching around, I found that it is actually much slower [2]. I thought this may be caused by AES using specific cpu subsets, but even without them it is faster than Camellia with them [3].

[1] : https://www.cosic.esat.kuleuven.be/nessie/updatedPhase2Specs/camellia/camellia-v2.pdf

[2] : https://www.jmest.org/wp-content/uploads/JMESTN42351298.pdf

[3] :
What is the fastest block cipher in the (Intel) world?

The paper says it is comparable in speed hardware and software to the AES finalists.

If we look at low end hardware performance, say cycles and resource bytes on a Z80 smart card:

Cipher         Keysched  Encrypt  RAM-KS RAM-ENC ROM-Total
----------------------------------------------------------
AES            10318     25494    32     34      980
Camellia       5146      28382    44     62      1698
Twofish        28512     31877    56     34      2808
RC6            138851    34736    90     124     1060
MARS           21742     45588    512    60      5468
Serpent        147972    71924    96     68      3937

AES is the fastest, but only about 11% faster than Camellia, all the other finalists are slower. Resource usage is also good, I would say their claim of being comparable is accurate, if not understated.

If we look at modern CPUs with hardware acceleration, what you saw was that AES is about 4 times faster. Without the hardware acceleration, Camellia is 2/3 of the speed of AES, slightly faster than Twofish, and faster than Serpent. I would say the claim still holds here, just not as strongly against AES.

For FPGA hardware from the Camellia paper in 2001, AES was clocked at 1540Mb/s using 1857 slices, whereas Camellia was clocked at 6750Mb/s using 9692 slices. Comparing rate/slice, they are within 20%. On other FPGA and AES with higher gate counts, AES will have a strong advantage, the Amphion CS5240X2 core on Xilinx Virtex2 clocks at 10Gb/s using only 2200 slices... and AES on Virtex4 clocks at 17.9Gb/s using 18400 slices, very very fast. AES is most likely more efficient on Virtex5, it can perform at 4Gb/s using only 350 slices, which 12 times the rate/slice of Virtex4. Camellia on Virtex5 using 132 slices operates at 85.4Mb/s, much slower. On a Spartan-3, AES does 2640Mb/s using 390 slices, and Camellia does 33Mb/s using 321 slices and half the clock speed.. or roughly 1/40th the rate per clock.

For ASIC, unrolled (1 cycle) on a 180nm process, Camellia performs at 25MHz using 355K gates, and an Amphion CS5240TK AES chip performs at 200MHz using 203K gates, a big difference, and a win for AES at 8 times the speed.

The closest looped ASIC frequency/area match is a 172Mhz 21 cycle Camellia implementation running at 1051Mb/s using 11.87K gates, vs the Amphion CS5220TK 200MHz 44 cycle processor at 581Mb/s using 14.8K gates, I call that one a win for Camellia since the speed per gate is more than double.

In the proposed Cryptoraptor configurable cryptographic processor, Camellia and Twofish run at half the speed of AES.

Considering that Camellia is a more complex cipher with more rounds, I consider their generalized claim of "comparable" to the finalists to be accurate, the AES winner Rijndael on the other hand does have an advantage due to its simplicity and low resource usage, based solely on the round count you would expect it to be 60% faster than Camellia in software table lookup, which it is. You can generally expect AES to be at least twice as fast in high end hardware, and about the same speed in low end hardware.


Can NORX32-f be used in a Salsa20 style stream cipher? #include <std_roll_your_own_crypto_warning.h>

With the third round CAESAR candidates about to be announced, the design[0] of Salsa20/ChaCha + Poly1305 is still looking good in a number of ways, including software performance.  However, LRX algorithms have a major advantage when it comes to (relatively) efficient masking/blinding[1].

https://cr.yp.to/snuffle/design.pdf
http://keccak.noekeon.org/NoteSideChannelAttacks.pdf

NORX[2] is a sponge based design similar to Keccak/SHA-3 and the Keccak-p based Keyak[3] CAESAR candidate but designed with efficient software performance in mind.  However, it is not as efficient as ChaCha20/Poly1305[4] in software, particularly if you want 256-bit keys on 32-bit systems.

https://norx.io/data/norx.pdf
https://competitions.cr.yp.to/round2/keyakv2.pdf
https://tools.ietf.org/html/rfc7539

So the question is, are there any obvious issues to using NORX32-f in a Salsa20 style stream cipher, using the pseudo-addition operation $H()$ to add in the initial state the way Salsa20 does?  What, if any, different security properties are needed for the stream cipher usage vs. the sponge usage?

NORX's $F^l$ is meant to behave as a random permutation (modulo some known harmless properties), given enough rounds. $F^l$ is similar to the ChaCha double-round in all but the addition operation, which is replaced by $H$, and the rotation constants.

NORX should be usable in a Salsa20/ChaCha-style mode; a break in that mode would likely spell trouble for the NORX sponge mode as well. Note that the last step, adding in the initial state, can be simply done with xor; no need to use $H$ in there. Since you lose authentication by using this mode, the cost of an independent MAC should also be taken into account.

Another option to improve NORX32's performance would be to use the parallel mode. With, say, $8$ lanes you could use AVX2 to compute all of them simultaneously. Since NORX suffers from being a purely sequential mode, this would improve performance by a factor of 2 or more. This would not, however, be an 'official' CAESAR-submitted mode.

That being said, I cannot recommend using the NORX permutation in these modes, nor can I recommend using NORX in any form whatsoever just yet. This is a cryptographic primitive in its infancy, and its strong security should not be assumed.


Prove I know a value $v$ in a Pedersen Commitment without revealing it Given a Pedersen Commitment:

$P = aG + vH$

Where $G$ and $H$ are points in some group. $a$ is a blinding value/mask and $v$ is the value I wish to commit to.

Is there a way to prove I know $v$ without revealing it?

This extension of the Schnorr protocol would appear to work:

$P := aG + vH$

$\operatorname{GenProof}(a, v)$:

$x, y \leftarrow Z_q$
$P' := xG + yH$
$t  := RandomOracle(P')$  (alternatively, the verifier picks $t$ after learning $P'$)
$x' := x + ta, y' := y + tv$
return $(P', x', y')$

$\operatorname{Verify}(P, P', x', y')$:

$t := RandomOracle(P')$
accept if $x'G + y'H = P' + tP$


Does Paillier Homomorphic Encryption Work only with numbers? Paillier homomorphic encryption enables us to combine two messages such as

$D\left(E(m_1,r_1) \cdot E(m_2,r_2) \mod n^2\right) = m_1+m_2 \mod n$

My question is what are the specification of $m_1$ and $m_2$. Should they only be numbers (e.g., integers), or could they be textual information (e.g., "Hi")?

If it allows textual input for $m_1$ and $m_2$ how would the sum $m_1+m_2$ be retrieved for $m_1 =$ "hi" and $m_2 =$ "hello" for example.

Shot answer:

It can work over a set $\mathcal{M}$ of non-numeric data, but you have to find a map from elements of $\mathcal{M}$ to $\mathbb{Z}_n$ in a way that the operations between elements of those two sets are related.

In details:

The message space of Paillier cryptosystem is the ring $\mathbb{Z}_n$ and it guarantees some homomorphic properties over this ring.

Thus, if you want to work homomorphically over any other message space $\mathcal{M}$, you have to model $\mathcal{M}$ as a ring and find an isomorphism, say $\varphi$, between $\mathcal{M}$ and $\mathbb{Z}_n$.

Given two messages $x_0$ and $x_1$ of $\mathcal{M}$, you would apply the isomorphism $\varphi$ to get  $m_0 = \varphi(x_0)$ and $m_1 = \varphi(x_1)$, then, encrypt those messages, getting $c_0 = Enc(m_0)$ and $c_1 = Enc(m_1)$. Now, if you add them, you get $c$ that decrypts to  $ m = m_0 + m_1$. Therefore, after decryption, you would just need to use the isomorphism:

$$\varphi^{-1}(m) = \varphi^{-1}(m_0 + m_1) = \varphi^{-1}(m_0) + \varphi^{-1}(m_1) = x_0 + x_1$$

as expected.

About the the particular case you pointed out: using concatenation as addition will never yield a ring isomorphic to $\mathbb{Z}_n$, because addition in $\mathbb{Z}_n$ is commutative, while concatenation is not (e.g., "hi" + "hello" is different from "hello" + "hi").


Is this protocol secure? Before anyone freaks out, this is purely speculative and I am not developing a cryptosystem!
I can't see anything wrong with this protocol, but my knowledge of cryptography is rather superficial:

Decentralized nodes need to publish a piece of information (their state, e.g. available/busy) to a central server S.

Each node has an RSA key pair.

Node A and node B have already exchanged their public keys via some secure channel outside of this protocol.

Node A sends a message to the central server S. The message contains:

A's public key
The (state, timestamp) pair
The signature for the above pair, which A calculated by using its private key

This may be the first time S sees A's public key. However, S makes sure the signature checks out, and registers A's new state provided that A's previous state is either older or non-existent.

Node B asks S for A's state. In its request to S, B identifies A by means of A's public key fingerprint (SHA-256 or whatever the best practice is), which effectively acts as node ID.

S forwards to B the state message it previously received from A. B independently checks that the signature is valid (B already had A's public key on record) and registers A's new state provided that A's previous state is either older or non-existent.

Questions:

Is there a way a malicious node can fool B by making it accept fake or outdated state messages in A's name?
Given that S has no prior knowledge of A's public key before receiving A's very first state message, is this protocol able to ensure that no malicious node can convince S to persist and propagate invalid state information in A's name or somehow enact some kind of denial of service (not by intense network activity that overloads S, but by intelligently breaking the protocol) whereby A is unable to propagate its real state?
Is there any other problem you may want to mention (leaving aside the questionable utility of the protocol)?

Thank you.

Question 2 can be easily answered. Yes, an attacker could easily overload this part of the system.

This may be the first time S sees A's public key. However, S makes sure the signature checks out, and registers A's new state provided that A's previous state is either older or non-existent.

An attacker can easily send their own public key instead of $A$'s key. Then sign with their own private key. The signature will, of course, be valid, so $S$ will accept it. If $S$ ties that key to the identifier for $A$ going forward, then future messages from the real $A$ would be blocked. Also, no $B$ will ever request a message with said key's fingerprint, so it will wait taking space in the message queue, leading to an easy way to fill the queue and stop any new messages from being processable.


What is the maximum number of shares in Shamir's Secret Sharing? I am using codahale’s Shamir's Secret Sharing implementation of Shamir's secret sharing from Github.

I am using this to generate a 32 byte random key encryption key (KEK) to encrypt a 32 byte data encryption key (DEK) which is used to encrypt the data on the Kafka producers. The DEK would be part of the payload, but the secret KEK is divided into max shares so that it can be distributed among consumers to recompute it.

What is the maximum number of shares that can be created with a threshold of 2 parts?

If I have to achieve this strategy for 1000 clients/parties, how can I do this?

The maximum number of shares in Shamir's secret sharing is limited by the size of the underlying finite field.  In particular, the maximum is one less than the number of elements in the field, since each share must be associated with a distinct element of the field, and one of the elements (usually the zero element) must be reserved for the secret being shared.

A quick Google search indicates that the com.codahale.shamir implementation always uses GF(256).  Thus, it can support at most 255 shares.

If you switched to an implementation that used, say, GF(216), then the maximum number of shares would increase to 216 − 1 = 65,535.  That should be enough for your purposes.  If not, using GF(232) would let you have up to 232 − 1 = 4,294,967,295 possible shares.

The main disadvantage of using fields larger than GF(256) = GF(28) for Shamir's secret sharing is that you may need to pad your data up to a multiple of the field size.  (With GF(256), the field elements are single bytes, so that's rarely an issue.)  In your case, however, your secrets are always 32 bytes = 256 bits long, so you can safely use GF(216), GF(232), GF(264), GF(2128) or even GF(2256) without having to worry about that.


What is the difference between CBC and GCM mode? I am trying to learn more about GCM mode and how it differs between CBC.  I already know that GCM provides a MAC which is used for message authentication.  From what I have read, and from the code snippets I've seen, GCM does an exclusive or much like CBC, but I'm not sure what the exclusive-or is against.  In CBC mode, the exclusive-or is plaintext against the previous ciphertext block, except for the first block which uses a random IV.  Does GCM do the same, or does it do the exclusive-or against something else?  If so, can someone please briefly explain how GCM uses the IV and how the exclusive-or is done.

GCM and CBC modes internally work quite differently; they both involve a block cipher and an exclusive-or, but they use them in different ways.

In CBC mode, you encrypt a block of data by taking the current plaintext block and exclusive-oring that wth the previous ciphertext block (or IV), and then sending the result of that through the block cipher; the output of the block cipher is the ciphertext block.

GCM mode provides both privacy (encryption) and integrity.  To provide encryption, GCM maintains a counter; for each block of data, it sends the current value of the counter through the block cipher.  Then, it takes the output of the block cipher, and exclusive or's that with the plaintext to form the ciphertext.

Note two key differences:

What's being exclusive-or'ed; in CBC mode, the plaintext is exclusive-or'ed with data that the attacker knows (the IV or a previous ciphertext block); hence, that in itself does not provide any inherent security (instead, we do it to minimize the chance that we send the same block twice through the block cipher).  In GCM mode, the plaintext is exclusive-or'ed with output from the block cipher; it is inherent in the security model that the attacker cannot guess that output (unless he already knows the plaintext and the ciphertext).
What's being sent through the block cipher; in CBC mode, the plaintext is sent through the block cipher (after it's been 'randomized' with an exclusive-or); in GCM mode, what's being sent through the block cipher doesn't actually depend on the data being encrypted, but instead only on internal state.

As for how GCM uses an IV (I personally consider 'nonce' a better term for what GCM uses, because that emphesizes the idea that with GCM, you cannot use the same nonce for the same key twice), well, it is used to initialize the counter.


Generating non-supersingular elliptic curves for symmetric pairings I am looking into the application of pairings in CPABE in particular. I've notice that the scheme uses a supersingular curve as the basis of the pairing. Looking through Ben Lynn's thesis for the Pairing Based Cryptography Library, there is only a single supersingular elliptic curve implemented, which is a Type A curve. However, he also mentions that type E curves provide the possibility of a symmetric pairing. I am unclear as to how this works, and how to generate such a curve that is a symmetric pairing to be used in schemes like CPABE, as the thesis only explains arbitrary Type E curves.

This case for symmetric pairing was mentioned in http://eprint.iacr.org/2001/003.

To sum the results given in that paper, you can get symmetric pairing in a few cases:

Trace 2 ordinary curves over where $p-1$ is square-free. In this case, the Tate pairing is non-degenerate for all points. Unfortunately, there is no known way to build such curves.
Trace 2 ordinary curves where $p-1$ contains a large square factor $\ell^2$. These are the Type E curves you mention, which are constructed using complex multiplication. In this case, depending on the considered parameters, there might or might not exist non-zero $\ell$-torsion points $P$ with $e(P,P)=1$. Note that, even when they exists, there are at most $2(\ell-1)$ such points.
Supersingular curve. Here $e(P,P)=1$ for $P$ defined in the basefield, but you can use a distorsion map $\psi$ and compute $e(P,\psi(P))$. This is the most frequent construction used for symmetric pairings.


Key generation times vs CPU load Does the key generation time affect the CPU load in a mobile phone, an embedded device? I am searching on Google for info, but I am not fully sure that I have concluded to something.

Any generation will consume CPU, but it is rather unlikely that you will find that it slows down a modern smart phone.
Of the known algorithms - barring post-quantum cryptography - common two-prime RSA has the most CPU intense generation technique as it needs to find two large primes. However, RSA key pairs are normally used as long term, static key pairs. So generally applications only create them once in a while. And barring client authentication, they aren't required for setting up e.g. TLS connections.
Symmetric key pair generation is limited to random number generation. As long as the secure RNG doesn't block it is extremely unlikely that you'd notice any slowdowns for normal use cases with just a few keys. And if it does block it won't affect the CPU; it will only affect the application that requires the keys. (EC)DH key pair generation is relatively fast as well.
Finally, it is always possible to botch an implementation. You could try and create a random number generator that uses a lot of CPU or memory access to retrieve enough entropy. This could e.g. be used by programmers that use an API that lacks access to the normal cryptographic operations, e.g. when using a cross compatible, high level runtime.


RSA using 2 as a public exponent I'm failing to see why 2 can never be used and what weaknesses would be associated with doing so.

There's a similar question asking why it has to be in the form of $2^n$+1 but why not $2^n$

It is not that RSA becomes insecure when used with public exponent $2$. (In fact, the Rabin Cryptosystem does exactly that.) It's that it doesn't  actually work.

The problem is that for $N = pq$ for two primes $p$ and $q$, the function $f : x \mapsto x^2 \bmod N$ is not injective. So it is impossible to invert uniquely. In fact, most elements of the function's range (the set of perfect squares) have $4$ preimages under $f$. (As pointed out by Thomas Pornin, the multiples of $p$ and $q$ have $2$, while $0$ has only one.)

We can get around this problem by choosing $p\equiv q\equiv 3 \bmod 4$ and restricting the domain to the set of quadratic residues. In this case, the function is a trapdoor permutation over the set of quadratic residues if factoring is hard.

One might note, that this is actually a better guarantee than the one we have for the RSA trapdoor permutation, where the security is not known to be implied by the hardness of factoring.


RSA: How to calculate the private exponent? I have this problem: In RSA algorithm considering $n=33$ (modulus) and public exponent $e=3$, calculate the corresponding private exponent $d$.

I know that $d = e^{-1} \pmod{\varphi(n)}$ and $\varphi(n) = (p – 1) (q – 1)$ but I don't know $p$ and $q$.

How can I do this?

If I'm understanding your question right, you want to obtain $d$ from given $n$ and $e$.

You'll have to factor $n=33=3*11$ and as $N=p*q$ you have obtained your $p=11$ and $q=3$. Now proceed as usual with calculating the inverse.

As pointed out correctly above, you can't easily generalize this approach to larger numbers as factoring $n$ will be infeasible. Now you see how to factor the number but for larger numbers even the best algorithms fail. Concerning your $e=3$ I'd consider using Coppersmith's attacks on low exponent RSA.


High Power Computing for Crypto Research Obviously, much of cryptography requires the assumption that adversaries have bounded computing power.

So, I was wondering, are there any fields in cryptographic research for which high power computing would aid researchers? Obviously, even the most advanced computers today will not give them an asymptotic advantage, but my question is:

Does crypto research require high computing power and if so specifically which field?

Insofar as cryptanalysis is considered a part of crypto research, certainly.  More computing power is always helpful for breaking ciphers, and indeed, some of the more notable massive distributed computing efforts of recent decades have involved the brute force breaking of cipher challenges such as the RSA Factoring, DES and Secret-Key Challenges.  Even with more "analytical" attacks, such as the recent MD5 collision attacks, the final stage of the attack typically still requires testing a large number of candidate values by brute force, a task made considerably easier by the availability of high computing power.

In other parts of crypto research, not so much, although some recent crypto primitives have made use of computationally intensive (pseudo-) Monte Carlo methods for choosing constants or combinations of operations to maximize desired cryptographic properties.  For example, the rotation constants of the Threefish block cipher used in the SHA-3 finalist hash function Skein were selected using a genetic algorithm.


Textbook RSA with exponent e=3 I remember $e=3$ is a bad choice for textbook RSA. But I can't really recall why. What happens if I choose $e=3$? Can I retrieve the message by simply calculating $\sqrt[3]{c}$? Why can't I do that with bigger $e$s? Is it possible to retrieve $d$, $p$ or $q$?

I remember that we had something with the Chinese Remainder Theorem (CRT), but when I look at it now, I does not seem to make any sense.

I'm thankful for fast responses!

What happens if I choose $e=3$? Can I retrieve the message by simply calculating $\sqrt[3]{c}$?

Yes, if the plaintext message is smaller than $\sqrt[3]{N}$, then yes, a simple computation of $\sqrt[3]{C}$ will recover the original message.

  Why can't I do that with bigger $e$'s?

Actually, you could... as long as the plaintext message is smaller than $\sqrt[e]{N}$.  However, if you actually consider that for, say, $e=65537$, well, that value turns out (for any sane value of $N$) to be less than 2; hence that could be used only if the plaintext message was either 0 or 1 (and if that's the case, well, the problem would be pretty easy anyways).

  Is it possible to retrieve $d$, $p$ or $q$?

No, it's not.  If it were, well, that'd give an easy way to factor the modulus (!), even if we were using RSA properly.  All the attacker would need to do is take the modulus, and pretend that he was using textbook RSA and $e=3$; he would generate messages his own of his own choosing, encrypt those messages (using plaintext RSA and an $e=3$), and use the technique to recover $d$, $p$ or $q$.  Any of the three is enough to factor the modulus.


diffie hellman digital signatures vs MACs I have the following homework question that im not sure about.

Alice and bob are going to use the diffie-hellman key agreement protocol to agree on a key for use in AES. Explain briefly why they would need to use digital signatures and why they cannot use Message Authentication Codes (MACs) instead.

I find the question a bit hard to understand, im aware that MACs require a shared secret key to compute the MAC so this would have to be done first but am not sure why digital signatures need to be used ?

The homework task is making an implicit assumption:

They don't have a common shared secret.

That's implicated by the fact that they do a DH key exchange and nothing else to exchange the key. A common shared secret would offer muc more possibilities, e.g. combine a DH key exchange with the shared secret as input to a KDF.

You realized yourself that a shared secret is required for MAC. So what protects the DH  key exchange from man-in-the-middle attacks? Because (not-authenticated) DH key exchange is vulnerable to that.