Building a stream-cipher out of a hash function? I've already read this:
Is it feasible to build a stream cipher from a cryptographic hash function?

However, my proposed construction differs…

Suppose the hash generates N bits. These bits are split into two parts:

$S$ bits are kept secret,
$X$ bits are used for the encryption, xor'ing the bytes the usual way
$S + X = N$
$H_i^S$ is the $S$ bits of the current hash $H_i$, in iteration $i$
$H_i^X$ is the $X$ bits of the same hash value
$P_i^X$ is $X$ bits of buffered plaintext in iteration $i$
$C_i^X$ is $X$ bits of ciphertext in iteration $i$

The algorithm:

generate a random key $K$ that will be shared between the peers
$i=0$, generate $H_0 = hash(K)$
$C_i^X = P_i^X \oplus H_i^X$
$H_{i+1} = hash(H_i^S|P_i^X)$
$i=i+1$, goto 3.

Analysis:

Even if the attacker has the plaintext and thus can retrieve $H_0^X$, say in the first round, since $H_0^S$ is unknown, he will not be able to calculate $H_1$. If $S$ is sufficiently large, guessing/brute forcing will be unfeasible. On the receiver side, if the stream was tampered, the bytes decoded in that round will have the same bit errors, but then in the next round, the hash's avalanche effect will kick in, making decoding bytes in the next rounds impossible.

Note:

The bytes used for xor'ing could come directly from the hash's state (keccak comes to mind), and the original bytes could go there, too, performing the specific bit mixing operations of the hash after each cipher round.

Eg:

For SHA256, 128 bits could be used for $S$, and 128 bits for $X$. Or, 64 bits for $S$ and 192 bits for $X$. The later would result in less processing per byte, with somewhat less security.

What is your take on this?

As I understand the construction (and it isn't well written), it looks weak; it is likely to leak information given real plaintexts.

The reason that I say it isn't well written is that it's not stated what you use to exclusive-or the plaintext bytes to generate the ciphertext-bytes; is it the hash you generated in step 2, or is it the "most recent hash" (the one in step 2 for the first iteration, or the one is step 4 for the next -- and step 5 really should be "goto step 3").

Assuming that you meant the latter, well, this appears to be 'Plaintext Feedback Mode':

In step 3, "the original bytes are buffered in $X'$"; that is, $X'$ is set to a segment of plaintext bytes.
In step 4, you construct the $H_1 = hash(S | X' )$, where $S$ is a secret key (constant for a specific stream), and $X'$ are plaintext bytes you stored in step 3.
In step 3, you compute $Ciphertext = Plaintext \oplus Trim(H_1)$. where $Trim$ is the first $X$ bits of $H_1$

The problem here is that real plaintext often have repeats; it is not unusual to see occurances of the exact same 16 characters repeated -- this is precisely why ECB mode is considered insecure.  However, when this happens for your construction, then $X'$ will be repeated, and so will $H_1$; the 16 bytes immediately following that will have the exact same exclusive-or (and this can be detected and exploited).

The obvious fix would be to change this into Ciphertext Feedback Mode; all you would need to do is set $X'$ to the ciphertext bytes, not the original plaintext bytes.

This still isn't a great encryption method (it's slow, and needs an integrity check to be secure); however if all you have is a hash function, it could be made to work.


Why does decryption fail after modification of the ciphertext for RSA with OAEP padding I have ciphertext which was encrypted using RSA with "OAEPWithMD5AndMGF1Padding" - i.e. OAEP using MD5 for the Mask Generation Function.

I understand the general idea of how the randomized padding works, but I'm not completely sure why the decryption process completely fails if I change one byte of the ciphertext. How does the algorithm spot that there were changes and why does it not return some random plain text?

For demonstration purposes, here is my code in Java:

        int              ilgis = 0;
        BigInteger       ct = new BigInteger("2D9487AA09DBE708084A97CC466A7CB2CAE2E00100D11FF8C79CF0568858F91E2A5CFC8FD3007F530FC12695870F", 16);
        byte[]           inputBytes = ct.toByteArray();
        SecureRandom     random = new SecureRandom();
        Cipher           cipher = Cipher.getInstance("RSA/None/OAEPWithMD5AndMGF1Padding", "BC");
        KeyFactory       keyFactory = KeyFactory.getInstance("RSA", "BC");

        RSAPublicKeySpec pubKeySpec = new RSAPublicKeySpec(
                new BigInteger("00A17DE2DBF5C2C68AF8EA044547670D3C8E2F4F9693804B7EC6FBCA5F09D0ABF85A73DB4DFC8FFF0EADF9B040375D", 16),
                new BigInteger("03", 16));
        RSAPrivateKeySpec privKeySpec = new RSAPrivateKeySpec(
                new BigInteger("00A17DE2DBF5C2C68AF8EA044547670D3C8E2F4F9693804B7EC6FBCA5F09D0ABF85A73DB4DFC8FFF0EADF9B040375D", 16),
                new BigInteger("6BA941E7F92C845CA5F1582E2F9A08D30974DFB9B7AADBEF595662C4E29DD76FDEDF48F5CBBD4ED2E961355F2013", 16));

        RSAPublicKey pubKey = (RSAPublicKey)keyFactory.generatePublic(pubKeySpec);
        RSAPrivateKey privKey = (RSAPrivateKey)keyFactory.generatePrivate(privKeySpec);

        System.out.println("Ciphertext: " + toHex(inputBytes, inputBytes.length));
        cipher.init(Cipher.DECRYPT_MODE, privKey, random);
        byte[] plainText = new byte[cipher.getOutputSize(inputBytes.length)];

        ilgis += cipher.doFinal(inputBytes, 0, inputBytes.length, plainText, 0);
        System.out.println("Plain text : " + toHex(plainText, ilgis) + " length: " + ilgis);
```

Let's look at the decryption part of RFC 8017 for OAEP. Let's only look at step 3, as step 1 is called length checking, and step 2 is the step to perform modular exponentiation and integer to octet string conversion (or, rather interpretation). Step 1 can fail but is out of scope for this as it acts on the ciphertext itself, step 2 cannot fail, even though the result may not make sense.

So here is step 3. Note that EM is the message after modular exponentiation with the private exponent, i.e. the input that should be generated after step 3 in the encryption phase.

3.  EME-OAEP decoding:

    a.  If the label L is not provided, let L be the empty string.
        Let lHash = Hash(L), an octet string of length hLen (see
        the note in Section 7.1.1).

Label L is a configuration option and therefore doesn't have to do with error checking. So we can know lHash regardless of any calculations performed during decryption.

    b.  Separate the encoded message EM into a single octet Y, an
        octet string maskedSeed of length hLen, and an octet
        string maskedDB of length k - hLen - 1 as

           EM = Y || maskedSeed || maskedDB.

This just splits the message EM without regard of the value of the octets.

    c.  Let seedMask = MGF(maskedDB, hLen).

Some function to calculate the seedMask, will finish without regard of the input...

    d.  Let seed = maskedSeed \xor seedMask.

Some function to calculate the seed, will finish without regard of the input...

    e.  Let dbMask = MGF(seed, k - hLen - 1).

Some function to calculate the dbMask, will finish without regard of the input...

    f.  Let DB = maskedDB \xor dbMask.

Some function to calculate the DB, will finish without regard of the input...

Now this is interesting, since we now have seed, dbMask but more importantly DB, which all have been defined in the encryption function as well. In other words, this whole process so far reversed the calculations in the padding process. If the input is garbage, then DB won't match the DB during encryption, but the above calculations will conclude in some result.

    g.  Separate DB into an octet string lHash' of length hLen, a
        (possibly empty) padding string PS consisting of octets
        with hexadecimal value 0x00, and a message M as

           DB = lHash' || PS || 0x01 || M.

Splitting DB of course is still performed without evaluating the values in the octets.

        If there is no octet with hexadecimal value 0x01 to
        separate PS from M, if lHash does not equal lHash', or if
        Y is nonzero, output "decryption error" and stop.  (See
        the note below.)

Finally, after all these calculations, we do some validation, before actually outputting M, which is the encrypted plaintext message. This is deliberately placed as final check, because we could have checked Y back at step 3b where it was the direct result of the modular exponentiation. To know why, see the section below.

So first we have to check the initial octet is 00 (although we may want to postpone that, see the section below).

Then most importantly we check if lHash' matches the hash over the label l, which is a configuration option so known beforehand. Generally, this label l cannot even be configured in implementations of RSA-OAEP so we can usually assume that lHash is simply the hash over an empty (zero octet) message, i.e. a constant specific to the configured hash function.

This is the most important step because it will check a full hash output size (in your case 16 octets for MD5) for correctness. And these 16 octets depend on all the other octets due to the masking process. Well, all other octets apart from Y that was already validated anyway. So there is negligible chance that the bits of this constant value are correct if any bits of EM have been altered.

Then we go over PS, expecting only 00 octets until the next octet which should have value 01 (if you look at it like that you don't have to check the 00 octets, just check if the first non-zero octet is 01). Finally we have M which can be anything so there is no possibility to check.

The chance that octet Y is correct and / or that the PS padding (which may be 0 bytes) and 01 byte is correct if incorrect ciphertext or key is used is around 1 in 192 * 256, depending somewhat on the modulus value. Although that chance is not very high, it is far from being negligibly small. So comparing the lHash and lHash' values is the comparison that matters.

Now for completeness, the note:

Note: Care must be taken to ensure that an opponent cannot
distinguish the different error conditions in Step 3.g, whether by
error message or timing, and, more generally, that an opponent
cannot learn partial information about the encoded message EM.
Otherwise, an opponent may be able to obtain useful information
about the decryption of the ciphertext C, leading to a chosen-
ciphertext attack such as the one observed by Manger [MANGER].

OK, so that's just about avoiding side channel attacks on the final validation.

It can probably be implemented very easily by validating lHash in a time-constant manner first. If that step hash negligible chance of completing if EM has an incorrect value, then obviously the Y must have value 00 and the separator be present and correct if it does complete.

If you want to know even more about OAEP padding validation and why it is secure then you probably have to consult the security proofs that have been presented for RSA-OAEP.


Why was the term "discrete" used in discrete logarithm? Is there anything especially "discrete" about a discrete logarithm? This is not a question of what is a discrete logarithm or why the discrete logarithm problem is an "intractable problem" given certain circumstances. I'm just trying to determine if there's some additional meaning to the term "discrete" as it's used in name discrete logarithm?

The definition of "discrete" is "individually separate and distinct". Could it be that the term "discrete" is a reference to the least non-negative residues of a modulus or the order of points for a particular cyclic group on an elliptic curve?

The word discrete is used as an antonym of 'continuous', that is, it is the normal logarithmic problem, just over a discrete group.

The standard logarithmic problem is over the infinite group $\mathbb{R}^*$, this group is called 'continuous', because for any element $x$, there are other elements that are arbitrarily close to it.

The discrete logarithmic problem is over a finite group (for example, $\mathbb{Z}_p^*$); in contrast to $\mathbb{R}^*$, we don't have group elements arbitrarily close together; we call this type of group 'discrete'.


Practical uses of Manipulation Detection Code (MDC) and IGE I've just skimmed over most of the paper "On Message Integrity in Symmetric Encryption". I've included (the last) part of the abstract below:

  We show that generic compositions of confidentiality-secure encryption
  schemes with Manipulation Detection Code (MDC) functions for
  authenticated encryption are, in general, weaker than
  "encrypt-than-authenticate" compositions using strong Message
  Authentication Code [edit: (MAC)] schemes. Since the former
  compositions lead, in general, to authenticated encryption schemes
  that are faster, more power-efficient, and simpler implementations
  than the latter, we conclude that both types of composition are
  necessary in practice for different application environments.

Now despite this claim I cannot find any protocols that e.g. use the Infinite Garble Extension (IGE) or double IGE (biIGE) modes of encryption.

Furthermore I found the following rather alarming notes (that are more alarming since the aforementioned paper seems to be of a later date than the attack described in the last link):

http://www.metzdowd.com/pipermail/cryptography/2006-September/011423.html

https://groups.google.com/forum/#!topic/sci.crypt/4bkzm_n7UGA

So my two related questions are:

Can there be any practical use of MDCs in general?
Can there be any  practical use of IGE or biIGE mode encryption?

Don't believe every claim ever made in any paper ever written, particularly when the paper provides little or no justification for the claim; not everything you read reflects the cryptographic consensus.  This is particularly true for a paper written in 2002, which is a time our understanding of authenticated encryption and security engineering was still in flux.

Today, the conventional wisdom is: just use authenticated encryption, such as GCM, EAX, etc.  For most purposes, there's really no compelling reason to ever use a special MDC-based scheme.

Can there ever be any practical use to MDCs?  I don't know; that's too broad a question to answer.  I don't know if anyone can ever convincingly tell you "no, they will never ever be useful, I absolutely guarantee it".  But in general, I don't see much use to MDC-based schemes.  I find it hard to imagine practical situations where I'd want to use a special MDC-based scheme.  Standard authenticated encryption schemes are good enough.

I don't recommend use of IGE nor biIGE modes: if you have to ask, you shouldn't be using them.  (There may be some very special situations where one might use them -- see, e.g., this use of biIGE in Minx, a system for anonymous communication -- but those are the exception instead of the norm.)
For almost all ordinary real-world situations that you're likely to encounter, an authenticated encryption scheme is going to be adequate.  Researchers have invented tons of clever ideas ever invented, but that doesn't mean they're all useful; in practice, a handful of standard primitives will cover you for 99% of real-world situations.


How to efficiently generate a stream of independent, but biased random bits? Usually, in cryptography, one is interested in debiasing a stream of independent (true) random bits, and several algorithms exist to do this. What about the converse? Let's assume I have a stream of independent and unbiased random bits at my disposal, and that I would like to generate a stream of statistically independent bits, but where $\Pr[B=0] = \frac{1}{5}$, say. How do I do this without sacrificing too much entropy from the initial source? A common algorithm for this precise case would consist in drawing $3$ bits, and interpret them as a number $0 \leq a \leq 7$. If $a=0$, then output $0$, else if $a < 5$, then output $1$, else output nothing. The problem is that I will sacrifice a lot of entropy: with probability $\frac{1}{4}$, I discard 3 bits, and with probability $\frac{3}{4}$, I transform 3 bits of entropy into a single one. Are you aware of a less entropy-hungry method?

If you want an answer that is maximally efficient in consuming a stream of random bits, then you need a decoder for arithmetic encoding.  However if you're using a moderately fast CSPRNG, why would you sacrifice extra clock cycles to squeeze all the biased bits you can from each unbiased bit?


Can AES-GCM be broken if initialisation vector is known? We are using AES encryption in GCM block mode in order to encrypt a number of different kinds of data at rest on a mobile device - Android.

The key used for encryption is stored in the protected key-store offered Android so I am assuming that it is pretty robustly stored. However, we are using the same nonce/IV to encrypt different data. The nonce/IV is stored in shared preferences without any encryption. So I am assuming that it is not secure given a malicious app on a rooted android device can get into the shared preferences or another app.

What am I trying to understand is - if someone indeed gets hold of the plain-text nonce/IV and a number of different encrypted messages (which are encrypted using the same key) can they be able to decrypt the messages successfully?

We have proposed to make this better by using a different nonce for encrypting each message. However, I am not sure if this will still prevent someone from decrypting the message when they can get hold of the plain-text nonce, even when there is only one message that is encrypted with that nonce.

Here is the relevant piece of code

public synchronized String encrypt(String input) throws SecurityException {
    try {
        Cipher c = getCipher(Cipher.ENCRYPT_MODE);
        byte[] encodedBytes = c.doFinal(input.getBytes("UTF-8"));
        return Base64.encodeToString(encodedBytes, Base64.DEFAULT);
    } catch (Exception e) {
        throw new SecurityException(e);
} }
public synchronized String decrypt(String encrypted) throws SecurityException {
    try {
        Cipher c = getCipher(Cipher.DECRYPT_MODE);
        byte[] decodedValue = Base64.decode(encrypted.getBytes("UTF-8"), Base64.DEFAULT);
        byte[] decryptedVal = c.doFinal(decodedValue);
        return new String(decryptedVal);
    } catch (Exception e) {
        throw new SecurityException(e);

} }

However, we are using the same nonce/IV to encrypt different data.

No, don't do that

  if someone indeed gets hold of the plain-text nonce/IV and a number of different encrypted messages (which are encrypted using the same key) can they be able to decrypt the messages successfully?

Actually, it doesn't matter if they know the nonce; if they get two messages encrypted with the same nonce, then they can compute the xor of the two plaintexts.  Depending on the nature of the plaintexts, that is often enough for an attacker to deduce the contents of the original plaintexts.  Given the attacker more than two messages from the same nonce, well, that just makes it easier for him.

In addition, knowing two messages with the same nonce, then can deduce the internal value $H$ to GCM; that'll allow him to generate encrypted messages of his own that would pass validation (hence the authentication piece of GCM goes away).

  We have proposed to make this better by using a different nonce for encrypting each message. However, I am not sure if this will still prevent someone from decrypting the message when they can get hold of the plain-text nonce, even when there is only one message that is encrypted with that nonce.

That is absolutely better.  It doesn't matter in the slightest if the attacker knows the nonce; that knowledge doesn't allow him to deduce anything about the plaintext.  In practice, we often just prepend the nonce to the ciphertext, as that's the easiest way to get the nonce to the decryptor.  What matters greatly is that you never use the same nonce twice.


Perfect Secrecy, two Definitions I'm reading the proof of the implication "Def 2.1 $\Rightarrow$ Def 2.4" in these slides about Adversarial Indistinguishability and Perfectly-Secret Encryption. I have a doubt in the slide 10. Here it says:

  Construct an adversary $A$ who outputs $m_0$, $m_1$ in the ﬁrst step of
   $\mathsf{PRIV_{EAV}}(\Pi,A,n)$. Then if $A$ receives any ciphertext
  $c' \neq \tilde{c}$ it outputs a random bit $b_0$; if it receives
  the ciphertext $\tilde{c}$, it outputs $b_0 = 0$.

How is $A$ able to "receive any ciphertext $c'$". Perhaps the adversary not receives only the ciphertext $Enc(m_b)$?

The adversary $\mathcal A$ is an entity (think of a computer program) designed to participate in the experiment $\operatorname{PrivK}^{\text{eav}}_{A,\Pi}$.

So the adversary produces two messages, then is given the encryption of one of them, and has to guess which one it was.

Of course, you can give the adversary other "ciphertexts" too, but this wouldn't be the same experiment, and the results of this thus don't matter for the experiment (they might be interesting in other experiments, though).

The proof does only have to consider the behavior of the adversary in the experiment, not in other cases.


What's the best way to pad a message? Currently my padding is adding a string of random characters

$ l(N)/3 - (l(M) + 1) $

Long and just adding it to the messages, is this sufficient?

$l(x)$ = length of a variable

As you are asking about the "best" way to pad, the answer is OAEP for Encryption and PSS for signatures. They are well understood, widely used, and considered secure. They also give you some neat additional properties that your system does not achieve, like preventing partial decryptions and making the message "look random" in the case of OAEP.

If you are actually planning to implement your padding scheme in a production system, the short version is: please don't. Instead, use a standard padding mode like OAEP and an implementation that is used by many people and well understood, and you will avoid a lot of pain and potential security holes.

If this is just a question from curiosity, my questions to you would be:

As @Gilles asked, do you want to encrypt or sign?
As @Maarten Bodewes asked, how did you arrive at this scheme? Where do the magic values come from?
How do you detect where the message ends and the padding starts, so you can distinguish between the two after decryption / when verifying the signature?
How do you make sure that the padding is valid after decryption? Padding should be predictable, as that can give you another indicator if the message has been tampered with.

For more information on padding schemes, see, for example, this question and answer. Also, this question has some additional pointers on how to go about designing and publishing a cipher, which in part apply to the case of designing a padding scheme.


Can two elliptic curve point multiplications have a same resulted point? Is it possible for $aG \equiv bG$, with $a, b$ are scalars and $G$ is a point on the curve?

Yes, it is possible, but only if $a, b$ differ by a multiple of the order of the point $G$.

When we perform elliptic curve cryptography, we select a curve and a point $G$ where the order is a large prime (typically, circa the field size).  When we select a random multiplier, we most often select a random one uniformly between 1 and $\operatorname{order}(G)-1$; if both $a, b$ were selected that way, then the only way for $aG = bG$ would be if $a=b$


What is mac-and-continue? I've seen the term mentioned in a paper by the Keccak team here, and by Adam Langley here when talking about properly authenticating stream ciphers.

What does it actually mean, and how does it work? What are its advantages in the case of encrypting and authenticating streams?

It looks like the first paper you linked hints at an explanation.

From what I can tell the idea is the same as with "intermediate tags", that is you have an instance of your cipher and you process all the data up to some point, then create a MAC-tag, insert it into the data stream for later verification and continue with the very same instance to process more data. The paper says:

  With appropriate domain-separating padding the security proofs allow
  the sponge states to be used for any number of consecutive
  authenticated messages (“MAC-and-Continue”) without the need for
  sequence numbers, and re-keying.

So why should one want to do this?

TL;DR: It's a "nice feature" to the programmer and data structure designer.

Strictly speaking you cannot be sure of the security of a decrypted message until you have fully verified the integrity of the entire message. That means if your message is 1MB you have to authenticate and decrypt the entire 1MB message before your crypto implementation should pass it on to the application. And with usual modes the tag marks the end of the message meaning you have to potentially re-initialize instances and worry about what the new nonce shall be. "Mac-and-Continue" simplifies that in that you can just insert a tag pretty much anywhere in the 1MB chunk and then all the data up to that tag is authenticated, meaning it can be handed to the application much sooner than expected. This helps to reduce buffer sizes, reduce latency (as you have less to process before being able to pass it on) and it eliminates the worries you would have if you had to manually design a mode that has chunks (which means defining nonces, protecting against re-ordering attacks and re-initializing your mode object).


Brute forcing CRC-32 I'm working on a cryptosystem which uses IDEA.  The designer made the mistake of including a CRC-32B hash of the password unencrypted in the header, so that the system can quickly reject bad passwords.  Of course, that opens it up to the obvious attack of brute forcing CRC32 over potential passwords until the right one is found.  Which is what I'm trying to do.

Questions:

Is the best way to do this simply to do an exhaustive search of the password space? It would seem to me that since CRC32(x) is related to x in manifest ways (eg XOR is preserved), it might be possible to do a construction where we actively direct the search in the right direction.  I don't know enough about CRC32, but it would seem to me something like this is possible.

Of course, it's not enough to find a string with the same CRC32.  It has to be the real password used, otherwise the IDEA decrypt will be gibberish.  So this might throw some water on this method.  But, regardless, I'd like to know more about it.  What do you say?
Failing that, I'll need fast code to brute force the CRC32B.  What is the fastest code? My plan is to brute force candidates via CRC32, then try to decrypt via IDEA and measure the entropy to filter out all of the false positives (1 in 4 billion) that will still match CRC.

Assuming the n-bit CRC of an unknown bit string b is known, one can constructively rebuild any consecutive n bits of b from the rest of the bit string (and the definition of the CRC). Indeed, in the case described, that speeds up password search considerably. One can compute the last 32 bits of the password (likely, 4 characters) from the beginning of the password. If the password is constrained to characters in [20h..7Fh], that will further remove $49/50$ of the candidates.

Many CRCs found in practice (including 32-bit CRC CCITT) are not "XOR-preserving" in the sense $CRC(x \oplus y) = CRC(x) \oplus CRC(y)$.
However it allways holds that $CRC(x \oplus y \oplus z) = CRC(x) \oplus CRC(y) \oplus CRC(z)$ for any $x$, $y$, $z$ of identical length (including with $z$ all-zero); that (and a little linear algebra) is enough to organize the computation. At the end of the day, with $n=32$, one can compute the last 4 bytes by XOR-ing the values found in precomputed tables (one table for each preceding byte, with each table $256·32$ bits).


Why $f(x)=x^e$ is a bijection i.f.f $e\in{\mathbf{Z^*_{\phi(N)}}}$? I understand that if $e\in{\mathbf{Z^*_{\phi(N)}}}$ then $\gcd(e,\phi(N))=1$
and if $e\not\in{\mathbf{Z^*_{\phi(N)}}}$ than $\gcd(e,\phi(N))\neq{}1$.

But I couldn't figure out why this implies bijection of $f(x)=x^e$.

I also tried to see examples but that didn't help me to explain the phenomenon.

The correct form is:
The integer $a \mod Z_n$ has multiplicative inverse iff $gcd(n,a)=1$

Here, you are working on exponents, so you must consider the modulo as $\phi(n)$ not $n$.

Therefore, here you can find the inverse of $e$ iff $gcd(e, \phi(e))=1$. This guarantees that you be able to find the inverse of $e$ using extended Euclidean algorithm.


How fast is hashing and is it always regarded as an O(1) operation? I've wondered how hashing can be such a fast operation. It's so fast that nobody talks about it in terms of performance and complexity.
I know that in terms of big O notation, you can drop all the constants and just speak in terms of the variables. I know that in hash lookup, if you know the key, it is O(1). This makes sense to me. What didn't make sense was to get the message digest, you have to actually run the hash function, and nobody talks about this. What if the file or document is super large, the complete works of William Shakespeare. Does that take 1000x as long to hash as a one page document? I assume the hash functions have to run through every single bit of the data one by one, so doesn't that factor into time complexity? Maybe it doesn't have to run through every bit. Maybe it runs through every 8 bits or 32 bits or whatever a word size is in a system. I know bitwise operations are significantly faster and I know the SHA algorithms make use of them, but still, when people say hashtable lookup is O(1), I'm amazed at how the hashing itself can always be considered as nothing, regardless of file size, as it seems that the entire data would have to be traversed through.

You are right. A hash function applied to $n$ bits of input will typically take $O(n)$ work to evaluate. It is important for a hash function to use every single bit of input as part of the calculation or collisions become very, very easy.
The "hashing takes time $O(1)$" is true for fixed/bounded length inputs, but as you say this is misleading.


Bilinear Map over group of unknown order Is it possible to build a bilinear map where the underlying group is of unknown order?

To maintain context, the original question appears below.
As per poncho's excellent answer, my original idea is infeasible:
Is it possible to build a bilinear map where the underlying group is an RSA group?
I.e.
$e: \mathbb{Z}_N \times \mathbb{Z}_N \rightarrow \mathbb{Z}_N$ where N is an RSA modulo?
Alternatively, a bilinear map where the underlying group is of unknown order?

Is it possible to build a bilinear map where the underlying group is an RSA group?

I.e. $e: \mathbb{Z}_N \times \mathbb{Z}_N \rightarrow \mathbb{Z}_N$ where N is an RSA modulo?

If we can build a nontrivial bilinear map over arbitrary RSA groups, then we can solve the DDH problem over a prime field.  Here's how:

The DDH problem is: given $g, p, g^a \bmod p, g^b \bmod p, g^c \bmod p$, is $g^{ab} \bmod p = g^c \bmod p$ ?

To solve this, we select a prime $q$ and compute $n = pq$, and then construct a bilinear map $e$ over that ring.

Then, you find the value $h$ with $h \equiv g \pmod p$ and $h \equiv 1 \pmod q$; this is a simple application of CRT

Then, the same process allows you to find $h^a$ from $g^a$ (as $h^a \equiv g^a \pmod p$ and $h^a \equiv 1 \pmod q$, and similarly $h^b$ and $h^c$

Then, you compute both $e(h^a, h^b) = e(h, h)^{ab}$ and $e(h, h^c) = e(h, h)^c$; if they're the same, then $ab \equiv c \pmod{p-1}$

We do not know how to solve the DDH problem over arbitrary prime fields, hence there is no known way to generate nontrivial bilinear maps over RSA groups.


Question on Waters IBE I'm reading “Efficient Identity-Based Encryption Without Random Oracles” by Brent Waters.

In Page 9, I don't know how $$\mathcal{P}_{BDH}=\Pr[\beta'=1]=\Pr[\beta'=1|\textbf{abort}]\Pr[\textbf{abort}]+\Pr[\beta'=1|\overline{\textbf{abort}}]\Pr[\overline{\textbf{abort}}]$$

becomes
$$\mathcal{P}_{BDH}=\frac{1}{2}+\frac{1}{2}(\Pr[\overline{\textbf{abort}}|\gamma'=\gamma]\Pr[\gamma'=\gamma]-\Pr[\overline{\textbf{abort}}|\gamma'\neq\gamma]\Pr[\gamma'\neq\gamma])$$
$$$$$$$$
Since

$$\Pr[\beta'=1|\textbf{abort}]=\frac{1}{2},$$

$$\mathcal{P}_{BDH}=\frac{1}{2}\Pr[\textbf{abort}]+\Pr[\beta'=1|\overline{\textbf{abort}}]\Pr[\overline{\textbf{abort}}]$$
I can't not follow after that.$$$$
Please help me to understand what Waters said.

It's been a while since I've read this paper, and I remember having a lot of trouble with this derivation. I'm sure there is an easy way to see it, but I don't see it, so I'll just brute force through with the algabra.

First, some context:

  When the simulator is given a random element as the last term in the tuple the simulator will either abort (and guess $\beta' = 1$ with probability $\frac12$) or guess $\beta' = 1$ [exactly] when the adversary is correct in guessing $\gamma$. However, the $\gamma$ will be completely hidden from the adversary in this case so the adversary will be correct with probability $\frac12$.

I have added the word exactly because actually if the simulator doesn't abort, then $\beta' = 1$ iff $\gamma = \gamma'$. This is seen in the simulator description at the end of section 5.1.

We'll start from your simplified expression for $\mathcal{P}_{BDH}$. We then have
$$\begin{align*}
\mathcal{P}_{BDH}
  &= \frac12\Pr[\textbf{abort}] + \Pr[\beta' = 1|\overline{\textbf{abort}}]\Pr[\overline{\textbf{abort}}] \\
  &= \frac12 + \left(\Pr[\beta' = 1|\overline{\textbf{abort}}] - \frac12\right)\Pr[\overline{\textbf{abort}}]
\end{align*}$$

For the non-aborting case, we know that $\beta' = 1$ if $\gamma = \gamma'$. So if split the case $\overline{\textbf{abort}}$ into two, $(\overline{\textbf{abort}} \land \gamma = \gamma')$ and $(\overline{\textbf{abort}} \land \gamma \neq \gamma')$, we get

$$\begin{align*}
\Pr[\overline{\textbf{abort}}]
  &= \Pr[\overline{\textbf{abort}}] \\
  &= (\Pr[\overline{\textbf{abort}}|\gamma = \gamma']\Pr[\gamma = \gamma']
  + \Pr[\overline{\textbf{abort}}|\gamma\neq\gamma']\Pr[\gamma\neq\gamma'])
\end{align*}$$

Since the adversary has no knowledge of $\gamma$, we may set $\Pr[\gamma=\gamma'] = \frac12 +\epsilon$ (and therefore $\Pr[\gamma\neq\gamma'] = \frac12-\epsilon$). This gets us
$$ \Pr[\textbf{abort}] = \Pr[\overline{\textbf{abort}}|\gamma = \gamma'](\frac12 + \epsilon)
  + \Pr[\overline{\textbf{abort}}|\gamma \neq \gamma'](\frac12 - \epsilon)$$
so our total probability is
$$ \frac12 + \left(\Pr[\beta' = 1|\overline{\textbf{abort}}] - \frac12\right)\left(\Pr[\overline{\textbf{abort}}|\gamma = \gamma'](\frac12 + \epsilon)
  + \Pr[\overline{\textbf{abort}}|\gamma \neq \gamma'](\frac12 - \epsilon)\right)$$

So far so good. Here's where the silly algebra comes in: let's rename these big terms as
$$ \frac12 + (A - \frac12)(B + C) $$
and notice that the desired form, with these new names, is
$$ \frac12 + \frac12(B - C) $$

Next, notice that
$$ A = \Pr[\beta' = 1|\overline{\textbf{abort}}]
  = \frac{\Pr[\beta' = 1 \land \overline{\textbf{abort}}]}{\Pr[\overline{\textbf{abort}}]} = \frac{B}{B + C}$$
so that
$$\begin{align*}
(A - \frac12)(B + C)
  &= \left(\frac{B}{B + C} - \frac12\right)(B + C) \\
  &= \left(\frac{2B - B - C}{2B + 2C}\right)(B + C) \\
  &= \frac12(B - C)
\end{align*}$$
and there you go!


Identity Based Encryption: Known Random Value Let's consider a situation whereby:

  Alice generates a ciphertext c from a message m using Bob’s ID.

  An attacker Carol can get c from the open channel. She knows that c is
  generated by using Bob’s ID but she does not know Bob’s secret key.

  On the other side, Carol is able to know the random number r that
  Alice has used in the encryption process

Also, it is given that the identity-based decryption formula is as such:

  Encrpytion: $c = (u,v) = (\mathtt{g}^{r}, m \oplus {H({T}_{id}^r)})$

  Decryption: $m = v \oplus H(e(\mathtt{d}_{id}, u))$

This is also the standard IBE Bilinear Pairing.

I also managed to deduce this equation below from deriving the decryption algorithm.

  $m = v \oplus H(\mathtt{{\mathtt{T}_{id}}}^{r})$

Now consider this question:

  Can Carol compute the plaintext message $m$ by just knowing $r$ but not Bob’s secret key?

My answer: It's not possible for Carol to compute $m$ just by knowing $r$ because she still has to solve the discrete log problem in the last equation given which is considered hard.

However, I am unsure whether this is right or wrong.

Edit:

  Formula for ${T}_{id}= e({Q}_{id},{K})$, where K is the master public key (${g}^{s}$), and ${Q}_{id}$ is the hash of the user id

  Formula for ${d}_{id} = ({Q}_{id})^s$, where s is the master secret key

Thanks. I guess $K=g^s$. It seems trivial if Carol knows the random integer $r$ then she can learn the message. As you mentioned everybody could compute $T_{id}$ because both $Q_{id}$ and $K$ are public amongst the network. Since Carol knows $r$ then she can compute $Z=T_{id}^r$ and hash of this result!
To learn the message, she has to calculate,

  $$m=v \oplus H(Z)=m \oplus H(T_{id}^r) \oplus H(T_{id}^r)=m \oplus (H(T_{id}^r)\oplus H(T_{id}^r))=m \oplus 0=m$$

In general, Carol does not need to know the master secret key $s$ to read the message. The Encryption phase is randomized by the integer $r$ and for a Chosen Ciphertext Carol can learn the message. While we know she can not compromise the forward and backward secrecy of the scheme because the Discrete Logarithm is hard and the random integer for next ciphertext will be sampled, independently.


When it is safe to reuse IV? (or not using at all) This is my case:

I don't have padding oracle (the server provide the data and users never able to execute the encryption function),
I never encoding the same text twice.
The text is always short - 128 bytes.
I store the encrypted text in the database.
I never send the decrypted text to any user.

What I want:

If one of the users have a copy of the database, he will never be able to decrypt the text.
If an attacker successfully accesses to one the text decrypted, it's a problem exactly like he has access to all the text decrypted.

In my case, is it safe to use AES-CTR with fixed IV (or not use IV at all).

In other words: If an attacker doesn't have any decrypted text, he has ONLY a database of unique 100k+ encrypted texts that use the same key and IV. Will he be able to break the encryption?

Please don't tell me about best practices, and Do not invent the wheel. I'm here to learn, and I want to know if there is REAL problem with using fixed IV or not use at all. I found that it is simpler to store in the database only one value, without saving IV for each value.

It is safe to reuse AES-CTR IV (or not use one at all) in some theoretical situations, including when all except one plaintext are uniformly random and independently chosen. However, that's unsafe in most practical situations, including when an adversary knows the general nature of the plaintext (or guess it among several standard use cases), and there are a number of ciphertexts. Don't reuse IV, at least with the same key.

For any block cipher in CTR mode, it is typically extremely dangerous to reuse the same key and IV (even if secret). That's because the encryption ends up to be XOR with a fixed keystream (a bitstring) dependent on key and IV. Even though the keystream is initialy secret and indistinguishable from random (for an adversary not knowing the key), the keystream can be recovered (and all ciphertext deciphered) under many plausible assumptions, including:

Adversary knows one plaintext.
Adversary knows the ith bit of the ith plaintext.
Adversary knows some general characteristic about the plaintext; and there are a enough ciphertexts.

The first and arguably second bullets are excluded by the question, but the third applies to nearly all practical use cases except super-encryption of already enciphered data, when there are enough ciphertexts.

The crudest, but still sometime effective method to find the keystream is to determine the expected mean value of the ith bit of plaintext (which is a function of the kind of plaintext and of i, independently of the actual plaintext, which is unknown). If that deviates enough from 1/2 in either direction (as it does for many practical kinds of plaintext), and enough ciphertext is available, comparing this expected mean to the actual mean for the ith bit in the ciphertext will often reveal the ith bit of the keystream (it is expected that the means are on the same side of 1/2 for a keystream bit of 0, and on different sides for 1).

Inter-bit dependencies in the plaintext allows much faster recovery of the keystream. If plaintext is known to be English text in ASCII, a handful of ciphertexts will typically allow to recover nearly all of the keystream. Even if the plaintext was email addresses, there is enough redundancy in that to allow to find the keystream from a few hundreds ciphertexts.

If database entries are never modified and have a key index that wont vary, a common and safe solution to the problem of IV choice and availability for decryption is to use as initial counter value the index shifted left by a constant large enough that the counter values will not overlap from one database entry to the next. For AES-CTR, that shift count constant can be as small as the number of bits in the maximum plaintext size in octets, minus 4. For 64 gigaoctet of maximum plaintext size, shifting left by 32 over 128 bits is fine. We can thus append 4 zero octets on both sides of an 8-octet binary representation of the index (without having to care about endianness, unless that's mixed) to set the initial counter value (which, depending on implementations details, may or may not be the IV; actually, many implementations with an IV less than 16-octet internally append zeroes on the appropriate side).

While other modes of operation (like CBC) significantly mitigate the danger of IV reuse, that's still extremely dangerous in some scenarios.


Is AES easier to crack when the input is small? Say you just want to encrypt a number. For example, say the number could be any  double. A double in C# and Java is 8 bytes.

If you were to encrypt a double using AES (MS-Doc, defaults to CBC as the mode):

var cypherText = AES.Encrypt(123d); // 8 bytes

would that be trivial to crack? If not would it at least be significantly easier to crack than the cyphertext from a larger input:

var largeText = GetDeclarationOfIndependence(); // 6760 ascii characters, so 6760 bytes
var cypherText = AES.Encrypt(largeText);

Assuming that encryption is performed correctly:

Using a modern cipher (AES)
An appropriate mode of operation
With no bugs in the implementation

then the nature of the plaintext has no effect on the security of the ciphertext.

  If not would it at least be significantly easier to crack than the cyphertext from a larger input:

Actually, a longer ciphertext is technically easier to "crack" than a small one.

The reason being that the larger cryptogram provides the adversary with more known plaintext-ciphertext pairs. Attacks that do exist against modern ciphers typically require very large numbers of plaintext-ciphertext pairs.

That being said, this effect is still negligible in pretty much any realistic use case. The quantity of plaintext-ciphertext pairs required for cryptanalysis is frequently obscenely and prohibitively large.


Is it a cryptographic risk to share the same encrypted data over and over again? Regular scenario

Let's say I have secret files which I will encrypt. The resulting container will be shared and might be intercepted. Not good, but that's okay - that's why I encrypted the data in the first place.

Scenario in question

However, now, I'll encrypt and share the same data again. With the same passphrase. The container will be different (because the key changed) but the data inside it is identical. And the attacker knows this. Does this open the encryption to any vulnerabilities from a cryptographical standpoint?

Pardon my lack of technical terms. I guess this would be a ciphertext-only attack? But modified in a way that each plaintext (my data, my files) prior to encryption is the same?

(It's a general question, the encrypted container might be from dm-crypt/LUKS or VeraCrypt or even an encrypted ZIP archive. But I think all of them are using 256-bit AES.)

...but the data inside it is identical. And the attacker knows this. Does this open the encryption to any vulnerabilities from a cryptographical standpoint?

No. If it did, then encryption would not be very useful.

In fact, modern encryption schemes are designed to be secure even if:

The adversary already knows the plaintext that the ciphertext represents (known plaintext attack - KPA)

Where "secure" means they cannot recover the key or learn any information from other ciphertexts

The adversary can choose plaintexts, submit them to be encrypted, and obtain the resultant ciphertexts (chosen plaintext attack - CPA)
The adversary can choose ciphertexts, submit them to be decrypted, and obtain the resultant plaintexts (chosen ciphertext attack - CCA)

Even in all of these scenarios, a modern cipher will remain secure. Not only will it protect the plaintext from discovery, no adversary will even be able to distinguish a ciphertext from a random stream of bits with a non-negligible probability.

As long as the encryption provider is:

using a competent algorithm (such as AES-256 mentioned in the question)
in an appropriate mode of operation (e.g. an authenicated mode such as GCM)(edit: AEAD is apparently not relevant in this scenario)
and handles initialization vectors appropriately

then the messages will remain as secure as the passphrase that protects them. How secure the passphrase is will depend on how long/complex it is, combined with how the key is derived from it.


Curve25519/Montgomery curves points with order 8 I found this post about Curve25519. It states, that there are only 5 points with a very low order. With this paper I was able to understand, how the points with order 2 and 4 were computed. My question is: How to compute the points with order 8?

Curve25519 has order $8\cdot q$, and we want a point of order $8$. This is the laziest solution I can think of:

Generate a random point $P$ on the curve;
Compute $Q = [q]P$. This point has order $1$, $2$, $4$ or $8$.
If $Q$ is not of order $8$, go back to step 1.

A sample code to see the points we get:
E = EllipticCurve(GF(2^255-19),[0,486662,0,1,0])
for i in range(20):
    P = E.random_element()
    Q = P.__mul__(2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed)
    print (Q.order(), Q)

Expect a few attemps until a point of order $8$ is found.

Another way to do this is to use division polynomials.
Just giving the general idea about them. There is a series of polynomials whose roots are related to torsion points. Basically, the points $P$ such that $[n]P = \infty$ have their $x$-coordinate as roots of a polynomial.
However, those roots can be over an extension field, so they do not correspond exactly to points on the elliptic curve over the base field.
Using SageMath, we can find the $8$-torsion points of Curve25519:
sage: p = 2^255 - 19
sage: E = EllipticCurve(GF(p), [0,486662,0,1,0])
sage: E.division_polynomial(8).roots(multiplicities=False)
[0,
 57896044618658097711785492504343953926634992332820282019728792003956564819948,
 39382357235489614581723060781553021112529911719440698176882885853963445705823,
 325606250916557431795983626356110631294008115727848805560023387167927233504,
 1]

There is the point $(0,0)$ of order $2$, the next root corresponds to two points of order $4$ on Curve25519 over $\mathbf F_{p^2}$, the next two roots to four points of order $8$, and the last one to two points of order $4$.


How can I force slow decryption in the browser? I have a string that I will encrypt on the server. I then want to send the encrypted string along with a decryption method for it to be decrypted in the browser.
I want the decryption to take some time for the end user. Let's say ~10 minutes.
Let me be clear:

I want the decryption to happen.
It must happen on the browser (I understand that some might cheat but let's assume I don't care much about these cases even if they happen).
It must take some time (~10 minutes).

I understand that decryption time depends on many parameters. You can assume that at least the string of data to be encrypted can be as small or as big as we need it to be in order to achieve the above 3 things. And we can assume the processing power of an average computer/browser.
Is this possible and how?
I am a JavaScript developer so a JS solution would be preferable. Some pseudocode/steps would also help.
I know nothing about cryptography so I would appreciate it if you could please refrain from using too much jargon I will probably not understand.

As I indicated in the comments, I believe a non-cryptographic solution may be the best for this task, where instead of attempting to measure "10 minutes" by the average amount of time it takes to do some computational task, you simply measure it by the wall-clock time. Note that this solution still uses some cryptography, but not as a proxy to measure 10 minutes.
Concretely, when a user wants the document, you can generate a key (say an AES private key) $k$, create a payload = $k || D$ where $D$ is the current date/time formatted in some standard way, let $h= H(k || D)$ be a hash of the payload, and then store $[h, k, D]$ in some table, and send $h$ to your user, along with the document (encrypted under the key $k$).
The user can then query you later with some hash $h'$. Upon recieving such a query, check if $h$ is in your stored table as part of some entry $[h, k, D]$. If so, and if at least 10 minutes have passed since the date/time $D$, return the key $k$ to the user, who can now decrypt. You can also evict the table entry $[h, k, D]$ at this point.
The pros/cons of this versus a "intentionally slow decryption" solution are:

There is less wasted computational effort on the part of the user

The limit of 10 minutes is enforced regardless of the user's particular architecture (and their desire to "cheat")

The operations on the server side of things are likely more efficient than the other RSA-based solution (for example, you have to use ~128 bits of randomness per user, instead of >2k for RSA to be secure).

The cons are:

The user has to query your server a second time
You must store some intermediate state for each user (the $[h, k, D]$). This should be rather small (a few hundred bits) per user, but is greater than zero.

I think it is worth mentioning that I expect it would be difficult to get a uniform "10 minute decryption time" in the browser using time lock puzzles, even among honest users. I have not thought through this in detail, but I imagine that differences in hardware architectures (especially with respect to the presence of certain SIMD instructions, i.e. Intel SSE / AVX type instructions) may be able to get a constant factor speedup on your users architectures in the underlying BigInt multiplication for RSA, which would then result in users having architecture-dependent decryption times.
If you implement things correctly (and make sure that auto-vectorization does not occur), you may avoid this issue. But even differences in clock speed (say 2GHz vs 3.5GHz, or whatever numbers are reasonable for a few-year-old phone vs a enthusiast's desktop) would likely make a big enough difference that it would be difficult to enforce a 10min decryption time for all users (you could likely ensure that decryption for all users takes at least 10 minutes, but for some users it may take 20 minutes, or whatever).


A set of key pairs and one hash to secure them I have a simple problem: I have a set of users' ECDSA key pairs, and say I want to encrypt them with a simple algorithm. I have access to one variable that uniquely identifies the user, so I hash it with a SHA-2 algorithm and have a string of bytes longer than each of the keys.

Is it safe to XOR a key pair, or XORing both of the keys together will make it easier to decode the original value?

What if I hash the entire key chain, does that make it much easier to get the data?

What you are proposing in effect means that you use a not-really-random one-time-pad, which is used twice (i.e. a two-times-pad). This is not secure.

Using a single hash to generate a key from a password is a bad idea - especially if the password is short, it is easy to brute-force it (i.e. try lots of passwords).
Using the simple XOR cipher to encrypt a ECDSA key pair, one half of which is public anyway, means that half your key is directly derive-able from the encrypted key pair. (This helps with the brute-forcing in step 1.)
Using a one-time-pad twice means that the attacker can derive $x_1 \oplus x_2$ (i.e. the XOR of the two private keys). I don't know of any way to come from this to $x_1$ and $x_2$ (given also the public keys $g^{x_1}$ and $g^{x_2}$), but I would not wonder if someone would find a way to do this easier than trying all $x_1$.

Instead, use established algorithms:

Use an established key derivation function (Bcrypt, Scrypt, PBKDF2) with an appropriate work factor to derive the key from a password.
Use a secure cipher algorithm (a block or stream cipher) in a secure mode instead of XORing.


how can I draw from a set of characters using a seed for entropy? Given a seed string S, I want to deterministically generate a password of the form:

N characters, each chosen from a set of characters C

Unfortunately neither N nor the cardinality of C necessarily play nicely with powers of 2, and I want to avoid introducing a bias towards any particular characters in C.

Is the following a sane approach to generating these passwords with a uniform distribution, or, is there already a well known approach to doing this?

To choose the i_th character of the password, I would compute for every character c in C the value sha256(S + i + c), then choose the character c for which this has the largest hash.

Yes, this strategy works, in the sense that it generates each character with the appropriate distribution, and there is not trivial attack (with the caveat that the formatting used must allow to unambiguously find $S$, $i$ and $c$ from the concatenation $S\|i\|c$; formatting $i$ and $c$ as fixed-width fields will do). However

We do not have a strong security argument: for this we'd need a MAC keyed by $S$, e.g. use $\operatorname{HMAC-SHA256}(S,i\|c)$; the HMAC construction turns a hash into a MAC, with a proof.
There is no entropy-stretching, nor salt, as in standard password-based key derivation; thus a guess of $S$ can be checked with low odds of errors knowing a password and it's $i$; if the seed string $S$ is low-entropy (like a master password), that's a huge problem.
We can obtain the appropriate distribution with far less hashes; see this.

Point 2 is by far the most worrying.


McEliece variants that support signatures Besides the Niederreiter cryptosystem, are there any other variants that support digital signatures? Can any of them sign arbitrary signatures unlike the Niederreiter cryptosystem? What are the key and signature sizes?

There is a variant of the Neiderreiter system by Courtois, Finiasz, and Sendrier found in their paper: "How to achieve a McEliece-based Digital Signature Scheme" from Asiacrypt 2001. The Wikipedia article on the Neiderreiter Cryptosystem provides a brief introduction to this signature. There is an element of trial and error in the signing process that is cumbersome but it should work for all message hashes.


Is the following non-interactive zero-knowledge set membership protocol provable secure? Given the following Zero-knowledge set-membership protocol https://infoscience.epfl.ch/record/128718/files/CCS08.pdf]. That is given in the following steps (Please refer to page 9).

The Verifier

-select a set of elements denoted as $\phi$

-Select $x \in_{R} \mathbb{Z}_{p}$ and computes $y \leftarrow g^{x}$ and $A_{i} \leftarrow g^{\frac{1}{x+i}}$ for every $i \in \Phi$

The Prover

-select an element in the set $\phi$ denoted as $\sigma$

-Select $v \in_{R} \mathbb{Z}_{p}$ and computes $V \leftarrow A_{\sigma}^{v}$

-Select $s, t, m \in_{R} \mathbb{Z}_{p}$ and computes $a \leftarrow e(V, g)^{-s} e(g, g)^{t}$ and $D \leftarrow g^{s} h^{m}$

-computes challenge c using fiat-shamir heuristic as: $c=H(V\|a\| D)$

-computes $z_{\sigma} \leftarrow s-\sigma c, z_{v} \leftarrow t-v c,$ and $z_{r} \leftarrow m-r c$

-sends $C, c, a, D, Z_{\sigma}, Z_{v}, Z_{r}$ to the verifier

The verifier validates the proof by checking:

$D \stackrel{?}{=} C^{c} h^{z_{r}} g^{z_{\sigma}}$ and $a \stackrel{?}{=} e(V, y)^{c} \cdot e(V, g)^{-z_{\sigma}} \cdot e(g, g)^{z_{v}}$

Following, the following Theorem 1 (that proofs the zero-knowledge of the above protocol) as follows:

"the extraction property implies that for any prover P* that convinces V with probability ε, there exists an extractor which interacts with P* and outputs a witness (σ, r, v) with probability poly(ε). Moreover, if we assume that the extractor input consists of two transcripts, i.e.

$$
\left\{y,\left\{A_{i}\right\}, V, a, D, c, c^{\prime}, z_{\sigma}, z_{\sigma}^{\prime}, z_{v}, z_{v}^{\prime}, z_{r}, z_{r}^{\prime}\right\}
$$

the witness can be obtained by computing:
$$
\sigma=\frac{z_{\sigma}-z_{\sigma}^{\prime}}{c^{\prime}-c} ; \quad r=\frac{z_{r}-z_{r}^{\prime}}{c^{\prime}-c} ; \quad v=\frac{z_{v}-z_{v}^{\prime}}{c^{\prime}-c}
$$

The extractor succeeds when $\left(c^{\prime}-c\right) \text { is invertible in } \mathbb{Z}_{p}$"

My question:

Considering the ZKSM and proof given in the paper, if we consider the case where the following data

$${y,{A_i },V,a,D,c,Z_σ,Z_v,Z_r}$$
is made public (e.g., stored in public blockchain that acts the verifier). Thus, an adversary succeeds in getting the witness ($\sigma$, r, v) if he is able to obtain $c^{'}$ such that $\left(c^{\prime}-c\right)$ is invertible in $Z_p$. Is this case doable?. In other words, considering properties of fields
 can the adversary find $c^{'}$ such that $\left(c^{\prime}-c\right)$ is invertible in $Z_p$?.

Reading the last sentence:

Can an adversary find a $c’$ such that $c’ - c= 0$ in a field. This follows from the definition of a field, whenever $c’ != c$


Is a Diffie-Hellman scheme in which parties always use the same public keys vulnerable? I have come across a couple of protocols in which the public keys of the parties are static across conversations, even with different users. Something about this makes my hairs stand on end but I can't pin down what the actual weakness is, if there is one. Is a scheme like this OK or is it known to be vulnerable?

This was actually the original proposal of Whit Diffie and Martin Hellman back in 1976:  Alice puts $g^a$ in the telephone book and keeps $a$ secret, Bob does likewise with $g^b$ and $b$, and whenever Alice and Bob want to have a conversation they use $g^{ab}$ as a shared secret key.

The main trouble is that you expose an oracle for $h \mapsto h^x$, where $x$ is your secret key, to anyone who wants to have a conversation with you.  If the group we're working in has many subgroups of small orders $\ell_1, \ell_2, \dotsc, \ell_n$, then the adversary can feed you points $h_1, h_2, \dotsc, h_n$ of those orders in order to learn $x \bmod \ell_1,$ $x \bmod \ell_2,$ $\dotsc,$ $x \bmod \ell_n$—this is the Lim–Lee active small-subgroup attack.

But if we operate in a group of prime or nearly prime order, that doesn't leak much information—for finite-field DH, for instance, we can use a safe prime $p = 2q + 1$, meaning that $q$ is also prime, so the only possible subgroup orders are $\{1,2,q,2q\}$, and we can choose $x \equiv 0 \pmod 2$ so that the adversary learns nothing from this.

Of course, if an adversary ever breaks into your computer and learns $x$, then they can also decrypt past conversations—the longer you use a secret key for encryption, the more conversations are vulnerable to retroactive decryption.  So you might want to use a long-term secret only for authentication and do a fresh key agreement per conversation, somewhat like Signal does—and pay attention to when you erase keys.  (A protocol that involves erasing keys is sometimes said to have ‘forward secrecy’, but I recommend against using that term because it obscures when you erase keys.)


Secure Broadcast Channel I've read a paper that says that one of the "assumptions" that it makes is secure broadcast. Why is this an assumption? Can't a broadcast channel be built with simple primitives--i.e. encrypt and sign messages with a shared key?

And, assuming that there is something more that I'm missing, how are broadcast channels usually approximated in practice?

The problem is not broadcast, but secure broadcast. Secure broadcast guarantees that every recipient ends up with the same message.

If you just sign the message and send it separately to each recipient, a malicious sender could send different messages to different recipients.

A simple solution is that each recipient counter-signs the message and re-sends it to the other recipients. Once everyone has everyone's signature on the message, they accept.

There are better solutions, but all of them have an associated cost.


Double 3DES/TDES Encryption If 3DES/TDES (officially TDEA or Triple DEA - Triple Data Encryption Algorithm) encryption is used twice, using 6 different keys K1-K6 :

ciphertext = EK6(DK5(EK4(EK3(DK2(EK1(plaintext))))))
plaintext = DK1(EK2(DK3(DK4(EK5(DK6(ciphertext))))))

would be such encryption more strong and less vulnerable to attacks than a regular 3DES ?

Furthermore, instead of E-D-E-E-D-E encryption and D-E-D-D-E-D decryption, would such double 3DES work with D-E-D-E-D-E encryption and E-D-E-D-E-D decryption as well?

You'd have to move to 9DES rather than 6DES as undoubtedly 6DES would still fall to the meet in the middle attack that can be performed on 2DES, now with the two 3DES block ciphers as parts. That means that (given a large amount of memory), the attack only adds a single bit of security, 113 bits.

Even then, just like 3DES has only 112 bits security for 3 different keys, 9DES would seem to max out to 2 x 112 = 224 bits of security rather than 9 x 56 = 504 bits that you would expect. However, it might well be that the meet in the middle attack on 3DES now doesn't work anymore giving you 2 x 168 = 336 bits of security instead. You might want to prove that.

Of course all the other nasty properties of 3DES are kept. Weak keys, parity bits, small block size and horrible speed all have to be endured. However, now it adds huge keys and additional calculations for this ad hoc fix of an ancient, insecure cipher.

The 5DES scheme probably has 168 bits of security if you use a meet in the middle. DES and other modern ciphers cannot be split in two after all; they are protected against meet in the middle by design (it might be the first thing to fall when a cipher is designed by a well willing amateur that at least gets some things right).


Implementing CD serial key system I am trying to create a system where to unlock the application one needs to enter a serial code. I have read many articles on the theme but there are two problems bugging me. One is, If I have a keygen and I can generate as many keys as I like then anyone else can do that too, but solving this by requiring a long "private key" there occurs another problem.

Usually serial codes are supposed to be short and easy to type but even the shortest Elliptical curve signature algorithm has a signature size of 160-bits which could not possibly fit into the 100 bits I have. Is it possible to use a threshold approach?

I have seen many similar questions (please do not mark as duplicate) but none have answered my main question as to how can you treat the serial code as a signed document if the length of signature is at least 60 bits more than the maximum allowable size of a serial code?

Could you please give a deeper insight on my question and bare with my lack of knowledge in many areas? Thank you.

If you want $N$ serial numbers, your serial numbers will have to use $n$ bits for uniqueness, where $n = \log_2 N$. So if you have 100 bits to use for the serial, you could use 20 to get about a million serials and have 80 bits to use for a cryptographic MAC or signature.

Now there are two approaches, the symmetric and the asymmetric.

In the symmetric approach, you have a key $k$ and calculate a $b$-bit MAC for each $n$-bit ID: $S = I||MAC_k(I)$.

This is very easy and allows an arbitrary split between $b$ and $n$ by truncating a longer MAC if needed. However, if the program can be easily studied, you may find the key and be able to use that for a key generator.

With $b = 80$ this is quite secure as long as the key remains secret. (Within the realm of plausibility if the adversary is dedicated, but very unlikely against a random CD key.)
In the asymmetric approach, you have a key-pair $(s, p)$ and calculate a signature for the ID that can be verified with the public key.

Here you would need a public key system with exactly $b$-bit signatures. OTOH, it would prevent even someone who can find the public key from creating serials... but wouldn't prevent someone from overwriting the public key with their own.

However, with $b = 80$ you'd need an 80-bit elliptic curve, which is not secure (nor would a 100-bit one be). It's only approximately as secure as a 40-bit symmetric key would be, and can be broken relatively easily without special hardware.

Therefore, if you need only 100-bit serials, I would recommend the former route. It's just security through obscurity, but the alternative isn't secure either.

There is a workaround to make an asymmetric scheme work, but then you need to shift bits from the "signatures" into the "public key".

For each ID you could create an $80$-bit MAC (or a random number, but a MAC allows you to recover serials), but instead of including the key in your program, you'd include hashes for each such MAC. E.g. $H(MAC_k(I))$ for some preimage resistance hash function $H$. The program would verify a serial $I|M$ by calculating $H(M)$, then comparing that to the hash it has for $I$. With $2^{20}$ serials, you'd need to store 10MB of "public key" to verify the serials with $80$-bit security.

Now the enterprising attacker could still overwrite (one of) those hashes to whatever they like... so it's not necessarily much better than the one where you just stored the key. (This is always the case with DRM, unless you involve some kind of hardware module.)


Why am I getting a wrong output when implementing Feige-Fiat-Shamir ID protocol? I am trying to implement the Feige-Fiat-Shamir identification protocol. I've read another posting here on this site and I tried to adapt - however the end results always fail to match. Maybe because aim doing Feige-Fiat-Shamir and not Fiat-Shamir? To get to the bottom of my problem, I therefore decided to post my own question.

Preparation:

N is given:

77

s are given:

s1 = 5, s2 = 12, s3 = 37

Compute v:v = (s^2) % n

v1 = v2, v2 = 58, v3 = 37

Now the round:

Select random r between 1 and n - 1 and s = 1, -1:

r = 12, s= 1

Calculate x:

x = (r^2) * s % n = 67

Choose a either 0 or 1:

a1 = 1, a2 = 0, a3 = 0

Calculate y:

y = (r * s^a) % n = 60

Now ,if y^2 equals (x * v^e) % n then it's accepted. However in my case

y^2 mod n = 58
(x * v^e) % n = 19

19+58 = 77, but I know that y^2 mod n should be 19 as well.
Or that 58-19 should be N, which isn’t the case either.

Question:

Why don't these numbers match? What am I doing wrong here? Is it maybe because Feige-Fiat-Shamir is y2 = ±xva1 · ·van modN ? So if 58+19 = 77 or 58-19 = 77 the protocol works?

The first problem is, that you calculated $v_i$ wrong right at the start.
$$v_i = s_i^2 \mod n$$
This means:
$$v_1 = 5^2 = 25 \mod 77$$
$$v_2 = 12^2 = 67 \mod 77$$
$$v_3 = 37^2 = 60 \mod 77$$

Then at the end you have:
$$(x \cdot \prod_i v_i^{a_i})  = 67 \cdot 25 \cdot 1 \cdot 1 = 58 \mod 77$$


Are bijective polynomials of degree $2 \bmod 2^m$ efficiently inverted? Take a bijective polynomial of degree $2 \bmod 2^{64}$ like:

$m = (n(n+1)/2)\ \bmod 2^{64}$

It is bijective and can trivially be inverted for numbers up to $2^{32}$ by calculating $\lfloor\sqrt{2m}\rfloor$ . For all other numbers the inversion is not that trivial but I have the feeling it could be done without brute force.

As pointed out in the comments by poncho m only depends on the lower i+1 bits of n . Therefore n can be reconstructed by testing the four possible states of the the two most significant bits at a time, starting with the first ones, then choosing the combination that produces the correct binary suffix to expand iteratively.


SSL Pinning security: can MitM generate the same public key? This is a very newbie question.
SSL Pinning is "safe" in assumption that only the real server can decrypt the public key.
By design, it should be almost impossible to find the private key from the public key.
However, is it relatively easy to create a new certificate (private key) that generates the "same" public key which the SSL Pinning trusts?
In order words, how hard is to create a new private key that generates the public key "I want".
For example, if I want to create a new certificate which the public key is:
sha256/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa=
Can I easily do that?

It's astonishingly difficult.

With RSA, it's literally a mathematical impossibility.

With Weierstrass, Montgomery and Edwards elliptic curves, the possibility of generating the same public key from different private key should be impossible assuming the private key scalar value doesn't overflow the order of the generator of the group.

With Hash-based digital signatures, this may be possible, because the public key is the tree hash of many one-time hash signature public keys. But still, finding such public key collision is as difficult as finding any regular hash collision. (not to mention real-world hash signatures often use randomized hashing).

Lattice-based schemes have the mathematical possibility of generating colliding public keys if the public component reduces the dimension of the private component, but that's very improbable. However, it should be noted, even the public component are randomly generated in most candidate schemes in NIST Post-Quantum Cryptography Project.


What are the possible applications of fully homomorphic RSA algorithm? As far as I know, RSA is not used for encrypting large files. Instead some symmetric key algorithm like AES or DES is being used for encryption with a random key and that random key is then encrypted with a public key. So, all operations in cloud will be performed on data that is encrypted using the symmetric key algorithms.

Then why would someone want RSA to be fully homomorphic? Are there any specific application for that? in cloud computing?

The question's observation is perfectly right: RSA as practiced uses padding or/and is used to encipher a symmetric key, which makes it not homomorphic at all.

Further, textbook RSA (without padding) is homomorphic, but is deterministic (the same plaintext always produces the same cypertext). This is most often a devastating weakness, because it lets anyone (with the public key) test an hypothesis on the plaintext.

For this reason, use of RSA as an homomorphic asymmetric encryption algorithm is questionable, and accordingly is now almost entirely absent in cryptographic publications with a peer-review system that I trust.

Update: A related question asks if it is possible to devise safe RSA padding while preserving homomorphy; I tentatively answered in the affirmative, but that does not seem practical at all.

I do not know any way to make RSA fully homomorphic, in the usual sense that it allows both addition and multiplication of plaintext from ciphertext.

The Pailler cryptosystem is a randomized asymmetric encryption algorithm (safe from plaintext guessing); is homomorphic (for addition of plaintext, rather than multiplication for RSA); is based on the same mathematical problem as RSA; and is not much more difficult to grasp. It might be a proper substitute for RSA when a homomorphic asymmetric encryption algorithm is thought. Also, there seems to be more applications of additive homomorphic encryption than of the multiplicative breed.

Among applications of the Pailler cryptosystem (and homomorphic encryption in general) are some electronic voting protocols (an interesting theoretical subject; still, count me among the strong opponents of their actual use for political elections).


In RSA, why would we ever want to find the values of p and q if we already know phi(n)? I'm studying RSA for the first time, and I know that $p$ and $q$ must be kept secret because with them we can calculate $\phi(n)$, which then lets us calculate the private key $d$. So $p$, $q$, and $\phi(n)$ are all kept secret.
Is there any reason we'd want to find $p$ and $q$ by working from the definition of $\phi(n)$ though? I'd think that an attacker wouldn't care about the specific values of $p$ and $q$ - if they have $\phi(n)$, they can calculate $d$ rightaway.
I ask this because I read this thread which showed how to get $p$ and $q$ from $\phi(n)$. I just don't see why we'd ever want to do that though. Why would an attacker care if $p$ = some number and $q$ = some other number, if they already have $\phi(n)$?

From an attacker's perspective, when we have $(n,e)$ and $\phi(n)$, we can compute a working $d\gets e^{-1}\bmod\phi(n)$. It will allow decryption or signature forgery in time polynomial to $\log(n)$: the attacker thus has won. Yet for repeated decryption or signature, the attacker may want to use the Chinese Remainder Theorem for efficiency, just like some legitimate users of RSA routinely do (see next section), which requires factoring $n$.
Also, the attacker might want to look at what the factors of $n$ are in hope to find patterns, in order to carry more attacks for other keys generated by the same method. And as kelalaka puts it, mathematical enthusiasm, curiosity, and searching for where that leads for better understanding are reasons enough.

The Chinese Remainder Theorem to speed-up RSA
A pragmatic reason both legitimate users of RSA and attackers want the factors of $n$ is they allow computation of the private-key function $x\mapsto y=x^d\bmod n$ several times faster using the Chinese Remainder Theorem.
When $n=p\,q$ with $p$ and $q$ distinct primes, that goes:

precomputations done once:

$d_p\gets e^{-1}\bmod(p-1)\;$ or equivalently $\;d_p\gets d\bmod(p-1)$
$d_p\gets e^{-1}\bmod(q-1)\;$ or equivalently $\;d_q\gets d\bmod(q-1)$
$q_\text{inv}\gets q^{-1} \bmod p$

for each computation $y\gets x^d\bmod n$ :

$\;x_p\gets x^{d_p}\bmod p$
$\;x_q\gets x^{d_q}\bmod q$
$\;y\gets\big((x_p-x_q)\,q_\text{inv}\bmod p\big)\,q+x_q$

The execution time is dominated by steps 1 and 2. The cost of exponentiation modulo $m$ with the exponent the same size as $m$ grows about as $(\log m)^\alpha$ with $2<\alpha\le3$ (depending on arithmetic algorithms used for modular multiplication), and using the CRT roughly halves $\log m$. Thus (for large $p$ and $q$ of comparable magnitude) the work is reduced by a factor in the order of $3$ (obtained as $2^\alpha/2\,$). Also, it is possible to parallelize steps 1 and 2, further halving the wall clock time on a machine with two otherwise idle CPUs.
The technique is even more useful if $n$ has more than two prime factors, that's multi-prime-rsa. For the disputed history of that realization, see this. For the computations, see this.
It is not uncommon that software accepts a private key as $(n,e,d)$ yet use that speedup, in which case it will need to factor $n$, as follows.

Getting the factorization of $n$ from $(n,e,d)$ or $(n,\phi(n))$
When given $(n,e,d)$, we can factor $n$, but the usual method for this does not find $\phi(n)$ first, for that's not trivial. Sure, computing $(e\,d-1)/\left\lceil(e\,d-1)/n\right\rceil$ can yield $\phi(n)$ if $e$ is small and $d$ was computed as $d\gets e^{-1}\bmod\phi(n)$. However, neither condition is required by the modern definition of RSA¹.
The method generally used to factor $n$ from an RSA $(n,e,d)$ or $(n,\phi(n))$ computes $f\gets e\,d-1$ or sets $f\gets\phi(n)$, then uses that for any $w$ coprime with $n$, if holds $w^f\equiv1\pmod n$. The factorization of $n$ is possible using an algorithm in Gary L. Miller's Riemann's hypothesis and tests for primality, in Journal of Computer and System Sciences, 1976 (free PDF available). For odd composite square-free $n$, that goes:

$r\gets 2f/(f\oplus(f-1))$ [this $r$ is odd and such that $f=r\,2^s$ for some $s$]
repeat (few times, since each iteration succeeds with probability better than 50%)

draw a random integer $w$ in $[2,n-2]$
optional (and not useful for $n$ an RSA modulus)

$u\gets\gcd(w,n)$
if $u\ne1$

output "$u$ is a non-trivial factor of $n$" and stop.

compute $v\gets w^r\bmod n$
if $v\ne1$

while $v\ne1$ (that's at most $s$ times)

$u\gets v$
$v\gets v^2\bmod n$

if $u\ne n-1$

$u\gets\gcd(u+1,n)$
if $u\ne1$

output "$u$ is a non-trivial factor of $n$" and stop.

When $n$ has more than two factors, the algorithm can be used to fully factor $n$, by running it again replacing $n$ by $u$ or $n/u$, for any of these two that is not prime. We have not handled some tractable difficulties arising when $n$ is divisible by the square of a prime, but that's not the case in standard RSA.
Try It Online! This generates an $(n,e,d)$ with 2048-bit $n$ the product of two large distinct primes $p$ and $q$, and $\gcd(p-1,q-1)$ with a 256-bit prime factor, a large random $e$, and large $d$ with $e\,d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$ [which makes computing $\phi(n)$ non-iteratively impossible AFAIK]; then finds the factorization of $n$ by Miller's algorithm.

¹ The de-facto definition of RSA is PKCS#1. It prescribes $e\in[3,n)$, $d\in[1,n)$, and $e\,d\equiv1\pmod{\lambda(n)}$. This uses the Carmichael function $\lambda$. When $n=p\,q$ with $p$ and $q$ distinct primes, it holds $\lambda(n)=\operatorname{lcm}(p-1,q-1)=\phi(n)/\gcd(p-1,q-1)$. Using $\lambda$ (rather than $\phi$) makes the later equation the necessary and sufficient condition (rather than a sufficient but not necessary condition) for RSA encryption/decryption to succeed for any message in $\Bbb Z_n^*$, and in the whole $\Bbb Z_n$ when $n$ is squarefree. Using $\lambda$ allows at least $\gcd(p-1,q-1)$ working private exponents $d$ values, of the form $d_j=(e^{-1}\bmod\lambda(n))+j\,\lambda(n)$. That's at least two, and can be many (though rarely for random choice of primes $p$ and $q$). The FIPS 186-4 standard requires using $d_0$, which is often smaller than $e^{-1}\bmod\phi(n)$, often making raising to the power $d$ faster.


Why does RSA signature need padding? Actually, I think I know why, but consider RSA2048 and SHA256. What about to, instead of padding, just use pbkdf2 with just 1 iteration to expand the 256bits hash to full 2048bits and use those 2048bits as an input for the plaintext RSA?

What would be wrong with that crypto-schema?

As indicated in the comments, using PBKDF2 instead of e.g. PSS is replacing the padding scheme with another padding scheme. PBKDF2 is used as a key derivation scheme that accepts a password. Although that password needs to be encoded as bytes first, it does mean that you use PBKDF2 differently from how it is intended.

If PBKDF2 is used without a salt then you would have a deterministic scheme. If you do use a salt, then you'd need to somehow put it in your signature scheme. That's not necessarily a huge problem, but your current scheme is not fully described at best.

Similarly, you probably simply mask out the most significant (leftmost) bit of the PBKDF2 result to zero. That's fine as long as you describe it correctly and perform verification correctly. It's slightly awkward that the result is within the range $[0, 2^{(l - 1)})$ rather than $[0, {N - 1})$ to create a full domain hash but I guess we can look past that.

PSS is provable secure (given the usual pre-conditions, such as RSA and the used hashes being secure of course). Your padding scheme on the other hand lacks any kind of security proof (although, as SEJPM already commented, it would probably be easy to show that it generates a full domain hash, and that's considered secure). I don't see why it would not be secure - I think it is even likely that it is rather secure. However, with any cryptanalysis on a fully described scheme, that's just an educated guess.

The question is why you would need it since PKCS#1 v1.5 padding (for signature generation) only requires a prefix / postfix in addition to the hash value and PSS can be configured to use a single hash function (or any combination of two secure hash functions, one for the data and one as configuration parameter for MGF1).

If you'd study PSS you'll probably conclude that it is not that different from your scheme at all...


Can the proof of elasped time (PoET) consensus algorithm be exploited by multiple nodes? i recently learned about the Hyperledger Blockchain Project and the specific frameworks. In case of the Sawtooth framework, consensus is reached not by PoW but by PoET (Proof of elapsed Time).

When getting familiar with the proof-of-work (PoW) you usually hear that it's safe regarding participant exploits, because of the computation power which would be needed.

In regards of PoET where the leader for making the consensus is elected by the node with the shortest wait time, i am wondering if it would not be possible to exploit the system, when spaming the network with multiple nodes, so it's more likely to become the leader.

BR

Yes, here's an article stating that "SgxSpectre Attack Can Extract Data from Intel SGX Enclaves".

  According to researchers, SgxSpectre works because of specific code
  patterns in software libraries that allow developers to add SGX
  support to their apps. Vulnerable SGX development kits include the
  Intel SGX SDK, Rust-SGX, and Graphene-SGX.

  Academics say an attacker can leverage the repetitive code execution
  patterns that these SDKs introduce in SGX enclaves and watch for small
  variations of cache size. This is a classic "side-channel attack," and
  is quite effective.

However, Intel stated that an update for the Intel SGX SDK that adds SgxSpectre mitigations will be released on March 16, 2018.

Also, Here's a research paper that does some theoretical analysis on compromising a blockchain network using SgX and finally states that "Yes, it might be possible".

The title of this paper is "On Security Analysis of Proof-of-Elapsed-Time (PoET)". I'm adding relevant snips of the paper to ensure that in case dead links occur, at least the summary of what they say is available in this post.

The brief of this paper states that

  "To fulfil this gap, we develop a theoretical framework for evaluating
  a PoET based blockchain system, and show that the current design is
  vulnerable in the sense that an adversary can  jeopardize the
  blockchain system by only compromising Θ(log log n/ log n) fraction of
  the participating nodes, which is very small when n is relatively
  large.

  Based on our theoretical analysis, we also propose methods to mitigate
  these vulnerabilities"

They go on to summarise that there are ways to mitigate these problems.

  Changing the probability distribution of F. If the probability distribution F does not rely on n, then adversaries have to compromise
  a a+µ fraction of the nodes in order to compromise the system.

  Allowing blocks generated by honest mining nodes to be rejected. We assume that the statistical test will not reject a block that is
  generated by an honest node, whereas the adversaries can simulate the
  fastest honest node in the system. It is possible to get beyond the
  threshold of Θ(log log n log n) if we allow the statistical test to
  reject blocks generated by honest users.

However, it is important to note that this paper does not mention a concrete method to compromise the safety of the PoET algorithm running in an SGX enclave and merely states that

  "SGX and other trusted computing technologies are not 100% reliable.
  Especially, they may be vulnerable to sophisticated adversaries with
  necessary resources and skillsets."

But given the SGXSpectre attack, it is not an academic question but a practical one ....

UPDATE: Here's an excellent video titled "34C3 - Microarchitectural Attacks on Trusted Execution Environments" where Keegan Ryan
explains in great detail about how TEE attacks are performed. This is absolute gold for a person interested in defending against security breaches.

TLDR: Yes, it is indeed possible to compromise the PoET algorithm (SGXSpectre attack) as also by compromising a small fraction of the participant nodes. There are also some ways to mitigate if not resolve this issue (SGX SDK Patch, other approaches).


What 32 bytes TLS data records for? I've captured my tor client network traffic and noticed that in every packet it sends 2 TLS records first of which is always 32 bytes long. The first TLS record seems not to be carrying any data. What is it for?

It's a defense against the BEAST attack.

This attack is against TLS 1.0 (and SSLv3) and CBC mode; in CBC mode, TLS always uses the previous ciphertext block as the next IV, and hence the attacker can always predict the IV that will be used to encrypt the next block.  So, what the attacker does is convince the sender to send a specific piece of data; that data, combined with the IV, causes AES (or DES/3DES) to encrypt an attacker chosen block, and that allows the attacker to tell whether previous blocks of encrypted data corresponded to a specific plaintext.

So, for this attack to work, the attacker needs to know the IV that will be used when he chooses the data to encrypt.

What this empty record does is mess this attack up.  The attacker knows the IV that will be used to encrypt the empty record, but he can't control the data that is encrypted (as it is empty).  TLS then sets the 'next IV' to the last ciphertext block of that record; then, TLS encrypts the real record (including the plaintext that the attacker has potentially chosen); however it uses an IV that the attacker could not predict when he selected the plaintext, and so the attack doesn't work.

An easier defense would be to use TLS 1.1 or latter (which selects the CBC mode IV for each record unpredictably), however if you're stuck with TLS 1.0, this is the sort of thing you need to do


Can an attacker predict value of $d$ if attacker already used $n$ for encryption? In RSA we have value of n and e which is known to sender.
If the sender keep maintaining a database of possible n's he can easy calculate $\phi(n)$ because he already know $p$ and $q$ then. $d$ is $e^{-1} \mod \phi(n)$.

If we choose a large number which is product of two primes, can an attacker predict value of $d$?

Technically you're right, if you get the two prime-factors of n (p and q), then you can calculate everything else pretty easily.

But that's the problem! There is no known way to calculate p and q efficiently, but it is also unproven, if there really isn't a suitable algorithm and RSA is purposefully implemented in that way.

This is actually one of the big unsolved questions in mathematics.

See:

https://en.wikipedia.org/wiki/P_versus_NP_problem
https://en.wikipedia.org/wiki/Integer_factorization

Also your idea with storing a database of possible n's is infeasible, because this database would be unimaginably huge. You would have to store all possible calculations which would easily be greater than the number of atoms in the universe by far.


How can I generate a brief (100) stream of random numbers, not using the computer or throwing dice? I am looking for a method of making random numbers that is off-line and is also independent of specialist equipment like a Geiger counter.

Do a long jump, measure the distance in millimeters, take it modulo 10.

Repeat 100 times.

Another idea: use clock timer that shows milliseconds, start it and then turn off after some time, look at the last digit.


Mixing x into permutation through XOR vs. modular addition Block ciphers mix key material into the permutation through XOR. Also do pre and post whitening this way.

Chacha/Salsa finishes by 32-bit modular adding key and iv material (among other bits but since reversing them is trivial that doesn't matter) into permutation output.

What is the rationale behind using 32-bit modular addition instead of XOR for that final step? MD hashes which have the exact same problem solve it with XOR and not modulus > 2 addition.

Either operation works as long as one operand (or both) is unpredictable and the two operands are (practically) statistically independent. Normally XOR is used because it requires fewer transistors and less time than modular addition in hardware based implementations.

In software both operations run in one cycle for data that fits a register size. This gives addition an advantage over plain XOR operations. Differences in inputs to the steps of the permutation propagate faster with additions because carry bits influence the probability that an output bit may change.

ChaCha is primarily meant to be used in software implementations on machines with native support for 32-bit modular addition. Replacing the final additions with XORs is very unlikely to effect security, so the choice may be arbitrary.


M-94 disk cipher keyspace If the M-94 had only 10 disks, what would be the keyspace of the resulting cipher and what is the useful keypspace of the 10 disk cipher?

In a disk cipher like the M-94, each key corresponds to a permutation of the cipher disks.  Thus, with $n$ disks, there are $n! = 1 \times 2 \times 3 \times \dots \times n$ distinct possible keys.

(It's technically possible for some of these keys to be equivalent, e.g. if two of the disks are identical.  But this is extremely unlikely if the letters on each disk are ordered randomly.)

Note that enumerating the keyspace by brute force is not the most efficient way to attack a disk cipher (and thus the size of the keyspace is not a meaningful indicator of the strength of the cipher), regardless of whether the attacker knows the alphabets on the disks or not.

Rather, a typical cryptanalytic approach would exploit either known or guessed plaintext, or simply the fact that consecutive letters in English text are highly correlated, and in particular, that certain words and phrases like "THE" or "AND" occur far more often than one would expect by chance.

For example, if the ciphertext begins with the letters "XYZ", and if we know (or can guess) that the first word of the plaintext might be "THE" and that the first cipher disk might be disk 1, then it's easy enough to locate the letters "X" and "T" on disk 1 and see which other disks have "Y"/"H" and "Z"/"E" at the corresponding positions.  If we find two such disks — say, disks 4 and 7 — then we can guess with a pretty good confidence that the first three disks in the key may be 1, 4 and 7, and proceed further from there; if we don't, then one of our guesses must be wrong, and we may e.g. try another disk for the first letter and see if that yields a solution.

(The attack described above assumes that the alphabets on the disks are known.  If they're not, a similar attack can still be carried out, based on repeating patterns in the ciphertext where the same word at the same position just happened to be encrypted with the same row, although it will require a lot more ciphertext and effort to succeed.  Even so, such an attack is still a lot more efficient than brute force enumeration of all the possible alphabets on each disk.)


How to construct a hash function into a cyclic group such that its discrete log is intractable? From the Linkable Ring Signatures paper:

  Let $G = \langle g\rangle$  be a cyclic group of prime order $q$ such that the underlying discrete logarithm problem (DLP) is hard. Let $H_1 : {0, 1}^∗ \to \mathbb Z_q$ and $H_2 : {0, 1}^∗ \to G$ be distinct hash functions viewed as random oracles. Assume that for any $\alpha\in\{0, 1\}^*$, the discrete-log of $H_2(\alpha)$ to the base $g$ is intractable.

For that, as suggested on my previous question, I'll pick a large Sophie Germain Prime $q$ such that $2^{q} \bmod {(2q+1)} = 1$, with $2$ as the group generator. It would be tempting to define $H_2(a) = g^{H(a)}$, where $H$ is a hash function distinct from $H_1$. That would not work as intended, though, because, under that construction, $log_g(H_2(a)) = H(a)$. How can I, thus, construct an appropriate definition for $H_2$ on that problem?

The obvious way to create such a hash function would be to first define a hash function $H$ (distinct from $H_1$) that generates as output an integer in the range $[2, q]$, and then define $H_2(x) = H(x)^2 \bmod (2q+1)$ (that is, square $H(x)$ modulo $2q+1$).

If we treat $H$ as a random oracle, then $H_2(x)$ is a random element (uniformly distributed, other than 1) of the subgroup of $\mathbb Z^*_{2q+1}$ that consists of quadratic residues. We can see this is a random element because each possible value of $H(x)$ yields a distinct quadratic residue, and there are $q-1$ subgroup elements (other than 1), and so each output is generated with equal probability.

This subgroup is the order $q$ subgroup has that you're thinking of, and if the DLP is hard, then it's hard to solve DLP on random elements.


Breaking keyed hash function with half-randomized input Let's say we have keyed hash function which transforms $256$-bit input into $256$-bit output and the attacker knows the key (let's say the key is $256$-bit long). Now let's consider we will construct an input block as:

$128$-bit message (first bits),
$128$ random bits (last $128$ bits).

Now output could be kind of randomized. I think there is no way to find the $128$-bit message. Am I right? Is the message safe in this case?

If we consider the keyed hash function with $\ell=256$ keyspace than we can formalize as
$$H(k,m): \{0,1\}^{\ell} \times \{0,1\}^{256} \to \{0,1\}^{256}$$
Now assume that $H$ is a Cryptographically Secure keyed Hash function. That hash has pre-image, second pre-image, and collision resistance. The cryptographic strength of this hash functions is like the HMAC, the strength depends upon the size of the secret key that is used. Assuming that we have good enough key size from brute force $\ell > 128$ and the $H$ has no other weakness.
Now, assume that the attacker knows the key, in this case, it is just a usual hash function.

I think there is no way to find the 128-bit message. Am I right? Is the message safe in this case?

To find the actual message, the attacker needs to execute a pre-image attack. That has a cost of $\mathcal{O}(2^{256})$ since the attackers know the key. The pre-image attack can return an input $x$ such that $H(x) = target$ and the $x$ can be different than the 128-bit message or it can return many messages that one is the target.
The attacker has a better way since the input is 128-bit. They can search for the 128-bit. 128-bit is still beyond the search and considered secure. The collective power of Bitcoin miners can reach $\approx 2^{92}$ in a year, and one still needs $2^{36}$ years to reach a 128-bit search. In this calculation, the random 128-bit is discarded since it is not part of the security. If the random is considered secret (it shouldn't), then the attacker's job is just the pre-image.

Now output could be kind of randomized

We expect from the hash function to have avalanche criteria that is a bit change in the input should flip each output bit with 50% probability. The avalanche criteria is an important design criterion since if a few bit changes it may easier to find some collisions.
A special note: fixing a key to a keyed hash functions need a special analysis. Some keys can turn the hash function into a weak hash function. Since we don't know the hash function and the key we can not talk about this.


Use RSA keys to derive AES key I have 2 end points where I would like to derive the same AES key.

Every end point has its own RSA key pair and RSA public key from the other end point, and I would like to combine them somehow on both sides to derive the same symmetric key. How it can be used to derive AES key with the same value on both sides?

I am looking for something like ECIES-KEM but for RSA.

EDIT:

From the RSA-KEM as suggested from Wiki:
I have on endpoint A private key SK_A and public key PK_B. On the end point B I have private key SK_B and public key PK_A. As I understand the end point A should generate random m, where 1 < m < n. Then the m should be encrypted on end point A with PK_B and sent to end point B.

After that, both end point would be able to derive the same AES key using m and KDF. Is that correct?

With RSA-KEM,* the sender knows a modulus $n$ and a public exponent $e$, and the receiver knows the private exponent $d \equiv e^{-1} \pmod{\phi(n)}$.  To send a message $m$, the sender picks $0 \leq x < n$ uniformly at random, derives $k = H(x)$ for some hash function $H$, computes $y = x^e \bmod n$, and transmits $y$ alongside the authenticated ciphertext $c$ (e.g., AES-GCM) of $m$ under the key $k$.  The receiver recovers $x = y^d \bmod n$, recomputes $k = H(x)$, and recovers $m$ from $c$ using the key $k$.

This protocol is non-interactive in the sense that the sender can package up $(y, c)$ and send it off to the receiver.  There's no authentication of the sender built into the protocol; if you want the receiver to be able to verify which sender sent it, the sender could sign the message $(n, e, y, c)$ giving a signature $s$, and transmit $(y, c, s)$.†

However, like ECIES-KEM, this protocol does not provide a static shared secret between the sender and receiver using their long-term key pairs.  In contrast, in Diffie and Hellman's seminal 1976 public-key cryptosystem, Alice publishes $g^a$ in the telephone book, Bob publishes $g^b$ in the telephone book, and their static shared secret is $g^{ab}$.

This protocol also doesn't provide is deniability—the signature $s$ can be verified by a third party.  In contrast, the Diffie–Hellman public-key cryptosystem does provide deniability because any authenticated ciphertext sent between Alice and Bob under a key derived from their static shared secret $g^{ab}$ could have been created by Alice or Bob: in a symmetric cryptosystem, the power to verify is also the power to forge.

* I would say that this is the RSA analogue of ECIES-KEM, but if anything, I would guess that ECIES-KEM as a concept came after and in response to RSA-KEM as a concept!

† Signing the recipient's key $n$ and $e$ in addition to the ciphertext thwarts Don Davis's misattribution attack on PGP and S/MIME.  If you use the signing key for multiple purposes or contexts, you should make sure to identify the purpose as part of the message you are signing so that a signature used for one purpose can't be abused for an unintended other purpose.  This is sometimes called ‘domain separation’.