Brute force attack on RSA - success criteria? In a hypothetical discussion we ended up with a concrete question I'd like to find the answer to:

If you try to brute force an RSA encryption, but the original vale which was encrypted was just random binary data, can you ever be sure you found the correct key? In other words: What are the success criteria for RSA brute forcing?

Do "you" say "This is neither a text encoding I know nor a file format I recognize, so this isn't the correct key" and try the next? Or can you tell by metadata or something that you've found the correct key? Or is it safe to say that completely random data encrypted with RSA is unbreakable by brute force?

Well, typically for RSA, we have the public key.  That makes the verification process easy:

If you're trying to guess the private key (factoring or equivilent), that's easy; you just verify the factorization; "does the two primes we get, multiplied together, give us the modulus in the public key?"
If you're trying to guess the padded plaintext that corresponds to a ciphertext, that's easy; you encrypt the padded plaintext with the public key, and if it results in the ciphertext, you guessed it correctly.  Note that, for nondetermanistic padding methods (which is what ought to be used for RSA encryption), you have to guess the nondetermanistic padding bytes as well as the message bytes.
If you're trying to forge an RSA signature, that's easy; you just verify the forgery with the public key.


Can we assume that a hash function with high collision resistance also means a highly uniform distribution? I want to use a hash function to generate a random sequence from number 0-n. And so I would like to find a good function that results in values that are seemingly random (does not need to be secure), but gives a sequence that is uniformly distributed.

Can I look at a function that has the property of high collision resistance and expect that it would also have a highly uniform distribution?

Define $H(x) = \operatorname{SHA-256}(x) \mathbin\| 1$; that is, append a single 1 bit to SHA-256.  Can you find a collision under $H$?  Does $H$ have anything resembling uniform distribution?

This counterexample is not merely pathological; designs like Rumba20 and VSH provide collision resistance but neither preimage resistance nor uniformity.

That said, typical ‘cryptographic hash functions’ like SHA-256, BLAKE2b, and SHAKE128 are designed for collision resistance and preimage resistance, and more broadly for random oracle modeling (barring length extension attacks on SHA-256), meaning that the outputs on distinct inputs can reasonably be modeled as independently uniformly distributed.

In the dark ages of the early '90s, when the United States still banned the export of cryptography as a munition, the ban covered encryption, per se, like DES—but had an explicit exception for authentication (22 CFR §121.1(XIII)(b)(1)(vi), since rescinded), and so the hash function Snefru was allowed to be published and exported.

A grad student named Dan pointed out in 1992 that you could use Snefru as a subroutine in an otherwise cryptography-free program to encrypt messages.  When he informed the United States Department of State of his remarkable discovery, and asked them to confirm his understanding that publishing his cryptography-free program together with the exempted Snefru would not fall afoul of the export controls, they were not amused.

The State Department's lack of humor led to a nearly decade-long court battle, Bernstein v. United States, about whether the regulations in 22 CFR §§120–130 and 15 CFR §§730–744 prohibiting the export of encryption software constitute prior restraint in violation of the First Amendment to the United States Constitution.  Eventually, the United States federal government, backed into a corner by an annoying grad student, relaxed the regulations and the case was dismissed.

Today, a newer incarnation of the same idea—using a hash function, ChaCha, together with a method inspired by the advanced technology of the one-time pad (also known in some circles as ‘xor’), to encrypt messages—protects the confidentiality of probably petabytes of data daily on the internet, in the form of the ChaCha/Poly1305 cipher suites in TLS.

But collision resistance is neither necessary—indeed, it is well-known that ChaCha is not collision-resistant—nor sufficient—as Rumba20 and VSH show—for indistinguishability from uniform random, which is what one needs for, e.g., a one-time pad to get any security.

P.S.  If you do use a hash function, e.g. generating the sequence of bits $H(k \mathbin\| 0)$, $H(k \mathbin\| 1)$, etc., and want to use that sequence of bits to choose an integer $x$ with $0 \leq x < n$ uniformly at random, make sure to do rejection sampling to avoid modulo bias if $n$ is not a power of two: if $H$ returns a string of $t$ bits interpreted as a $t$-bit integer, and $H(k \mathbin\| i)$ is below $2^t \bmod n$, reject it and try $i + 1$; otherwise return $H(k \mathbin\| i) \bmod n$


What is the prp-advantage of a $2^{80}$-time adversary attacking AES-256? I am somewhat confused with something I read in Dan Boneh's slides discussing the advantage of a $2^{80}$-time adversary attacking AES-256; according to Boneh, the assumption is that this advantage is bounded by $2^{-40}$ (see slide 8 here or fast forward to 7:04' in the video here).

I have been looking to a few lecture notes (e.g., Goldwasser-Bellare, pg 72, section 5.5 at cseweb.ucsd.edu/~mihir/papers/gb.pdf) and books (e.g., Boneh-Shoup cryptobook draft 0.3 chapter 4, the katz-lindell book, or the handbook of applied cryptography chapter 7), but I am still unsure about this bound. It seems unrelated to quantum attacks on the key, which may justify a square root on $2^{80}$; however, an exhaustive search for AES-256 keys should take $2^{128}$ steps on a quantum computer.

In addition, it doesn't seem to be related to the birthday paradox either. Most birthday attack related bounds in the aforementioned references were linked to a mode of operation (for example, CTR-mode attacks related to the number of blocks encrypted under the same key), proofs related to PRFs, etc. What I find confusing is the connection between the time complexity of the adversary and the PRP advantage bound, as the attack that distinguishes the PRP from a truly random permutation is unclear.

Is the $2^{-40}$ advantage assumption accurate? If so, how is it explained? Why the adversary is getting this advantage after all?

You misunderstood what Dan Boneh was trying to say. There is no known attack on AES256 that comes even close to this complexity. However, if there was a known attack that came close to this, then it would be very unwise to assume that this is the best attack. When formalizing an assumption, one needs to be conservative relative to what is known. Thus, Dan was giving an example of how one could formulate a conservative assumption about AES, and he was being very conservative (which is a good thing).


Is there a standard one way function that does not produce collision Is there any standard or accepted one way function that does not produce collisions? I'm not looking for hash functions.

Does that make sense at all? for example given string with length n, the function will always output same obfuscated string that is not possible to reverse engineer. something that is mathematically one way function but also doesn't produce collision.

So I don't want to store the actual input, but just a successor of input that cant be decrypted at all, this will be used only to see if duplicate input is received or not.

With a fixed length output (ala today's hash functions)?  No.

You cannot map an infinite space to a finite space, no matter how vast that finite space may be, without the possibility of collisions.


Elliptic Curve-based Diffie Hellman: How is the shared key (mnp) calculated? It's a very quick question, but I couldn't find the answer from the sources I have.

I've been coding EC based D-H key exchange, and I'm almost done with it.

So here's what I've understood so far.

Michael and Nikita agree on an Elliptic Curve $E:y^2=x^3+ax+b $, a prime number $p$, and a point $P$ on $E$ over $Z/pZ$.
They choose their secret numbers $m$ (for Michael) and $n$ (for Nikita).
They exchange $mP$ and $nP$, each calculated by adding $P$ to itself $m$ and $n$ times over $E$ in $Z/pZ$. (I understand how the "addition" works)
Now by using the $mP$ or $nP$ they got from each other and the secret number they chose ($n$ and $m$) to calculate the shared key $mnP$.

So my question is, how do you calculate $mnP$? No source I have specified what exactly it is, so I'm not sure if it is $(m \times n)P$ or $P$ added $n$ times to $mP$.

Thanks in advance!

So my question is, how do you calculate $mnP$?

For Michael, he takes the value $nP$ he received from Nikita, and adds it to itself $m$ times; that is, it's $\underbrace{nP + nP + \dots + nP}_\text{$m$ times}$, that is the value $m(nP)$.

And, of course Nikita takes the value $mP$ he received from Michael, and adds it to itself $n$ times; that is, it's $\underbrace{mP + mP + \dots + mP}_\text{$n$ times}$, that is the value $n(mP)$.

And, because we perform these operations in a mathematical group (that is, associativity holds), we have $m(nP) = n(mP) = mnP$, so they come up with the same value.


Explain: An NTRU key for a lattice of dimension $d$ has size only $O(d\log{d})$ The associated NTRU lattice is of dimension $d=2N$.
The public and private key sizes are both of length $O(N)=O(d/2)=O(d)$.

So where does the $d\log(d)$ appear?

Thanks in advance.

An NTRU public key is a polynomial of degree $d-1$ whose coefficients are elements in $\mathbb{Z}_q$.  So the number of bits you need to represent it is $d\log{q}$.  If q is of the same order as d, then this gives you $d\log{d}$.  The private key, on the other hand, can be represented with $O(d)$ bits since the coefficients are all in the set $\{-1,0,1\}$.


Relying on a 4-bit S-box instead of an 8-bit one I've discovered that generating good S-boxes with only modular addition, bitwise XOR, bitwise AND, bitwise OR, bitwise NOT, rotations, and, shifts is difficult. I figure that using them to make a good 4-bit S-box will be easier. But, does using a 4-bit S-box instead of an 8-bit one degrade security by a large margin?

While an ideal 4x4 s-box will have less ideal properties compared to an ideal 8x8 s-box, you can make up the difference with more applications of the smaller s-box.

As an example, the worst differential in the AES s-box is 4/256, or 1/64. If your s-box only has 16 entries, you clearly cannot obtain an entry nearly so low as 1/64 - the lowest possible entry is only 1/16 in the smaller s-box (neglecting the need for uniformity). But if you apply your smaller s-box repeatedly, you can see that the overall probability can be made to be equivalent.

Note that the design of 4x4 s-boxes is basically a solved problem - there are multiple papers out there that have already searched through all possible 4-bit mapping and found the s-boxes with optimal properties that can be implemented in a minimum number of instructions from among all 4x4 s-boxes.


What is the purpose of salting when integrating PBKDF2 with AES? I'm a bit new to cryptography and I'm trying to wrap my head around PBKDF2 and AES. As a disclaimer, this is not going to be used in an actual application, I'm just testing things locally as a fun side project.

Right now what I'm trying to do is accept a password from someone to encrypt a message, and decrypt it at a later time.

I was doing the following:

    key = InputPassword()
    salt = RandomSalt()
    self.key = PBKDF2(key, salt, 16)

I would then encrypt with AES. At the later time point, I would run:

    key = InputPassword()
    salt = RandomSalt()
    self.key = PBKDF2(key, salt, 16)

again. Of course, my salt is going to be different each time. The problem seems to be that when the salt is different, AES decryption does not work. Am I therefore supposed to include the salt in the encrypted message? For example send something like: "message = message, salt=salt"? If so, what is the purpose of the salt, and what security benefit does including it confer?

One reason is to mitigate from the Rainbow tables which is the work of  Oechslin. If everybody uses the same salt, one can build a Rainbow table for cracking everybody's passwords. There are even commercial tables for sale (I'm not advertising them just providing the existence). Using the salt for key derivation and passwords simply kills the usage of Rainbow tables. Rainbow tables are still useful if there is a multi-target attack, especially for block-ciphers.
The other not good reason is deriving two different keys by just one password. For example, if you want to encrypt with AES and then HMAC, you will need two keys. By using two salts you can get two keys. The below is from Crypto module of Python.

$$\operatorname{PBKDF2}(password, salt, count, dkLen, prf)$$

The iteration (count) should be larger than 16 to make harder the job of passwords crackers like hashcat. 65536 or depending on the user experience, waiting more than 1 seconds may not be a good experience so you can adjust it according to the system.
dkLen is the derived key length with default. It can be increased upto $2^{31}-1$ times the output size of the hash function. You can increase it to derive AES and HMAC key with one salt or you can use domain separation with two salts.
Actually, for deriving Multiple Keys can be risky with PBDKF2, once your password is found the two keys are gone. You can use PBKDF2 to generate a key and then use KDF like HKDF, rfc5869
$$key = \operatorname{PBKDF2}(password, salt, 65536, dkLen, \operatorname{SHA256})$$then use the key with HKF for different contexts with context

$$\operatorname{AES-KEY} = \operatorname{HKDF-Expand}(key, \text{"aes-key"}, 128)$$
$$\operatorname{HMAC-KEY} = \operatorname{HKDF-Expand}(key, \text{"hmac-key"}, 256)$$
In this case, you don't need the Extract mechanisms of HKDF, PBKDF2 does it.

If you want to send an encrypted message to someone then the generated key must be sent. For this kind of problem, we have a better alternative like DHKE, libsodium crypto box, or RSA-KEM which are based on public-key cryptography. In RSA-KEM we don't use PBKDF2 to derive a key we use KDF like KDF1 or HDKF.
PBKDF2 can be used in the protection of passwords in the login systems or key generation like in Veracypt, disk encryption utility. Veracypt can use the PBKDF2 with RIPEMD160 hash function to derive a Key Encryption Key to decrypt the actual encryption key. The iteration is 327661 for system partitions and 655331 for other containers. In order to, access the files again yo need to use not only your password but also the same parameters; salt, and iteration count. Otherwise, you cannot access the encrypted files. The Veracrypt handles the parameters for you, they are not kept as secret!

The new alternative for PBKDF2 is the Argon2 which is the Winner of the passwords hashing competition, in 2015. Argon2 can increase the used memory during calculations that can prevent the massive parallel hash calculations with GPUs. Hashcat can calculate

1173.1 kH/s for PBKDF2-HMAC-SHA1 and
277.0 kH/s for TrueCrypt PBKDF2-HMAC-RipeMD160 + XTS 512 bit

based on Nvidia GTX 1080 hashcat performance. *

note that the salt is not secret, only your password is secret here. Once you use a proper system then the attacker's ability is guessing your password. Therefore you must use strong passwords.

* Unfortunately there is not Argon2 to compare


Why do stream ciphers like A5/1 and ZUC have "frames"? A5/1 and (I think) ZUC, both stream ciphers used in mobile telecommunications, have "frames" where the, in addition to the key, a frame number is provided to the keystream generator which produces a relatively short pseudorandom sequence called a "frame" (on the order of at most a few kilobytes).

Advancing the stream cipher requires incrementing the counter and running the algorithm again with no state carried over from the generation of the previous frame. This stands in contrast to stream ciphers like RC4, Trivium, and Grain, where the $i$th keystream bit can only be computed after generating the previous $i-1$ bits, and in contrast to counter mode and stream ciphers like ChaCha20 which are capable of complete random access.

What is the rationale behind these "frames" and why not just go for full random access if they want this?

What is the rationale behind these "frames" and why not just go for full random access if they want this?

That's because they're used in mobile communications.  There, packets can easily be dropped in transit (e.g. by a bit of electrical noise that just happens to come in at the wrong time); possibly with the receiver not even knowing that he missed one.

Because of this, it is necessary to design our crypto system to be able to decrypt even if packets are missing; using a system that can decrypt only if it has successfully received the previous packets just doesn't work.  One approach to do this is to put in a frame number; by using the frame number, the decryptor can work even if he missed some packets.

Now, you might think that we might also try to make the system reliable, by having the sender retransmit packets that the receiver didn't get (just like TLS does).  This really doesn't work out for voice communications; not only does it consume extra bandwidth (which is precious), live voice is time sensitive; if the next audio segment does come in late, the receiver can't do anything with it, and so there's no point in retransmitting it.

As for why they use serial numbers, rather than another approach (e.g. a random nonce), serial numbers are needed to tell the receiver when this segment of the voice should be replayed, and so voice communications have serial numbers in there anyways; using the same thing for two different purposes reduces on the bandwidth used (and, as I said, that's a major concern for wireless).


Why encrypting with private and public keys produce the same result? Let say $e = 5$, $n = 119$ and $d = 77$. If I encrypt, for example, $m=15$ I get:
$$m_1 = m^e=15 ^ 5 \mod 119 = 36\qquad\text{and}\qquad m_2 =m^d= 15 ^ {77} \mod 119 = 36$$. Why? Is it always like that in RSA? Is it bad?

My question was prompted by an answer to Why hash or salt when signing? : why does this work?

No, you wouldn't always get that - in fact it's very unlikely behavior (eg the wikipedia worked example).

If encrypting with the public and private exponents was always the same you'd be able to decrypt someone else's message $c$ by calculating $c^e=c^d=m$.

It is important to realize that (after running the RSA setup algorithm) there is algebraically no reason you couldn't swap $e$ and $d$, since $d=e^{-1}$ and thus $e=d^{-1}$ (all modulo $\varphi(N)$). However, it is unlikely that $m^d$ and $m^e$ would be equal.

In the question you link to, using the "wrong" exponent is done to cheat: it demonstrates a potential flaw in the encryption scheme. In the forgability game, we say the adversary 'wins' if they manage to create a pair $(m,s)$ such that $s$ is a valid signature for $m$, without asking the legitimate signer to calculate a signature of $m$.

So, consider what a valid message signature pair actually is (in textbook RSA signing): The pair $(m,s)$ is valid if $m=s^e\pmod N$. Now, since the public key is $(e,N)$, the adversary can cheat a bit. Instead of picking the message that he wants signed, he instead picks the signature. Having picked $s$, he now calculates $m:=s^e \pmod N$. This leaves him with the pair $(m,s)$, which by construction must be valid.

Notice that he doesn't have a clue what the message $m$ actually says, but we do know that $s$ is a valid signature for it. This is why real-world RSA signing uses a secure padding scheme: a message $m$ created in the way I describe above is very unlikely to have valid padding.


Help with pseudorandom functions I started a new lecture this year about crypto and I've had a few problems in the first few weeks with the exercises we got.

I would appreciate a "guide" on how to solve problems like the following one because I feel like it will haunt me later in the semester if I don't figure it out now. Please don't simply post a solution, I need to figure this one out myself.

  Let $F : \{0, 1\}^n × \{0, 1\}^n → \{0, 1\}^n$ be a pseudorandom function. Prove or disprove that this is also a secure pseudorandom function:
  $$F'(x) := F(x ⊕ 1^n)$$

Two suggestions:

Does it simplify the problem for you if you omit n? (or only consider the n=1 case)
Suppose F(x⊕1n) would not be a pseudorandom function, what does that tell you about the pseudorandomness of the original function F?


Is Schnorr's digital signature a non-interactive zero-knowledge proof? If yes, is there any paper that proves it? Unifying Zero-Knowledge Proofs of Knowledge, by Ueli Maurer, argues that Schnorr's interactive protocol is zero-knowledge. If this is true, using the Fiat-Shamir transform, can we convert Schnorr's protocol into a NIZK proof?

Yes, and in fact, Schnorr's signature scheme was originally described as a non-interactive protocol. I think the confusion around interactivity comes from the fact that the same paper first described a interactive identification scheme, which can be viewed as a specialization of the signature scheme for empty messages.
In both schemes, challenges can be generated either interactively or using hashes. The non-interactive variant can be viewed as an application of the Fiat-Shamir transform, although Schnorr did not describe it as such.
Note that while more general formulations of the Fiat-Shamir transform involve a random oracle assumption, the Schnorr signature scheme in particular has weaker requirements -- see Navel et al. and Chen et al.


Detect desynchronization in HOTP authentication In HOTP authentication, is there a way for a system to detect that the token has been desynchronized? If so how does it know that the OTP was generated from a desynchronized (but valid) token and is not just a fake/random OTP?

From RFC 4226:

  7.4.  Resynchronization of the Counter

  Although the server's counter value is only incremented after a
  successful HOTP authentication, the counter on the token is
  incremented every time a new HOTP is requested by the user.  Because
  of this, the counter values on the server and on the token might be
  out of synchronization.

  We RECOMMEND setting a look-ahead parameter s on the server, which
  defines the size of the look-ahead window.  In a nutshell, the server
  can recalculate the next s HOTP-server values, and check them against
  the received HOTP client.

  Synchronization of counters in this scenario simply requires the
  server to calculate the next HOTP values and determine if there is a
  match.  Optionally, the system MAY require the user to send a
  sequence of (say, 2, 3) HOTP values for resynchronization purpose,
  since forging a sequence of consecutive HOTP values is even more
  difficult than guessing a single HOTP value.

  The upper bound set by the parameter s ensures the server does not
  go    on checking HOTP values forever (causing a denial-of-service
  attack)    and also restricts the space of possible solutions for an
  attacker    trying to manufacture HOTP values. s SHOULD be set as low
  as    possible, while still ensuring that usability is not impacted.


What is the period of a cipher? For the following explanation of RC4:

  It is a variable key-size stream cipher with byte-oriented operations.  The algorithm is based on the use of a random permutation.  Analysis shows that the period of the cipher is overwhelmingly likely to be greater than $10^{100}$."

What does it mean by the period of the cipher and greater than $10^{100}$?

I think the 10100 is a typo and should be $10^{100}$ as shown here

The period would be something along the lines of how long until the byte stream repeats. For example if the byte stream were "ABCDABCDABCD" and so on, then the period would be 4.

For security you want a large period so that you can encrypt large amounts of data.


AES-CBC then SHA vs AES-GCM for encrypting and authenticating a web token I am trying to have something like JWT but kinda ad hoc and encrypted. The token itself is simply a stringified JSON that contains the user ID and Unix timestamp.

Now, I tried to use AES-128-GCM, however I did some simple modification in the ciphertext before decrypting, just appended some bytes to the ciphertext, and found that it decrypts successfully, does that mean that those bytes were counted as padding and that AES GCM is authenticate then encrypt algorithm?

I feel that encrypt-then-authenticate feels more secure to me. Also, is AES GCM authentication even secure enough to be compared to SHA256 for example or is it CRC tier for quick integrity and cannot be used for secure authentication like HMAC?

In other words: is AES-128-CBC then SHA-256 more secure than AES-128-GCM?

just appended some bytes to the ciphertext, and found that it decrypts
  successfully

Normally this shouldn't happen, as the appended bytes surely aren't a valid authentication tag for the previous "ciphertext". I suppose (but don't know!) the implementation you are using encoded the length of the ciphertext, the associated data and the tag and retrieved these values upon decryption, ignoring the added values, yielding a correct decryption.

  AES GCM is authenticate then encrypt algorithm? because I feel that
  encrypt then authenticate feels more secure to me

AES-GCM is an authenticated encryption algorithm. Encrypt-then-Authenticate is one specific construction that achieves this general definition and is indeed preferable to Authenticate-then-Encrypt, which is why GCM internally does encrypt-then-authenticate and so AES-GCM achieves the same security definition as CBC-then-HMAC.

  is AES-128-CBC then SHA-256 more secure than AES-128-GCM?

When you say "AES-128-CBC then SHA-256" I suppose you actually mean AES-128-CBC with HMAC-SHA256 authentication on the ciphertext.

Then yes, technically that is more secure, because HMAC-SHA256 requires $2^{128}$ operations to come up with a forgery, whereas AES-128-GCM allows you to perform a multi-target search for a key that works dropping security slightly below $2^{128}$. So it also has a serious security level unlike CRC. Also from this we can infer that both are secure, as neither $2^{128}$ nor $2^{100}$ operations are feasible making them both "secure" (a.k.a. "meh, can't break"), so you might as well use the easier-to-use and faster AES-GCM, assuming you have hardware support available, which is the case on modern x86 processors.

See Squeamish's comments below for a more detailed discussion of the actual values. Also see their answer here.


Converting a number to a member of a multiplicative cyclic group I am currently trying to make an implementation of the ElGamal encryption for educational purposes. As I understand it, when using the encryption with multiplicative cyclic groups, one generates a cyclic group for a safe private key as follows:

Find a safe prime number $p$ (of the form $p = 2*q + 1$ where $q$ is prime)
Find the generator of a cyclic group with order $q$ and modulo $p$ (i.e. a number $g$ less than $p$ such that $g^q \mod p = 1$ and $g^2 \mod p \neq 1$)

For example, for $p = 11$, we'd have $q = 5$, $g = 3, 4, 5$ or $9$, and the cyclic group would have the elements {$1, 3, 9, 5, 4$}.

Then, during the encryption stage, the one performing the encryption should convert $m$, the number representation of the message, into $m_1$, a member of this group. How is this done if $m$ doesn't belong to our group (for example, if it is $2, 6, 7, 8$ or $10$)?

If I am missing something, please tell me what did I get wrong!

Use the Legendre symbol in your case.
Explanation: when $p=2.q+1$, the order of the multiplicative group of $F_p$ is p-1=2q.
Then there is no other alternative, when you select a random number, it could be a quadratic Residue with probability $\frac{1}{2}$.
The legendre symbol of any number a, is : $a^{\frac{p-1}{2}}=a^{q}=\pm 1$

Then except the number 1, all the other quadratic residue (Legendre symbol is 1) have order q.


Key expansion for cryptographic keys I have seen some applications use key expansion when deriving AES-keys.
E.g. the application will generate some random data (e.g. 128bits), then use PBKDF2 to expand it into 512bits (2x256 keys).

Why go through this process of taking a small amount of random and expanding it, instead of taking 512bits cryptographic randomness directly?

The random 'seed' value is not stored either so it can be reused for the key expansion.

The main reason is that true random data is hard to obtain; whether it is from:

A user's password since people only remember them so long
Or from a random source such as an operating system that reads random measurements like disk latencies since it can only produce so much randomness per unit time.


Huffman coding is a prefix code, proof How would you prove that Huffman coding $C$ is a prefix code, i.e $$\forall x,y \in C,\  \forall z \in \lbrace 0,1\rbrace^*,\ x\not=y||z$$

Using induction according to the number of items to code? The base step would be easy, but I don't know how to prove the inductive step.

Let $T$ be an optimum prefix code tree, and let $b$ and $c$ be two siblings at the maximum depth of the tree (must exist because $T$ is full). Assume without loss of generality that $f (b) \le f(c)$ and $f(x) \le f(y)$ (if this is not true, then rename these characters). Since $x$ and $y$ have the two smallest frequencies it follows that $f(x) \le f(b)$ (they may be equal) and $f(y) \le f(c)$ (may be equal). Because $b$ and $c$ are at the deepest level of the tree we know that $d(b) \ge d(x)$ and $d(c) \ge d(y)$.
Now switch the positions of $x$ and $b$ in the tree resulting in a different tree $T′$ and see how the cost changes. Since $T$ is optimum,

$$\begin{align}
B(T) &\le B(T′) \\
&= B(T) − f(x)d(x) − f(b)d(b) + f(x)d(b) + f(b)d(x) \\
&= B(T) − (f(b) − f(x))(d(b) − d(x)) \\
&\le B(T)
\end{align}$$

Therefore, $B(T′) = B(T)$, that is, $T′$ is an optimum tree. By switching $y$ with $c$ we get a new tree $T ′′$ which by a similar argument is optimum. The final tree $T′′$ satisfies the statement of the claim.


Simplifying the description of the Keccak padding rules I would like to check if my following understanding of Keccak padding has any flaws and if there are, please feel free to point them out and correct them.

The Keccak version I am interested is the original Keccak with 256 bits output (not the SHA3 from NIST).

It has a bitrate of 1088 bits and a 256 output bits.

Assuming that a Keccak function operation has a absorbing phase followed by a squeezing phase, Keccak-256 would require 136 bytes (1088 bits) of memory space to compute on for every absorbing phase.

During the absorbing phase, a part of the input message of 136 bytes of length would be copied into the computation states (blocks/lanes ..etc..). If the copied message into the states are insufficient, a padding has to be applied otherwise if the message states are sufficient (exactly 136 bytes), nothing has to be done.

When padding occurs on the bit level, it will begin with bit 1 followed by a string of 0 until finally the last bit is also a 1 for the original Keccak-256.

I would like to know the flaws of my above description and what are the correct description in a very simply and easy to understand manner I should approach it from.

According to Keccak submission 3rd document on page 10, the padding scheme changed from round 2 to round 3.

  We shortened and simplified the padding rule. The new padding rule is the pad10∗1
  rule

In the original specifications on page 3;

  $\texttt{pad}(M, n)$ returns a bit string obtained by appending to the bit string M a single 1 and
  the smallest number of zeroes such that the length is a multiple of n.

In Sponge Construction Functions, The Keccak team  proved that both satisfies

  the sponge construction offers protection against generic attacks if the
  padding rule is sponge-compliant, i.e., it is injective and ensures that the last block is different from the all-zero block

They changed it because of this rationale:

  pad10∗1 is simpler to describe and to implement than the rounds 1-2 padding rule

In Short, Keccak padding rule evolved during the submissions.


What are words in a HASH algorithms From wikipedia: "They differ in the word size; SHA-256 uses 32-bit words where SHA-512 uses 64-bit words."

In this context what do they mean with words? is it the same as a 32 bit (or 64 bit) block in a block cipher? just simply the size in which it divides up it's input?

Word size is not a term originating in cryptography. Rather it is a term which came from the area of computer architecture. Here it specifies either how many bits are transferred over a bus at a time or the size of a register.

When used in the description of cryptographic primitives (such as a compression function or a block cipher), it covers the size of the variables in the definition of the primitive. Ideally these variable sizes line up with the register size of the CPU they are going to be executed on.

In case of the SHA-2 family, the internal state is always 8 words, and the block size is always 16 words. The word size is either 32 bits or 64 bits.

This is why on a 32 bit CPU SHA-224 and SHA-256 are faster than the other variants, but on a 64 bit CPU they are slower than the other variants.


Attacking Double DES (OFB Mode) given the initialization vector and not much else? I'm given a Plaintext/Ciphertext pair, a Ciphertext to break, and the IV. One thing of note is that the same IV is used for both DES Encryptions, so $$C = E_{K_2}(E_{K_1}(P, IV), IV)$$ I have limited resources, so brute-forcing a Meet-in-the-Middle attack of complexity $2^{56}$ is unfeasible. What other options do I have for attacking OFB Mode?

EDIT: It has now been revealed to me that both $K_1$ and $K_2$ are weak keys. Hopefully this gives enough info to crack it, however I'm unfamiliar with how to approach weak keys, what do I do with them?

Read up on weak keys on Wikipedia.

The weak keys are the ones that result in the left and right key halves at the output of the Permuted Choice function being either all 1's or all 0's. So you can test all possibilities for weak keys to break the OFB mode.

What is more, if weak keys are used DES becomes idempotent, thus double encryption gives the plaintext back. This, however, would normally only work in ECB mode.


Why would one choose DTLS-SRTP versus just RTP over DTLS? If I understand DTLS-SRTP correctly, DTLS is used to exchange keys and then the endpoints switch to SRTP for encryption. What is the benefit of this setup versus just sending RTP over DTLS? Is it just about compatibility with existing SRTP stacks?

It's all about encryption overhead; how much the extra data the encryption method extends the packet by.

DTLS has a noticeable amount of overhead; the DTLS header alone is 13 bytes, and then you have the IV/nonce, and the tag; this overhead can be more than the actual VoIP payload.  In contrast, SRTP was specifically designed to minimize this overhead; except for the tag (which is optional; IMHO, bad idea to omit it, but some people insisted), there is no overhead compared to RTP.

You might ask "what's the big deal about encryption overhead?  Doesn't the internet not care that much about packet sizes?"  Well, yes, if you're talking about wired internet connections, actually, this overhead might not be that significant.  However, for wireless, yes, people do worry about it, because:

Because of power; the more bytes you have, the more bytes need to be transmitted (and if you're on a battery, well, that's a concern)
Because wireless is a shared media, so the more bytes you broadcast, that's less bandwidth everyone else connecting to the same AP gets.


Maximum steganographic embedding rate not detectable by steganalysis? When using advanced steganographic methods (like F5) what is the approximate maximum embedding rate when advanced Steganalysis (like a machine learning approach) can no longer reliably detect it?

I have searched for papers dealing with this topic but have been unable to find any. Does anyone here know anything about this topic or any research papers dealing with this issue?

It is an interesting question, let me clarify some points before.

Nowadays F5 can not be considered an advanced steganographic method. There are algorithms as for example HUGO[1] or WOW[2] that are much harder to detect. Usually these algorithms hide information in the bitmap. F5 hide information in the DCT coefficients and this is easier to detect. Therefore, let's assume that we are using one of these modern algorithms.

Almost every research in modern steganalysis is based on machine learning. The common framework can be found in [3] and uses a feature extractor called Rich Models and Ensemble Classifiers. Using this framework (or reading this paper and other papers dealing with the same issues) you can find a first answer. An example result could be about 80% of accuracy using HUGO with bitrate 0.40. Maybe HUGO with a bitrate around 0.20 or 0.10 can be acceptable for you.

There are a lot of similar papers with different techniques and different results, getting better in recent papers. But there exist an important problem in steganalysis: the Cover Source Mismatch (CSM). It is, in fact, a problem of machine learning called "domain adaptation" with a new name [4,5]. It refers to the problem of using the classifier with images from a different source from those with which it has been trained. Unfortunately, we never known the source or domain of the steganographer, so we always have the CSM problem. And this worsens the results.

If you take into account the CSM problem you will see that the results presented in some papers may be a little bit confusing. So, if you see something similar to my previous example (HUGO 0.40 with 80% of accuracy) you can not consider that HUGO 0.40 is insecure because if you have no access to the camera used by the steganographer, you can not train your classifier properly. Currently the CSM problems is an active area of research.

At this point, reading the referenced papers, we have the optimistic answer (it will be for example 0.20/0.40 using HUGO) because the CSM problem and the cautious answer (it will be for example HUGO 0.10 or lower).

[1] Pevný, T., Filler, T., Bas, P., 2010b. Using High-Dimensional Image Models to Perform Highly Undetectable Steganography. In: Information Hiding - 12th International Conference. pp. 161–177.

[2] Holub, V., Fridrich, J. J., 2012. Designing Steganographic Distortion Using Directional Filters. In: International Workshop on Information Forensics and Security (WIFS). IEEE, pp. 234–239.

[3] Fridrich, J., Kodovský, J., 2012. Rich Models for Steganalysis of Digital Images. IEEE Trans. Information Forensics and Security 7 (3), 868–882.

[4] Cancelli, G., Dorr, G., Barni, M., Cox, I. J., 2008. A Comparative Study of ±1 Steganalyzers. In: Multimedia Signal Processing, 2008 IEEE 10th Workshop on. pp. 791–796

[5] Ker, A. D., Bas, P., Böhme, R., Cogranne, R., Craver, S., Filler, T., Fridrich, J., Pevný, T., 2013. Moving Steganography and Steganalysis from the Laboratory into the Real World. In: Proceedings of the First ACM Workshop on Information Hiding and Multimedia Security. ACM, pp. 45–58.


The security of the AES secret itself I am writing an application, running on a server, where multiple users access data from a database which is AES encrypted with a master secret. The master secret itself is initially randomly generated, and then AES encrypted with a user-secret to yield a 'user-hash'. The master secret is never stored, but the user-hash is stored in a database.
When a user enters his user-secret, the user-hash is decrypted to temporarily (on the fly) yield the master-secret which is used to decrypt the data. The data is then send to the user.

If a user is deleted, the user-hash is deleted. He may have saved decrypted data, but cannot decrypt further data.

The question is: How safe is the master-secret in this constellation? If the database is compromised, an attacker has access to the user-hash and the encrypted data. If the attacker was a user, he may also have decrypted data. Will he then be able to break the master-secret?

If a user has a copy of both the encrypted and decrypted data, he is in a position to perform at least a known-plaintext attack. If users can submit arbitrary plaintexts for encryption, they can conduct a chosen-plaintext attack, which is stronger. In a chosen-plaintext attack, the attacker can submit any number of plaintexts and can retrieve the corresponding ciphertext.

All reasonable encryption algorithms are resistant to chosen-plaintext attacks, and AES is considered a reasonable encryption algorithm. Someone in possession of some (plaintext, ciphertext) pairs cannot encrypt or decrypt other messages (except sometimes messages derived from the known messages if a bad mode is used). In particular, no matter how many known plaintexts and ciphertexts the attacker is, he has no method to obtain the key that is better than brute force (trying all possible $2^{128}$ keys).

Do note that deleting the private secret does not delete the master secret. The master secret can still be recovered from backup copies of the private secret that weren't deleted, from other users' private secret, or from extant copies of the master secret.


AES speed compared to permuted LCG What is the speed of AES and how to estimate it well? Here:
https://security.stackexchange.com/questions/92074/aes-algorithm-encryption-time
they wrote it could be 700 MB/s. But here:
https://www.cse.wustl.edu/~jain/cse567-06/ftp/encryption_perf/index.html
Abdel-Karima Al Tamima estimated it is about 50 MB/s. Why are there such differences? Is it because of some kind of hardware acceleration? I'm trying to compare it to PCG generators:
https://www.pcg-random.org/paper.html
Just to compare what is faster in generating pseudorandom numbers (I know that PCG is not cryptographically secure and it is not a cipher). For example 128-bit PCG XSL RR RR can proceed about 65 GB/s (it was probably implemented in numpy of Python). Is it comparable to 50 MB/s or 700 MB/s?

AES is generally very fast when implemented in hardware.  On my laptop, a Core i7 8665U, AES-128 operates at 6758 MB/s.  It is slower when implemented in software, and it is much slower when implemented in software in a constant-time implementation.  A naive software implementation that is not constant time runs as 367 MB/s on my system.
You mentioned that you're looking for smartphone processors.  Some of the newer processors will have AES acceleration available, but not all will.  If you're looking for an algorithm that will perform well on almost all systems, be constant time, and cryptographically secure, I'd recommend ChaCha20, or, if you really need screaming performance, ChaCha12.  ChaCha20 on my system runs at 3513 MB/s and will clearly outperform AES where hardware acceleration is not present.  ChaCha12 performs almost as well as or better than many non-cryptographic PRNGs.  It would be my choice for a PRNG, whether cryptographic or non-cryptographic, because it is fast, secure, and has no weak seeds (unlike many non-cryptographic PRNGs).  It is also the default PRNG for the Rust rand family of crates, and ChaCha20 is used in the Linux kernel to generate random numbers.
Note that any performance comparison of PRNGs also has to consider not just generating the values but getting them into a place where they can be used.  For example, AES-NI instructions would probably perform even better than I listed above if you only encrypt the same data in place using vector registers.  However, the performance drops off when you must load and store data to and from memory because that is more expensive.  I suspect the PCG paper does not take that into account in a practical way.
Of course, performance measurements on my system are not reflective of other systems and if you need to know how things work on a particular system, you should benchmark it yourself.  You may also want to look at SUPERCOP, which benchmarks many cryptographic primitives on various types of hardware to answer your questions.  It's likely that you'll find hardware that is comparable to modern and older processors, including a variety of ARM and ARM64 hardware.
A final note about performance: you don't always need to use the fastest algorithm for a job.  It is likely that in most applications, the generation of random numbers is not the bottleneck, and the benefits of using an algorithm like ChaCha (such as its lack of weak states and better quality) may outweigh the fact that it is slightly slower.  Your benchmarking would need to focus on identifying places that are a bottleneck, and improving those whenever possible.


CBC-MAC for Arbitrary Length Messages Katz/Lindell propose the following modification to the basic CBC-MAC scheme to handle variable length messages (p.125):

  We sample two uniform independent keys $k_1, k_2\in \{0,1\}^n$. Then to authenticate a message $m$, we first compute the basic CBC-MAC of $m$ using $k_1$ and call the resulting tag $t$. Then we let the output tag be $t' = F_{k_2}(t)$.

My question is why do we need to use two keys? That is, why is the scheme insecure if we compute the output tag $t'$ using $F_{k_1}$?

That is, why is the scheme insecure if we compute the output tag $t'$ using $F_{k_1}$?

Computing $F_{k_1}( \text{CBCMAC}_{k_1}(M))$ is precisely equivalent to taking the padded message $M$, appending an all-zero block to it, and then preforming the CBC-MAC on it (sans the padding operation).

Here's how an attacker can exploit that to break the MAC scheme, given the restriction that all messages presented to CBC-MAC has an all-0 block at the end:

First, ask for $a = \text{CBCMAC}_k(M_1 || 0)$, and $b = \text{CBCMAC}_k(M_2 || 0)$

Then, we know that $\text{CBCMAC}_k(M_1 || 0 || u || 0)$ and $\text{CBCMAC}_k(M_2 || 0 || u\oplus a \oplus b || 0)$ are the same (for any single block $u$); this happens because, when the two MACs xor in the $u$ or the $u \oplus a \oplus b$ blocks, then both set their internal states to $u \oplus a$, and all other processing is identical past that point.

So, the attacker asks for one, and he then knows the MAC of the other.


why hash(hash(str)) is bad? Why do people say that using hash twice or more is bad? yes there is key derivation that do that job, but in a low bandwidth network countries, the solution i see is to use a simple hashing system on the  server to gain one second or two.

Is rainbow table effective when using more than one hash? because on internet, i only find MD5 or SHA tables, so i guess that the algorithm will work only on hash(str) and will not work on hash(hash(str)) ?

This call for a few different answers.

First concerning any rainbow table or similar approach, nothing prevents you from defining $HH(x)=H(H(x))$ and then to apply the desired method to the composed function $HH$. Even if $HH$ has slightly different properties from a usual hash function (see below), this will still work fine. So you gain no additional protection here.
If you are concerned by collisions, you should be aware that the probability of collision is slightly higher with a repeated hash, indeed, a collision $HH(x)=HH(y)$ with $x\neq y$ may arise in two different ways (either $H(x)=H(y)$ or $H(x)\neq H(y)$ and $H(H(x))=H(H(y))$. This almost doubles the probability of collision for a given pair $\approx 2^{1-h}$ instead of $2^{-h}$.
If you want to consider a more theoretical approach, you should look at To Hash or Not to Hash Again? (In)differentiability Results for H^2 and HMAC (http://eprint.iacr.org/2013/382), which shows that $HH$ is not indifferentiable from a random oracle.


Overdeterminate system of multivariate equation If I have a random too way overdeterminate systems of homogenous non-linear equations and few variables, What's the better way too find a solution, finding a the Groener Basis or just using linearization ?

Thanks

I think this is better suited to be a question on the MSE site. However, I will answer it.

The first thing is that if your system is random, then the chances it admits at least one solution are extremely small, and it therefore does not make too much sense to "solve" the system. On the other hand, if you already know in advance that your system has a solution (for instance, the system arose by evaluating a value at some polynomials and subtracting the result), there are a couple of techniques that could be used depending on how large is the number of equations $m$ compared to the number of variables $n$ (I'll assume for simplicity that your equations are quadratic).

Intuition says that the more equations you have, the easier the system will be to solve. This is because equations represent "information" about the solution, and the more information you have, the easier it is to caractherize the solution. For instance, if you have many many more equations than variables (something like $m = \binom{n+2}{2}$), then linearization will work and actually will give you the solution in polynomial time. However, if you don't have this condition you are not guaranteed linearization will succeed.

On the other hand, if the ratio $m/n$ is equal to $C$, some work on semi-regular sequences shows that if you take a random system with these characteristics, then the fundamental parameter determining the running time of any Groebner basis algorithm (the Degree of Regularity) will be approximately equal to
$$\left(C - \frac{1}{2} - \sqrt{C(C-1)}\right)n$$
(notice this is a decreasing function in $C$, as expected). Using the relation between the arithmetic complexity of general Groebner basis algorithms and this Degree of Regularity, one can show that this complexity is exponential in $n$ if $m = O(n)$, and sub-exponential if $m = \tilde{O}(n)$.


Can chaining hash functions reduce security? Is there a concrete case where chaining cryptographic hash functions reduces security?

I'm thinking of things like md5(md5(x)) or sha256(sha1(x)), as common in password hashing (even though neither function above is suitable for it).

Yes, there are concrete cases where chaining cryptographic hash functions reduces security; and you gave one. SHA-256(SHA-1(x)) is in particular less collision-resistant than SHA-256(x). We now know collisions for SHA-1(x), and these give collisions for SHA-256(SHA-1(x)), but not  SHA-256(x).

More generally, a chain of hashes is neither more collision-resistant, nor second-preimage-resitant, than the first hash performed is. Thus inserting a weak hash as the first/inner is a recipe for weakening an otherwise fine hash.

On the other hand, SHA-256(SHA-1(x)) resists length-extension attack when neither SHA-256(x) nor SHA-1(x) do; and SHA-256(SHA-1(x)) can be more resistant than SHA-256(SHA-256(x)) is to some attacks in some Proof-of-Work protocol; thus chaining hashes, including different hashes, can have some benefit.


Why is it important that phi(n) is kept a secret, in RSA? Why is it important that $\phi(n)$ is kept a secret, in RSA?

From the definition of the totient function, we have the relation:

$$\varphi{(n)} = (p - 1)(q - 1) = pq - p - q + 1 = (n + 1) - (p + q)$$

It then easily follows that:

$$(n + 1) - \varphi{(n)} = p + q$$
$$(n + 1) - \varphi{(n)} - p = q$$

And you know from the definition of RSA that:

$$n = pq$$

Substituting one into the other, you can derive:

$$n = p \left ( n + 1 - \varphi{(n)} - p \right ) = -p^2 + (n + 1 - \varphi{(n)})p$$

With some rearranging, we obtain:

$$p^2 - (n + 1 - \varphi{(n)})p + n = 0$$

This is a quadratic equation in $p$, with:

$$\begin{align}a &= 1 \\ b &= -(n + 1 - \varphi{(n)}) \\ c &= n \end{align}$$

Which can be readily solved using the well-known quadratic formula:

$$p = \frac{-b \pm \sqrt{|b|^2 - 4ac}}{2a} = \frac{(n + 1 - \varphi{(n)}) \pm \sqrt{|n + 1 - \varphi{(n)}|^2 - 4n}}{2}$$

Because of symmetry, the two solutions for $p$ will in fact be the two prime factors of $n$.

Here is a short example, let $n = 13 \times 29 = 377$ and $\varphi{(n)} = (13 - 1) \times (29 - 1) = 12 \times 28 = 336$. Using the quadratic equation shown above, we need to use the following coefficients for the equation:

$$\begin{align}a &= 1 \\ b &= -(377 + 1 - 336) = -42 \\ c &= 377 \end{align}$$

Thus we have the following quadratic to solve:

$$p^2 - 42p + 377 = 0 ~ \implies ~ p = \frac{42 \pm \sqrt{|-42|^2 - 4 \times 377}}{2} = \frac{42 \pm 16}{2}$$

Finally, we calculate the two solutions, which are the two prime factors of $377$ as expected:

$$\frac{26}{2} = 13 ~ ~ ~ ~ ~ ~ ~ ~ \mathrm{and} ~ ~ ~ ~ ~ ~ ~ ~ \frac{58}{2} = 29$$

In conclusion, knowledge of $\varphi{(n)}$ allows one to factor $n$ in time $O(1)$. The other answers are equivalent, in that knowing $d$ achieves the same result (loss of any security properties of RSA), but just for completeness I thought it would be a good idea to show how $n$ can be factored with this information.


How many bytes of data does AES 256 encrypt at one time? Since the block size of AES 256 is 256, how would we calculate the bytes of data AES 256 encrypts at one time?

AES has always 128-bit block size with 128,192 and 256-bit keyspaces.  Therefore, you can encrypt 16-byte at a time if you are using ECB and CBC modes. By using CTR mode you can encrypt 1-bit to 128-bit.

Some people confuse AES with Rijndael where AES is a variant of the Rijndael. Some old libraries use the Rijndael (see RijndaelManaged). Rijndael can have 128, 160, 192, 224, and 256-bit block size. Note that these are not standardized, see FIPS 197.


How hard is to figure out the ENCRYPTION key given message and clear text? How feasible is to brute force the ENCRYPTION key if you have

the clear-text message
the encrypted-version of the same message
you know that Rijandel is the encryption algorithm
you know that the salt is 2 bytes long

The attack you describe is called a "known-plaintext attack". It was commonly used to break older encryption schemes, most notably Enigma in the second world war.

AES/Rijndael is not susceptible to known-plaintext attacks.

Further reading:

Wikipedia: Known-plaintext attack

Why is AES resistant to known-plaintext attacks?


Is there necessarily an infinite number of inputs to any given output in a crypto hash function? This might be a very easy question. Let's consider cryptographic hash functions with the usual properties, weak and strong collision resistance and preimage resistance.

For any given output, obviously there are multiple inputs. But is that necessarily an infinite number of preimages, for any given hash value?

How would I go about giving a formal proof that there exists no crypto hash function $h$ such that there is a given value $v = h(m)$ for which the possible set of inputs $m^*$ is finite? Would this necessarily break collision resistance?

For any given output, obviously there are multiple inputs.

This is not true. Namely, for any is not true. There are outputs such that multiple inputs produce them - this is consequence of pigeonhole principle. But we cannot claim that this holds for any output for any hash function. This can be true for some specific hash function only.

  ... proof that there exists no crypto hash function ...

There is no proof because this statement is simply false. Here is a simple example of a hash function that has many hashes that have finite number of preimages.

function hash(x){
    if (x.length <= 64) {
        return
            '1' ||
            '0000000000000000000000000000000000000000000000000000000000000000' ||
            sha3(x);
    } else {
        return
            '0' ||
            sha3(x) ||
            '0000000000000000000000000000000000000000000000000000000000000000';
    }
}

The number of inputs that produce hashes starting with '1' is finite.


Goldreich-Goldwasser-Micali Construction The Goldreich-Goldwasser-Micali construction allows to build a (cryptographically secure) pseudo-random function from of a (cryptographically secure) pseudo-random generator.

More formally, let $G: \{0, 1\}^s \rightarrow \{0, 1\}^{2s}$ be a length-doubling PRNG. Given a seed $s$, $G(s)$ returns a $2s$-bit string $G(s) = G_1(s)||G_0(s)$, where $||$ denotes the concatenation. Then, the GGM construction works as follows: given a key $k\in\{0, 1\}^s$ and an input $x=x_{n-1}||\dots||x_{0}\in\{0, 1\}^n$, the output $y \in \{0, 1\}^s$ is computed as $y = F_k(x) = G_{x_{n-1}}(G_{x_{n-2}}(\dots(G_{x_0}(k))\dots))$.

In terms of efficiency, the GGM construction needs $n$ calls to the PRNG for an $n$-bit input. Is there a more efficient, but still provably secure construction, i.e., a construction making less calls to the PRNG? Any pointer on a paper is welcome!

Levin showed that combining PRG with a universal hash function, one can reduce the number of calls. Roughly speaking, we shorten a message with a universal hash function before applying the GGM construction.
That is, $y = F_{k,k'}(x) = \mathrm{GGM}_G(k,h(k',x))$, where $h$ is a universal hash function.

At TCC 2012, Jain, Pietrzak, and Tentes gave another technique to reduce the number of calls with preserving hardness by using t-wise independent hash functions. See their paper for details.

Leonid A. Levin. One-way functions and pseudorandom generators. Combinatorica, 7(4):357-363, 1987. Levin87

Abhishek Jain, Krzysztof Pietrzak, Aris Tentes: Hardness Preserving Constructions of Pseudorandom Functions. TCC 2012: 369-382. JPT12


Given $ g^s, g^y , g^r, g^t, g^{st-rs}, g^{(yr+d)/t}$ , is it hard to distinguish $e(g,g)^{syr}$ from a random value? Where $g$ is a group element in bilinear group $G$, $e(g,g)∈GT$ and $s, y, r, t, d$ are randomly chosen.

I understand it is very similar to the conventional DBDH problem, but $g^t, g^{st-rs}, g^{(yr+d)/t}$ are also known, possibly making it easier???

Does anyone know the answer or suggest some material for reference?

Many Thanks

No, it's no easier than the standard DBDH problem.

Here's the reduction that shows that: suppose that we have an Oracle that solves your problem (given $g^s, g^y, g^r, g^t, g^{st-rs}, g^{(yr+d)/t}, e(g,g)^x$ is $e(g,g)^x = e(g,g)^{syr}$?)

Now, suppose we're given $g^s, g^y, g^r, e(g,g)^x$, and are asked whether $e(g,g)^x = e(g,g)^{syr}$.

What we do is select a random values $t'$ and $z$, and compute $g^{t'} / g^r = g^t$ and $(g^s)^{t'} = g^{st-rs}$; we don't know the value of $t = t' - r$, but we know that it exists).  We further compute $g^z = g^{(yr+d)/t}$ (again, we don't know the value $d = zt - yr$; but we don't have to know).

Then, with these values, along with the values we got with the original query, we ask the Oracle (and get the answer).


One Time Pad change by third party? I was reading about how a one time pad output can be changed by a third party without the receiving person realising.  Surely the output at the other end would be garbage?  Also, could you not generate a crc for the output, encrypt it with the same random sequence so at the other end it could be decrypted and checked to make sure nothing has changed?

I was reading about how a one time pad output can be changed by a third party without the receiving person realising. Surely the output at the other end would be garbage?

There's no guarantee either way that it will or it won't.  And in fact, OTPs have one very unfortunate (but by no means fatal) property: an active adversary that flips one bit of the ciphertext will cause plaintext bit at the same position to flip (relative to the true plaintext) when the adulterated ciphertext is decrypted.  The recipient must therefore be able to tell that the decrypted message is wrong from a single bit flip.

One key concept you're missing here is that in cryptography we generally assume that the adversary may have partial knowledge of the plaintext.  Even though we often informally say that the goal of a cipher is to prevent the adversary from learning anything about the plaintexts, what that actually means is preventing them from learning anything more than what they already knew beforehand.

In real life, adversaries may know a lot about the plaintexts that the honest parties encrypt.  Like, for example, they might know that the plaintext is an HTTP request to a certain path within the server, and the values of some but not all request parameters.  And that sort of knowledge might be enough for the adversary to modify the ciphertext to produce a plaintext that the recipient cannot tell is a forgery.

And even if the adversary doesn't have certain knowledge of any part of the plaintext, they might have a bunch of reasonable guesses.  So they might just repeatedly try and modify the ciphertexts according to those guesses and see if they get lucky.  Even if most of the guesses result in garbage at the other end, this is much more dangerous than you're giving it credit for, because nowadays the other end is almost always a computer, not a human being.  Programmers are routinely careless, and computers are really good at blindly following instructions even when the program's preconditions have not been met.  They're also really fast, so the attacker could possibly get to try a ton of guesses before any human being spots it, and even if they don't succeed at their goal they could cause a ton of collateral damage by getting the computer to act funny and damage all sorts of data and business processes.

  Also, could you not generate a crc for the output, encrypt it with the same random sequence so at the other end it could be decrypted and checked to make sure nothing has changed?

Nope, that's easy to defeat.  If you flip one bit of the original message, it's easy to compute the bits that you must flip on its CRC to produce the CRC of the adulterated one.  And this means you can just flip the corresponding encrypted CRC bits in the ciphertext as well.


Is it safe to use GZIP to avoid padding related attacks I am designing a library that supports encrypting some in-memory data using AES in CBC mode. Now I need a padding but it seemed to me that Apple's CommonCrypto library and OpenSSL have different padding schemes but I want to retain interoperability even when mixing CommonCrypto implementation and OpenSSL ones. (My library should work under Linux which have only OpenSSL, iOS which have only CommonCrypto and OS X which have both.)

Given that my library already have gzip and gzip archives can still be unarchived with any byte string concatenated after it, I am considering this padding scheme:

Gzip the incoming data.
Concatenate this archive with random bytes to bring the length up to AES block boundary.

When decrypting, the gzip algorithm will automatically discard the appended random bytes.

You are basically using gzip to convey the length of the given message. As long as your implementation of AES-CBC is secure (e.g. by using a random IV) then the given scheme should be secure against padding oracle attacks. This is easy to prove as there is nothing that removes the padding from the plaintext.

CBC padding in general does not add any security to the block cipher mode. You could just pad with zero bytes if you already know the size of the plaintext. In that sense the scheme is safe as long as no information is leaked to an attacker after decryption. Note that using gzip may influence the size of the plaintext so you need to make sure an attacker cannot learn too much from the size of the ciphertext.

Your scheme is therefore safe if the attacker only has access to the ciphertext. In that case it does provide confidentiality.

So now for the bad news...

This does not mean that the data within the ciphertext container cannot be altered. As there is no cryptographically secure authentication tag present, an attacker could very well be able to change the ciphertext in a way that cannot be detected. So the application code that processes the decrypted data could still be fooled to leak information about the plain text.

In other words, although you have now successfully protected against padding oracle attacks, you haven't protected yourself against similar, active attacks on the ciphertext. Please add some kind of secure authentication tag. It is by far the best way to protect yourself against these kinds of active attacks.


Why gcd(r,(p-1)/r) needs to be 1 in benaloh cryptosystem I recently discovered the benaloh cryptosystem.
I am working with the system as it is discribed in the following link:
https://en.wikipedia.org/wiki/Benaloh_cryptosystem

However I need some help in order to understand why we need
\begin{equation}
{gcd(r,(p-1)/r)}
\end{equation}

As far as I understand the condition
\begin{equation}
r \mid (p-1)
\end{equation}
guarantees the existence of the subgroup of order (p-1)/r which contains the r-residues.

The third condition

\begin{equation}
{gcd(r,(q-1))}
\end{equation}

allows us to say that there are

\begin{equation}
\mid \mathbb{Z}_n^* \mid /r
\end{equation}
r-residues mod n.

what does the other condition add?

$gcd(r,(p-1)/r)$ needs to be $1$ in Benaloh cryptosystem that mean that $(r)$ and $(p-1)$ are preliminary among them.


RSA encryption and decryption not resulting to the correct result? I'm having a hard time creating a functioning RSA algorithm for some reason even though I have all the steps right (or at least I think I do). So I have the following :

I picked prime numbers, $p$ and $q$ as:

$$p = 13691$$
$$q = 29387$$

I picked $n$ as $p \cdot q$
$$n = 402337417$$

So
$$\phi(n) = 402294340$$

I picked a random $e$ between $1$ and $\phi(n)$
$e = 46117$

My message was
$M=3$

I got $d$ by the Extended Euclidean Algorithm as the following:
$d= 7795$

When I do the encryption using $M^e \,\text{mod}\, n$ I get: $c= 399797630$

When I do the decryption using $C^d \,\text{mod}\, n$, I get $243069037$, which is not $M = 3$?

Any idea what can be the reason behind this? My guess is that $d$ is incorrect.

Your $d$ is wrong, double check your EEA calculation. You picked up the wrong Bezout coefficient from $7795\times 402294340 - 67998447\times 46117 =1$. You should use
$d= -67998447 \equiv 334295893 \pmod {\phi(n)}.$


Is SHA-256 safe when used in this way? I am wondering whether an attacker can gain any useful information from having several hashes of an unknown plaintext that differs in relatively few bits. For example, if provided with:

H1 = SHA-256(TXT | 1)
H2 = SHA-256(TXT | 2)
...
HN = SHA-256(TXT | N)

Can an attacker recover TXT more easily?

What you (most probably) describe is called a "preimage attack", where the attacker tries to find a message that has a specific hash value.

Some related attacks against reduced/weakened versions of SHA-256 are known, but (as far as I know) no such attack was successful against the standard SHA-256 algorithm up to today. So generally, it can be to be considered safe... but: as Stephen Touset already noted in his comment, the security of your final implementation may be influenced negatively if the overall entropy of hashed data is small enough to render things like brute-force attacks feasible. You should definitely keep a critical eye on that aspect.

In fact, there are - at least - two things you should watch out for in relation to salts in general:
(btw.: just in case you don't know... "salt" is the crypto-term for your TXT part)

The "Salt Reuse" Problem

Depending on your actual implementation, it could be a mistake to use the same salt in each hash.

If - for example - two users use the same salt, they will produce the same hash. This can be pretty ineffective from a security point of view. In such a case, an attacker could use a reverse lookup table attack to run a dictionary attack on every hash at the same time. The attacker would just have to apply the salt to each "message" guess before the attacker hashes it.

Simpler said: if the salt is reused, lookup tables and rainbow tables could be built for that salt and that would make it easier to crack hashes generated by your implementation. That's why - for example - when implementing user-login systems and hashing user passwords, a new random salt must be generated each time a user creates an account or changes their password.
The "Salt Length" Problem

If a salt is too short, an attacker can build a lookup table for every possible salt. Let's take your example and assume it were a real-life implementation where your salt is made up out of the three letters TXT. If an attacker would guess you were only using 3 ASCII characters, then the attacker would merely need to check around and about (95x95x95 =) 857375 possible salts. That may seem like a lot at first glimpse, but creating according lookup tables is rather simple and an according attack pretty manageable with today's hardware.

So, to make it infeasible for an attacker to create a lookup table for every possible salt, the salt must be long.

Personally, I assume it to be a good choice to use salts of the same size as the output of the individually used hash. For example: the output of SHA-256 is 256 bits (= 32 bytes), so I would salt it with (at least) 32 random bytes. But this is more of a personal preference. Others might disagree.

Getting back to your question while pointing at what I noted above: it can be safe, if you implement it correctly - but a small mistake in your implementation may result in a big gain for potential attackers.


GCM optimisation using $M_0$ and $R$ tables - Calculation of $R$ I'm implementing GCM in C as a way to learn about it. In the paper titled as The Galois/Counter Mode of Operation (GCM) by McGrew and Viega on chapter 4.1, page 11, 12, they talk about the optimisation of GCM via usage of the tables $M_0$ and $R$. What I'm not understanding is how to calculate the table $R$, which shall contain the products of $x \cdot P^{128}$.

The Paper doesn't go more in depth about it, can some of you help me with my understanding of it?

$P$, defined on p. 8, is a representation of a primitive element in $\operatorname{GF}(2^{128})$; specifically, if we represent the field by $\operatorname{GF}(2)[t]/(f)$ where $f = t^{128} + t^7 + t^2 + t + 1$, $P$ represents the polynomial $t$, i.e. $0 + t + 0 t^2 + 0 t^3 + \cdots + 0 t^{127}$.

If $x$ is a byte, represented as some polynomial in $\operatorname{GF}(2)[t]$, then there are only 256 possible values of $x$.  The table $x\cdot P^{128}$ maps each possible byte to the corresponding polynomial $x\cdot t^{128}$ reduced modulo $f$.


Can nesting different ciphers with different keys ever decrease security? Very related to this question but not addressed there.

Does the following construction risk introducing any vulnerabilities that render it less secure than using either of its individual components in isolation?:

EncryptAB(K1||K2, PT) = EncryptA(K1, EncryptB(K2, PT))

EncryptA and EncryptB may be different algorithms. K1 and K2 my be of different lengths. The result need not be more secure than the better of it's components, just not less secure.

A related question is: are there any potential problems with interleaving the rounds of two or more independent algorithms?

(BTW: I'm not planning on doing either, it's more a matter of curiosity.)

Edit: I'm only thinking of the bare block cipher primitives rather then chaining modes and such.

In your construct:

EncryptAB(K1||K2, PT) = EncryptA(K1, EncryptB(K2, PT))

it is easy to show that, as long as the keys K1 and K2 are independent, that this cannot be any less secure than the stronger of EncryptA and EncryptB.

Here is a sketch of how this is shown; suppose that there is a chosen plaintext attack against EncryptAB; that is, the attacker submits known values to EncryptAB, examines its results, and somehow rederive the value K1||K2.  Then, this method can be used to attack EncryptA; the attacker would choose a random value for K2; he would take his chosen plaintexts, EncryptB them with his K2 value, and then submit them as chosen plaintexts to the EncryptA with the known key.  Then, he can use those encrypted values to rederive the K1||K2 values, which includes the value K1 which he was interested in.  The attack against EncryptB works in exactly the same manner.

Now, this method doesn't prove that EncryptAB is any stronger than the stronger of EncryptA and EncryptB (and, indeed, it might not be); however, it does show that using the two of them doesn't make things any worse.  Also, we need to assume that that keys K1 and K2 are independent, because this simulation has the attacker picking one of those values; if they are interrelated, he wouldn't be able to do that.

Now, for your related question: how about interleaving the rounds of two different ciphers.  That doesn't have any such security reduction, and in practice, it would give me the willies.  Encryption round functions don't have that much strength in themselves (that's why we use multiple rounds); what a good round function is designed to do is play nicely with the round functions that'll be next to it in the designed cipher.  For example, if there is a good differential through one round, it's going to be the case that it doesn't have any good paths through the next one (or the one after that).  This is not by accident; the cipher designer (at least, if they knew what they were doing) went through some serious analysis to make sure that was the case.

In contrast, if you interleave the round functions from two different ciphers, well, no one has done any such analysis.  Yes, it might be secure, but without someone spending a lot of time looking at it, you couldn't be certain.  It'd be far better to use your original suggestion, and do a full set of rounds from your first cipher, and then do a second set of rounds from your second.


How to store keypair generated by RSA in a textfile? I'm trying to write an encryption decryption program using Openssl-RSA. There are only two operations. User stores the data and retrieves it whenever he needs.

To decrypt something, we need the keypair that was generated during the encryption. Where and how do I store this keypair so that I can access it whenever the user requests decryption of something (which was already encrypted by the user).


Problem in understanding Blakley's Secret Sharing Scheme I need to implement Blakley's Secret Sharing Scheme. I have read below mentioned two research papers but still unable to understand how to implement it.

Safeguarding cryptographic keys
Two Matrices for Blakley’s Secret Sharing Scheme

The following is the steps I have been able to understand.

We chose positive integers $z$, $a$ and $b$.
We chose a large $p$
A $(a+b+2)\times(b+2)$ matrix $M$ is created satisfying the following conditions:

Random entry in each row is set to $1$.
Another random entry in first row is set to $k$, chosen from $\mathbb F_p$.
All other entries are filled with random values from $\mathbb F_p$.

After this some equation need to be formed and then solved for share.

I am unable to understand how shares are calculated and how can they be verified. Kindly help me understand the remaining process.

An easier way of explaining it is here: http://www.demoivre.org/courses/CIS628/chapter15.pdf

So for a point $(x_0,y_0,z_0)$ we set $x_0$ as the secret and then randomly choose $y_0$ and $z_0\pmod{P}$.

Now we  generate our plane to distribute to the participants:
we pick two random integers $a$ and $b$, then we set

$$C = z_0 - ax_0 -by_0 \pmod{P}$$

we now have our equation for the plane, such that:

$$z = ax + by + c$$

to reassemble the secret we use matrix manipulation and it is simply:

$$a_i x + b_i y - z \equiv -c_i \pmod{P} $$

scroll down to page 12 on that link for a really good example


Fast 128-bit MAC with second preimage resistance? I have an application that needs a fast 128-bit MAC to guarantee message authenticity in a protocol. I would like to reuse this MAC value as a binding identifier, so that even those who know the key cannot later generate another message with the same MAC value for that key.

"Second preimage resistance", or whatever you call it here, is not normally a required property of MACs and the only one with it that comes to mind is HMAC. However, I would like something faster (with many relatively short messages per key). AES hardware can be assumed, so if there is a block cipher based MAC that does not allow generating a colliding message, that could fit the bill.

Do such MACs exist?

Collision resistance is not required.

I really like this question, and have two things to say.

First note that CBC-MAC is no good since given the key it's easy to find a collision. Let $t$ be a tag for a message $m=m_1,m_2$ of length $\ell$ bits. Then, in CBC-MAC the input to AES first is $\ell$ and then the output is XORed with $m_1$ and input to AES, and so on. Let $t_1$ be the intermediate value output from AES with $m_1$. Then, you can make any change to $m_1$ and compute $t_1'$. Now take $m_2'$ so that $m_2'\oplus t_1' = m_2 \oplus t_1$. This will give you the same output tag $t$. (I hope that this is clear.)

Now, let's try and answer better. Specifically, let's assume that there exists a construction that gives what you want, and so you have collision resistance even given the key. This actually gives you a construction of a hash function from a block cipher. We have some such constructions in the ideal cipher model, like Davies-Meyer. However, these are problematic to apply to AES since AES has weaknesses under related key attacks (which are exactly the types of attacks that appear when constructing a hash function from a block cipher).

Based on @otus's comment, I will extend my answer to deal with theory as well. What you are really asking is to build a second-preimage resistant hash function from a block cipher. Practically, we don't know how to do this differently to full collision resistance (to the best of my knowledge; please correct me if I'm wrong). However, theoretically, it is possible to construct universal one-way hash functions (which are second preimage-resistant hash functions) from one-way functions. This is a famed result by Rompel, with a full proof here. Thus, theoretically speaking, it is possible to construct such a hash function from block ciphers (since block ciphers are pseudorandom permutations and one-way functions can easily be constructed from them).

In contrast, Simon proved that collision-resistant hash functions cannot be constructed from one-way functions in a black-box way.


Do any probabilistic hashing algorithms have additive homomorphism? What I am looking for is a function that meets the following criteria:

For each possible input (assume integers from [0, 255]), there must be trillions of possible outputs so as to prevent preimage attacks and is hence probabilistic.
The function must be a one-way hash, so given an output the input cannot be deduced.
The outputs must exhibit additive homomorphism such that some operation on f(a) and f(b) will equal f(a+b).

Is such a scheme possible? I've read many papers that have developed methods close to this, but none that I understand fully meet my criteria.

Paillier exhibits these properties, except it's an encryption scheme as opposed to a hash, meaning it requires public and private keys. In this scheme, there should be no feasible way to "decrypt" an output.

I've found several homomorphic hashing schemes, but each one seems to fall short in some way:

LtHash is interesting, but not probabilistic, as an input maps to only one output and a small input set should be easy to preimage.
The cryptosystem proposed in this paper seems like it could be a good fit, but I don't entirely understand how the global vs per-publisher hashing would work.
This blog post outlines a similar mechanism, but I'm not sure if it's still vulnerable to pre-imaging and always maintains it's homomorphic properties.

I've read through StackExchange, and I've only seen a few posts in the last few years relevant to the question, including this one, but I don't see how Merkle or Hash trees could be used as a solution to these criteria.

The purpose of this function is to obfuscate values in a distributed ledger, while still allowing arithmetic operations to be conducted on them. Paillier would work perfectly if only a public key was distributed, but the potential existence of a private key doesn't work for this scenario, as it would allow one party to read all of the data.

If one of these solutions does, in fact, meet the criteria outlined, a quick explanation as to how would be greatly appreciated. Thanks.

The outputs must exhibit additive homomorphism such that some operation on $f(a)$ and $f(b)$ will equal $f(a+b)$.

Because $f$ is mandated to be nondeterministic, I assume that the requirement be that $f(a) \odot f(b)$ be some possible output $f(a+b)$ (for some computable operation $\odot$).

If so, there must be some further requirement; here's one $f$ function that meets the above requirements in a spectacularly unuseful way:

$f(x)$ is a nondetermanistic function that ignores the input $x$ and generates a random bit string of length $n$ (for a suitably large value of $n$).

Then:

For any input, there are $2^n$ possible outputs; if $n$ is large enough, this easily meets the 'trillions of possible outputs'
Examining the output does not allow the input to be deduced - obviously true.
There must be an operation on $f(a)$ and $f(b)$ that yields a possible output of $f(a+b)$ - for this, we can pick any arbitrary operation $\odot$ that maps two $n$ bit inputs to an $n$ bit output, and then we have $f(a) \odot f(b)$ is a possible output of $f(a+b)$.

Obviously, this function $f$ is unlikely to solve the specific problem you have in mind - what additional requirements are there?


What is Quantum Cryptography? When it comes to exchanging secure information over an insecure channel, this approach is considered. It all depends on the nature of photons in which the third polarization is focused. It can easily be trusted when it comes to exchanging the Secret keys without facing any issue.

What is Quantum Cryptography?
What are the differences between modern cryptography and quantum cryptography?

What is Quantum Cryptography?

Today's "normal" cryptography relies mostly on mathematical principles. For example RSA is based on the practical difficulty of the factorization of the product of two large prime numbers, the so-called "factoring problem".

Quantum cryptography (quote from Wikipedia):

  Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks.

So instead of relying only on mathematical principles, quantum cryptography relies more on quantum mechanical properties (physics). Some of these properties include:

The uncertainty principle
Quantum superposision
Quantum entanglement

  How secure are data that encrypted with Quantum Cryptography methods?

Quantum cryptographic tasks (often incorrectly called quantum cryptography) are theoretically 100% secure, even against quantum-computers.

The method described in your question is Quantum key distribution (QKD). QKD has provable security based on information theory, and forward secrecy. This is based on the No-cloning theorem, which states that it is impossible to create an identical copy of an arbitrary unknown quantum state.

  If Quantum Computing becomes practical and is mass-produced, will we be facing with next-generation of cybersecurity?

Not necessarily. I personally think that quantum computers won't fully replace classical computers, because quantum computers only outperform classical computers in certain areas (i.e. large-scale simulations).

But if quantum computers were available they would break some of today's cryptography used on classical computers, i.e. RSA or Diffie-Hellman. We would then have to switch to post-quantum cryptographic algorithms like Supersingular isogeny key exchange. So ultimately, I think, we would just switch to quantum-resistant algrorithms and go on with our lives.

EDIT: This answer provides some additional information.


Using 3DES decryption to get a specific result I want to get 3DES to get a predictable result; assume I have:

key: [any]

data: [any]

then I want to apply 3DES decryption on key and data to get a specific result, such as:

decrypted 3DES: 12121212121212121212121212121212

Is this possible in theory?

I want to apply 3DES decryption on key and data to get a specific result. Is this possible in theory?

Sure. 3DES is a functionally correct encryption scheme for any fixed key, so for any message there exists a(t least one) corresponding ciphertext value.

So if you want to have a specific decryption result $m$ using a specific key $k$, you simply choose the ciphertext $c$ as $c=E_k(m)$ and by correctness $D_k(c)=D_k(E_k(m))=m$.


Short Weierstrass equation is non-singular for not 2 or 3 characteristic Consider a field $K$ of characteristic $p \neq 2,3$. Consider a curve $E$ over $K$ defined by the equation $y^2 = x^3 + ax + b$.

How can I show that:

  $E$ is not an elliptic curve (it is not singular) $\iff$
  $4a^3 + 27b^2 = 0$

By definition, a point on the affine curve
$$
E\colon\quad \underbrace{y^2-x^3-ax-b}_{=:f}=0
$$
is singular if and only if the Jacobi matrix
$$
J_f
=\Big(\frac{\partial}{\partial x}f,\frac{\partial}{\partial y}f\Big)
=(-3x^2-a,2y)
$$
does not have maximal rank at that point, that is (here), vanishes.
Hence precisely the points $(x,0)$, where $x$ annihilates both $x^3+ax+b$ and its derivative $3x^2+a$, are singular points of $E$. Therefore, such a point exists if and only if $x^3+ax+b$ has a multiple root, and this is the case if and only if its discriminant
$$
\Delta=-4a^3-27b^2
$$
is zero.

To be precise, it still remains to prove that the point at infinity $[0:1:0]$ is always non-singular: On the affine patch $\{y=1\}$, the (projectivized) curve equation $y^2z-x^3-axz^2-bz^3$ dehomogenizes to $z-x^3-axz^2-bz^3$. Its Jacobi matrix $(-3x^2-az^2,1-2axz-3bz^2)$ becomes $(0,1)$ at the point at infinity $(0,0)$, hence is non-degenerate for any $a$ and $b$.


Calculating hash of original message by encoded message Consider E - encryption function and H - function calculating hash of message.
Is there any E, H for which for message M:

H(E(M)) = H(M)

As SEJPM notes in the comments, this is trivially achieved by making $E$ the identity function, such that $E(M) = M$ for all $M$.

If $E$ is not the identity function (and, in particular, if it's practical to find a message $M$ such the $E(M) ≠ M$), then $H(E(M)) = H(M)$ would be a collision attack on $H$.

Normal cryptographic hash functions are supposed to be collision resistant, so for such hash functions $H$ there cannot be any such function $E$ (at least, none that is practically computable and distinguishable from identity), or else the hash is broken.

But I suspect what you're really looking for is something else, such as $H'(E(M)) = H(M)$, where $H'$ and $H$ are two different hash functions.  This is easy to achieve by defining $H$ as $H(x) := H'(E(x))$ or, if $E$ is invertible, by defining $H'$ as $H'(x) := H(E^{-1}(x))$.  However, defining $H$ (or $H'$) like this does mean that if computing $E = E_K$ requires some secret key $K$, then the same key will also be needed to compute at least one of $H$ or $H'$.

What if we wanted to have $H'(E_K(M)) = H(M)$, where neither of $H$ and $H'$ depend on the key $K$?  In that case (assuming the $H$ isn't constant, and in particular that an attacker can choose two messages $M_0$ and $M_1$ such that $H(M_0) ≠ H(M_1)$) $E$ cannot be an IND-CPA secure encryption scheme, and thus cannot be semantically secure.  Semantic security is commonly considered the minimum baseline requirement for a secure modern encryption scheme (although there are some weaker but still useful security properties, such as Rogaway and Shrimpton's DAE security), so by that definition, even $H'(E_K(M)) = H(M)$ isn't achievable if $E$ is supposed to be secure (and $H$ is distinguishable from a constant function).


Is deniable error-correction possible? This question came up as I tried to answer an earlier question I asked: Cryptographic data structure: sparse array without membership test.  I still have not resolved that question to my satisfaction, but this question may be appreciated independently.

I want an error-correcting code that has the additional property that when encoding a string that cannot itself be feasibly distinguished from a random string, the encoding cannot be feasibly distinguished from a random string either.  So, for example, Alice could generate a random 1000 bit string, encode it using the algorithm to get a 2000 bit string, and send it over a noisy channel to Bob.  Bob could recover Alice's original 1000 bit string (even if there were many corrupted bits) but would have no way of knowing that Alice did not just send a random 2000 bit string.

I realize that "deniable" may not be the best word to use for this property since this word already has a different technical use in cryptography.  But I am not sure what to call the property.

Also, are there any tags I should be using besides "algorithm-design"?  For both my previous question and this one, I felt that there was no completely appropriate tag.

Here's an approach that corrects some errors:

Alice has a bitstring S that is indistinguishable from random that she wants Trent to know. (Perhaps it's actually a ciphertext that only Bob knows how to decrypt).
Alice generates 5 fresh new random bit-strings pM, pN, pP, pQ, and pR just as long as the original random bitstring S.
For each bit of S, Alice checks the the corresponding 5 bits of the random strings pM, pN, pP, pQ, and pR. If the majority of those 5 bits is the same as S, Alice keeps that bit the same, otherwise Alice flips all 5 bits, generating 5 modified versions of those random strings M, N, P, Q, and R.
Alice sends M, N, P, Q, and R to Trent.
For each bit of the messages M, N, P, Q, and R, Trent uses 5-modular redundancy -- the majority of the 5 bits -- to attempt to recover the string S.

Because pM, pN, pP, pQ, and pR are completely randomly generated, and S is indistinguishable from random, Trent is still unable to distinguish M, N, P, Q, and R from random bit-strings.

For any one bit-position, the 5 bits can be in any one of 32 possible patterns with equal probability.
If there is no bit error in some particular position, Trent always recovers the correct bit of S at that position.
Trent can usually correct any single-bit-flip error across a row of 5 bits.
(Given any 1 of the 5 bit positions ahead of time that will suffer a single-bit-flip error, 20 of the 32 possible patterns result in Trent recovering the correct bit of S, but the remaining 12 possible patterns would result in Trent decoding an erroneous bit).

I suspect there is a better encoding that allows Trent to always correct any single-bit-flip error.
Perhaps somehow forbidding the 12 vulnerable patterns, even though that allows statistical tests to conclude the collection of strings M, N, P, Q, and R are not completely random?


Selective Forgery of a Digital Signature - Goldwasser et al I am working though the paper of Goldwasser, Micali and Rivest ''A Digital Signature Scheme Secure Against Adaptive Chosen- Message Attacks''

In the hierarchy of the severity of breaking the signature scheme, what does the ''a priori'' in the definition of Selective Forgery mean?

  Selective Forgery: Forge a signature for a particular message chosen priori by the enemy.

The reference is Shafi Goldwasser, Silvio Micali, Ronald L. Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, in SIAM Journal on Computing, 1988.

It defines

  Selective forgery. Forge a signature for a particular message chosen a priori by the enemy.

Here, "a priori" means, informally, that the message is to some degree chosen by the adversary (or at least restricted) before the attack is carried, as opposed to being entirely a result of the attack.

The authors do not give a formal definition. One could be that the adversary must define, before being given the public key, a suitably small subset of the full message set among which s/he will later be able to exhibit a forgery (that is, an acceptable message/signature pair for which s/he has not obtained the signature by asking a signing oracle).


In zero knowledge proofs, would it make a difference if the prover is deterministic or probabilistic? In zero knowledge proofs, would it make a difference if the prover is deterministic or probabilistic?

As the verifier can simulate the prover's interaction with him, I assumed that the prover would need to be deterministic. Maybe this is a misunderstanding on my part?

In the general case of for auxiliary-input zero knowledge, it is impossible for the prover to be deterministic; see Definitions and properties of Zero-Knowledge proof systems by Goldreich and Oren. In the random oracle model, everything is different, so I don't want to go there. However, I will say that it is not true that the prover is deterministic is Fiat-Shamir. Fiat-Shamir is a way of converting some honest-verifier ZK protocols to fully malicious ones. Almost all honest-verifier ZK protocols considered have a probabilistic prover, so the Fiat-Shamir version also has a probabilistic prover.


Is this PGP key exchange secure? I am currently trying to create a secure key exchange between two parties. I have a good implementation of PGP that works well for my app, but my DH is really slow and doesn't work well; so I was thinking that maybe I could perform the key exchange with PGP.

My idea is this:

Party 1 -> public key -> Party 2
Party 2 -> public key -> Party 1

Party 1 generates random bits and sends them to party 2 with the public key
Party 2 generates random bits and sends them to party 1 with the public key

Shared key = Sha256(Party 1 random concatenated with  Party 2 random)

Would this be secure? (assuming that the implementations of Sha256, PGP, and the random generator are to par.

Assuming

that in the question "with public key" describes encryption under the intended recipient's public key;
secrecy of the corresponding private keys;
that by some external mechanism public keys are securely bound to the legitimate parties;
the parties have some unstated convention to define which is Party 1, defining who transmits first and order in "concatenated"

then yes,

the "Shared key" is the same on both sides absent alteration by an active adversary
an adversary (even active) can't predict any characteristic of the "Shared key" that one of the legitimate party uses.

Notice undesirable characteristics:

There's no forward secrecy: from past communications passively eavesdropped, an adversary later learning the two private keys can find the "Shared key". Modern key exchange protocols are safe from this.
[Edit: The simple/standard/best method for forward secrecy is DH, with some independent authentication mechanism (e.g. using the PGP keys in signature mode). I know no way to turn generic encryption or/and signature into forward secure key exchange without some other asymmetric crypto primitive.]
The party that transmits second can weaken the "Shared key" to some degree; e.g. choose it's random so that the top 32 bits of "Shared key" are zero, or some function of the other bits. However, each additional bit of weakening doubles the effort.
The parties have no insurance that their "Shared key" is shared with anyone; the only assurance is that it could be shared only with the legitimate holder of the private key matching the public key alleged by the other party.


Why does an algorithm need a keyspace? Why does an algorithm need a keyspace? I thought the person encrypting would define his/her own key.

An encryption algorithm does not need a keyspace.  By definition, however, it has one.

It sound to me like your confusion is mainly terminological.  In cryptography, the "keyspace" of an encryption system is defined simply as the set of all possible (distinct) keys that the algorithm can accept.

For example, let's say that we're back in the days of the ancient Romans, and encrypting a message with a simple shift cipher.  Obviously, to encrypt and decrypt the message, we need to know the correct key: the number of letters by which the alphabet is shifted.

Clearly, "1" is a valid key for this cipher, since we can indeed shift the alphabet by one letter.  So is "2", and "3", and so on.  Equally clearly, "1.5" is not a valid key, since it makes no sense to shift the alphabet by one and a half letters.  Thus, while the keys 1, 2 and 3 are all part of the keyspace, 1.5 is not.  Neither is $\pi$ or $\sqrt{-1}$ or "banana".

(A somewhat more subtle question is whether the keyspace for a shift cipher should include "0" or "-1" or "999".  Certainly, an alphabet shift of zero letters is possible; it just doesn't obscure the message in any way, and is thus completely insecure even by ancient Roman standards.  Similarly, we could shift the alphabet by 999 letters — but, since neither the modern nor the ancient Roman alphabet actually has that many letters, it will just wrap around and be equivalent to some smaller shift amount.  Generally, for cryptanalytic purposes, we'd want to ignore such obviously equivalent keys, and just say that the keyspace of the shift cipher has as many (distinct) keys as the alphabet has letters; or one fewer, if the zero key is not allowed.)

Why do we care about the keyspace, or its size, then?  Well, for one thing, a simple way for someone to attack a cipher is to try to decrypt a captured message with every possible key, and see which of the results makes sense.  The bigger the keyspace, the more resistant the cipher is to this naïve attack.  (Furthermore, in modern crypto, we actually try to design our algorithms so that, hopefully, this naïve attack is the best possible one, or at least close to the best.  Thus, unless someone breaks the cipher by finding a more efficient attack, the size of the keyspace is a direct measure of the strength of the algorithm.)

Also, when we do pick our encryption key, we obviously need to pick one that belongs in the keyspace; otherwise, by definition, it will not work.  Indeed, the safest choice is generally to pick the key uniformly at random from the entire keyspace.  If we don't (and the attacker knows or can guess how we picked our key; which we generally cannot prove isn't the case), then they can speed up their attack by trying the keys we're more likely to have picked first.  Thus, it's not enough to just know the size of the keyspace; we also need to know what the keyspace is, or at least enough about it to let us pick random keys from it.