How to deal with concrete security against lots of queries? In general, $O(1/\epsilon^2)$ queries are required to distinguish between two distributions that are statistically close at most $\epsilon$.
This informal state deals with the required number of queries to distinguish between two distributions. However, I cannot find any statement that when we have $Q$ queries, then we can distinguish two distributions under some $P$ probability.
I have a few questions about some common knowledge in cryptographic fields.

How can I formally write the statement about concrete security against lots of queries?
How we set parameter to be secure against adversaries allowed $Q$ queries? As standard decision problems, adversary has a negligible advantage?
Why NIST PQC standardization recommend parameters to be secure against number of queries $2^{64}$? Is there a special reason? What is implicit consensus relate to $2^{64}$?

Distinguishing distributions is studied in the field of distribution testing. See this survey for more information.
In particular, I believe the survey states that the correct sample bound includes a term roughly of the form $O(|\Omega|/\epsilon^2)$, where $\Omega$ is the support of the underlying distribution.
As for your particular questions:

Generally, query-bounds arise within cryptography when making Renyi-divergence arguments, as one can often make significant gains by bounding the queries (say as $q \leq 2^{64}$, rather than $2^{128}$, which is the "trivial" bound for 128-bit security). See for example this slides of Thomas Prest's (or in general his recent publications --- he has been quite interested in developing renyi divergence arguments in lattice cryptography).

For setting parameters when you're allowed to institute query bounds, see the slides. In particular, he works through the example of a particular algorithm (the Micciancio Walter convolution sampler) that claimed 100 bits of security, and shows that (up to $2^{96}$ queries) the sampler actually achieves 256 bits of security. For a different algorithm, he is able to set parameters such that certain state required for the algorithm is an order of magnitude smaller.

I can't really speak to the third question in any concrete way though.


Encrypting and obscuring data between site/user without SSL Im trying to figure out what the best way to encrypt data sent between a webpage and the user(both ways) is, when hosted in an environment that doesn't support SSL. The purpose of encryption would be obscuring content for delivery through filters that aid in internet censorship. What ways would that be possible to acomplish for normal visitors without any effort on their part?

Any steering you guys could provide is greatly appreciated, Thanks!

There is no easy way to do this in a secure manner. Simply obscuring the content will give you no additional security. I'll give you an overview of the possible ways to realise such a system, and then I'll conclude by telling you why they don't work well enough, unfortunately.

Key-Exchange protocols and encryption

The basic idea of these protocols is to securely exchange a secret (the shared secret) and use it to encrypt communication.

First approach (flawed, as we'll see)

Have both parties participate in a Diffie-Hellman key exchange

Both agree on $G$ and $P$ (see RFC 3526)
Both generate a random value $X$.
Both exchange public value $Y = G^X \mod P$
With each other's $Y$, they generate secret key: $K = Y^X \mod P$

Now that both parties share a secret, use AES encryption (for instance) to encrypt the data being transmitted, using the shared secret to derive an AES encryption key.

This is easily implemented in JavaScript.

The great problem with this approach is that it's susceptible to a Man-in-the-middle attack. Unless you add some form of authentication, for instance using a pre-shared key, an attacker would simply intercept and relay the comunication: Alice ←→ Eve ←→ Bob. The Communication between Alice and Eve, and between Eve and Bob is now secure, the communication between Alice and Bob isn't.

Possible fix:

If there is a shared secret, one that is either transmitted securely through some other means or shared beforehand, you can authenticate messages using a Message authentication code.

This "solution" however isn't very good. It basically means:

  In order to exchange a secret, first exchange a secret.

Which in practice means this approach will typically lead to an insecure crypto-system. This also happens to be the main problem with One-Time Pads.

You could use asymmetric keys for this, and build a Public Key Infrastructure to overcome this limitation, but then you'd basically implement almost all of SSL. It's worth mentioning again that 99% of security flaws are caused by mistakes in the implementation, rather than insecure protocols.

Second approach (totally doable, reasonably complicated)

We saw that the basic problems comes down to exchanging a secret. In order to authenticate both parties to each other (this is important, authenticating the client isn't enough!), we can use a password. This way, we can exchange a secret and know that we exchange it with the right person.

An example of a protocol designed for this purpose is the Secure Remote Password protocol (SRP). I'll not explain the protocol here, wikipedia does a far better job doing that.

Third approach, just implementing SSL

You could also basically implement SSL using your server-side language and JavaScript on the client. Now, SSL is quite complicated. The probability of a programming error leading to an insecure cryptosystem is very high.

It also requires you to have your own public key infrastructure. Meaning your clients have to get the right keys in order to communicate with your server.

In practice

This kind of thing is almost never done in practice. There are systems like Kerberos which, using a special key server, implement this kind of approach for client-server communication in closed networks, but I've never encountered anything like it on the world wide web.

If you just want to avoid being detected by Deep packet inspection, merely obfuscating the data will be enough. But you have to obfuscate at the TCP level, which normally means re-implementing whole protocols.
If you have to safeguard against decryption or de-obfuscation of your data after the fact, you need to use proper encryption that provides a few properties:

Authentication (you know exactly who you're talking to, both client and server)
Encryption (your communication is secret)
Perfect forward-secrecy (compromise of the long-term keys [like RSA keys] does not lead to a compromise of the short-lived encryption keys, i.e. does not compromise your past communications [this is the huge problem with PGP encrypted instant messaging])
Malleability (adversaries can easily fake the transcript of your messages after the fact, so that your scheme now provides deniability).

One protocol which provides all of these is Off-The-Record Messaging (OTR). This is a fantastic protocol, it's used for Instant Messaging however, not for web-pages.

Conclusion

I think I've taken more than enough of your time to demonstrate: there isn't an accepted or appropriate way to do it. But you can fiddle about until you find something that fits your (watered down) attack scenario. The Secure Remote Password protocol is the best way of doing this.

It will be much easier, and well worth your time and effort, to just change the rest of the system so that you can implement real SSL. That's the right way to do it.


Security aspects of using a global values as nonce and additional data for AES? is it a good idea to use global values as nonce / additional data? What problems
can occur?
What should be take in account when we deal with such parameters for encryption.

Thanks

It is not clear what you are attempting to do.
AES in itself does not need a nonce, it only needs a key.
If you are using an algorithm which uses AES, such as AES-GCM then the nonce must never be reused (In general when using cryptographic protocols, never reuse a nonce!).

If by global value, you mean one which is constant, this ruins the security of any nonce using protocol. If you simply mean using a global variable as an engineering question, this is usually not advisable, as you are not encapsulating the nonce, but should not ruin the cryptographic security of any algorithm, provided the nonce is used only once.


Combining secret/public keys Suppose that we have three authorities which each of them generate one secret/public key for Alice. It means that Alice has three secret keys and three related public keys. Suppose that Alice combines these three secret keys in a way with any kind of function and generate a new secret key (forth secret key), can he generate the related forth public key by any function or not? Is there any relationship between these two functions?

What's asked is possible, both for public-key encryption and signature schemes.

One option can be a concatenation of the keys, with delimiters allowing separation of concatenated keys (by the same function for public and private keys), with

for encryption, cascaded encryption in order of the public keys
for decryption, cascaded decryption in reverse order of the private keys
for signature (with appendix), concatenation of the signatures in the order of the private keys, with delimiters allowing separation of the signatures
for signature verification, verification of all the signatures in the order of the public keys (and success iff all the signatures check).

More in details, restricting to public-key encryption: we start from some hybrid public-key encryption scheme, easily implemented with wrapper scripts on top of GPG. Encryption accepts any plaintext file and a public key (as a text file starting with -----BEGIN PGP PUBLIC KEY BLOCK----- restricted to a single such block), and outputs a ciphertext file. Decryption accepts a ciphertext file and the matching private key (as a text file starting with -----BEGIN PGP PRIVATE KEY BLOCK----- restricted to a single such block), and outputs the original plaintext.

We define the question's functions building new keys to both be concatenation: the "fourth secret key" is the file obtained by concatenation of the first three secret keys (with some EOLs as separator), same for the public keys.

We modify the encryption script to parse its public key input and, for each public key found in that, encrypt the plaintext (for the first key) or the previous encryption result (for the next ones, if any). It outputs the final ciphertext obtained.

We modify the decryption script in the same way, except that it processes multiple private keys starting from the last one in the private key input file.

The modified encryption and decryption scripts still works just as the original when fed a single public or private key. And when using the fourth public and private keys as obtained by the concatenation functions, they are able to encrypt and decrypt.

It can be proven that if GPG is secure, then the new scheme obtained is.


Should I be using PKCS1 v1.5 or PSS for RSA signatures? I am implementing an application where a user needs to sign some data that they have created, store it in an untrusted place, then later retrieve that data and verify it is still authentic before using it. The user already has a RSA keypair for doing encryption throughout the application so I would like to re-use it for this signature (or else I would normally just use HMAC).

I see that I have two schemes available with RSA signatures: PKCS1 v1.5 and PSS.

Which of these should I be using? PKCS1 v1.5 seems a bit simpler to implement.
Are there security concerns with each schemes I should be aware of?
If I need to use PSS, what digest should I be using? Is SHA1 a concern if used?

Which of these should I be using? PKCS1 v1.5 seems a bit simpler to implement.

Generally you should not be implementing this yourself, there are plenty of libraries that implement these schemes out of the box.
Both the PKCS#1 v1.5 padding for signature generation and PSS padding have pro's and con's which I list below. Which one you decide to use it up to you.

Are there security concerns with each schemes I should be aware of?

PKCS#1 v1.5 padding has the following drawbacks.

It is deterministic, which is not a requirement for signatures and this can actually be detrimental to security in some very specific situations.
It's missing a security proof; PSS has a security proof (for the padding mode, not for RSA itself of course). That said, PKCS#1 v1.5 padding for signature generation has not been broken (unlike PKCS#1 v1.5 padding for encryption, which does have vulnerabilities).

PSS has  drawbacks as well:

it is more complex to implement;
it is definitely not as prevalent as PKCS#1 v1.5 padding - probably because PKCS#1 v1.5 padding is older and hasn't been broken;
it requires configuration (both during signature generation and verification).

If I need to use PSS, what digest should I be using? Is SHA1 a concern if used?

SHA-1 is definitely an issue if you would use it for hashing the message as part of the signature generation (regardless of the padding mode), as it isn't collision resistant anymore. A collision resistant hash is a requirement for signature generation algorithm.

PSS uses another instance of a hash function for PSS padding for a function called the mask generation function (MGF) which performs the actual padding. MGF1 is the only MGF defined for PSS, and it in turn requires a hash to create the PSS padding: the data hash value is input for MGF1.  MGF1 can be compared to HMAC when it comes to security, and SHA-1 is still secure in HMAC.
So SHA-1 isn't a problem if you just use it for the underlying MGF1 used within PSS padding. Of course, for new protocols you'd still go for a more secure cryptographic hash function such as SHA-512.
The two hash functions algorithms can be different than the one used for the data hashing. Some implementations default to SHA-1 and some default to the data hash algorithms. For some reason SHA-256 is often preferred for MGF1 although SHA-512 would make a lot more sense for RSA because it would be more efficient because of its larger output size. As indicated, complexity is a drawback of PSS - even when it comes to configuring the algorithm.
Quite often the hash used in MGF1 it is set to the same hash as used for hashing the message, and that's probably best if you want to remain compatible with most applications & libraries.
If you decide to use PKCS#1 PSS padding, be sure you document the algorithm you use for both the data and the MGF1 function.


Key exchange and authentication using libhydrogen I have been able to exchange session keys on two devices using Libhydrogen's Key exchange using the N variant method. I also want to authenticate both devices to have some protection against the Man in the middle attack. Can I use libhydrogen's Public key signatures method for that? If yes, how to use it with key exchange?

Q 1: This method generates a key pair for signing. Should I first transfer the public key of the server to the client? The client can then sign the session key and send it back to the server for verification? Would this work?

Q 2: Should the I use libhydrogen's signature method for authentication before the key exchange or after?

Any help would be appreciated.

All the key exchange schemes provided by libhydrogen (actually the Noise protocol) are secure against MITM.

With the N variant, the client has to know the server's public key, and will not return a valid shared key pair unless the response comes from a server that has the corresponding secret key.

If you need the server to authenticate the client as well, use the KK variant instead.

Signatures are not needed, unless you want keys to be signed by a certificate authority.


Can someone explain the ECB Penguin? I've seen the ECB Penguin used to demonstrate why ECB is not a recommended method of encryption, but I do not understand how this translates to text or passwords.

Aren't the people who create these images comparing apples and oranges?

For a real-world example of precisely the same ECB weakness leading to a massive password compromise, see the Adobe password database leak, as memorably illustrated in the xkcd web comic:
$\hspace{83px}$
(source: xkcd.com)
While there were several issues contributing to the scale of the compromise, one of them was that Adobe, instead of properly hashing the passwords, encrypted them using ECB mode instead.  Even though the attackers apparently did not get the encryption key (or, if they did, they chose not to disclose it), this still exposed several weaknesses that made the passwords much easier to guess:

The length of the encrypted data revealed the length of the password, rounded up to the next 8 bytes.  (This weakness is actually not specific to ECB mode, but I'm including it for completeness.)

Identical passwords produced identical ciphertexts, making it easy to locate frequently reused (and thus presumbaly weak) passwords, and also allowing multiple hints for the same passwords to be correlated as shown in the cartoon above.  (This is a weakness of ECB mode; it would not have happened if the encryption had been done using a semantically secure mode with a proper IV.)

Passwords with the same 8-character prefix yielded ciphertexts with the same first block, making it easier to guess the prefix by comparing hints.  Similarly, any multi-block passwords differing only in some of the blocks would yield partly matching ciphertexts, and any password that happened to contain repeating 8-character blocks (say, "passwordpassword" or "aaaaaaaaaaaaaaaa") would produce a repetitive ciphertext, just like in the Tux image example.


Is there a cryptographic primitive that allows "signature chaining"? Let's assume that a digital signature scheme $S$, which is secure against existential forgery under adaptive chosen message attack, can only be used with fairly short signature inputs, i.e. $S(sk, m)$ has a constraint of $len(m) < n$.

Is there a way to use this scheme in a way that gives stronger protection against forged signatures than the naive solution of signing the first $n$ bit of the output of a hash function over a message, i.e.

$S'(sk, m) = H(m)[0..n]$?

The security of $S'$ seems to be limited by the relatively short output of the hash function: Finding a hash that collides only in the first $n$ bits of a message pair $(m, m')$ allows for a forged signature, even though the asymmetric primitive itself might not allow for a forgery.

One way I can think of is to apply the signature function over slices of the hash output and concatenate the results, i.e.

$S''(sk, m) = S(sk, H(m)[0..n]) || S(sk, H(m)[n..2n]) ...)$,

but that would allow for the rearranging of the signed parts, which does not seem good.

When driven to the logical extreme, setting $n = 1$, it becomes obvious that any such scheme will fall apart, given that there are only two possible signature outputs that can be interpreted as logical zeroes and ones, and rearranged to form any desired hash output.

The scheme could be further improved by encoding the "block number" in the signature input, or by somehow chaining the hash output and the signature output with some feedback mechanism similar to some hash function or block cipher modes of operations, but I'm going to stop here since I'm assuming that what I'm trying to do is generally impossible:

Assuming that the number $i$ of signature operations that an attacker can perform is bounded to $i<\sqrt(n)$ (i.e. the birthday bound), is there a way to construct any signature scheme $S'$ that makes an existential forgery harder than $O(n)$ for an attacker, given the constraints on the atomic input into the asymmetric signature function?

And does the situation change if the adversary does not have access to $S$, but only to $S'$ (i.e., can $S'$ then be possibly made secure even for $i > n$)?

(I'm aware that the assumptions in my question might be a logical contradiction with the chosen security properties of the "atomic" signature scheme. In this case, let's assume that it is as secure as possible given the constraints, i.e. an input of only $n$ bit and no other user-controllable randomness, even though it might internally use a random padding scheme etc.9

Assuming that the number $i$ of signature operations that an attacker can perform is bounded to $i<\sqrt(n)$ (i.e. the birthday bound), is there a way to construct any signature scheme $S'$ that makes an existential forgery harder than $O(n)$ for an attacker, given the constraints on the atomic input into the asymmetric signature function?

It would appear that we can do better than that, assuming a bound on the number of valid signatures that can be generated.

Here's is one possible approach; we apply a randomized hash that converts the message into 5 different 64 bit values (perhaps the signer selects a random value and then hashes that value along with the message using SHAKE-256, squeezing out $5\cdot 64$ bits); then, you sign each 64 bit value using the asymmetric function.  Then, for the signature, you publish the random value and the 5 signatures.

To generate a forgery (assuming that the attacker cannot attack the 64 bit signature operation directly), the attacker would need to find a different randomizer/message pair that hashed to values that has already been signed (and so he can put together the signature using values he has already seen).

If we assume that the valid signer will sign no more than $2^{32}$ messages, that means that the attacker has (at most) $5 \cdot 2^{32} < 2^{35}$ 64-bits values for which he has the signature.  Then, for any randomizer/message pair he selects, he hashes it; if we treat the hash as a random Oracle, then that produces 5 random 64 bit values, without the attacker having any control of those values before he hashes them.  Each value has, at most, a probability of $<2^{35-64} = 2^{-29}$ of being a value he has a signature for.  To create a valid forgery, all 5 values need to be values he has signatures for, and so the total probability of success (for each trial) is no more that $2^{-145}$.  Hence, the expected number of trials the attacker needs to do before he is successful is $2^{145}$, which is considerably better than what you asked.


AES Encryption vs Decryption We recently learned about AES in class and it was heavily emphasized that encryption and decryption in AES are not the same because the functions are not reversible.
Why then, when we got to block ciphers, do certain cipher modes use the encryption function for both encryption and decryption?
The reasoning given was that XOR is reversible, but doesn't this contradict the first statement?

More than likely the wrong words were used in class, 'not reversible' was probably supposed to be tied to the understanding of Feistel type ciphers, where simply reversing the order of operations of the block cipher leads to decryption. We are talking about the block cipher here, not modes.
In AES, reversing the order does NOT lead to decryption, since not all the operations are their own 'self inverse' like they are in say, DES.
In AES, which uses a combination of MDS matrix multiplication, s-box lookups, and XOR, needs the inverse MDS matrix and s-box to decrypt when reversing the order of operations, in this case the subkey XOR does not change.
AES also offers something called Equivalent Inverse Decryption, which still needs using the decrypt matrix and s-box, but allows the order of operations to be the same as encryption. This works by changing some of the subkeys using the decryption operations. If you look at this from the start without a good understanding of the regular encryption and decryption functions and their component operations, it looks like witchcraft.
I recommend reading the original submission paper, which explains everything pretty well.


powers of g in $GF(256)$ The finite field $GF(256)$ is usually implemented $mod$ 0x11b to keep the numbers inside that field.
I understand that 0x11b was picked as it is the smallest irreducible polynomial that is greater than any number of $GF(256)$. This is sufficient for multiplication as any element of the field can be reached by multiplying two other elements from the same field and the result will also be inside that field.

Now I stumbled over powers in finite fields. By trying it myself I noticed that with $g=2$ not every element of $GF(256)$ could be expressed as $g^x$ when using $mod$ 0x11b. 0x11d has to be used instead for example. But when using $g=3$ I can use 0x11b again. And for $g=6$ I can use both. For $g=7$ I can't use either. So the choice of the irreducible polynomial depends on the generator $g$.

Does this mean unless you have tested the choice of irreducible polynomial $p$ throughly, you cannot use it for key exchange as proposed by Diffie-Hellman but you can use it for Elliptic Curves?

Is it even feasible to do both on a finite field?

Does this mean unless you have tested the choice of irreducible polynomial $p$ throughly, you cannot use it for key exchange as proposed by Diffie-Hellman but you can use it for Elliptic Curves?

Skipping the part about Galois fields (where you can easily map between different representations, and so the choice isn't important for security), for Diffie-Hellman, one thing that is important (if not sufficient) is the size of the subgroup that is generated by the generator.

If we pick a size that has a small factor $a$, the attacker can easily derive the values of our DH private keys modulo $a$ (with $O(\sqrt{a})$ work), and so we are leaking $\log_2 a$ bits.

Instead of targeting a generator that generates the entire group, we typically select a generator that generates a large prime subgroup of the group (in some happy cases, this prime subgroup will just happen to be the entire group; that's not the case here, unless we pick $GF(2^x)$ where $2^x-1$ is a Mersenne prime).

For $GF(2^8)$, the size of the multiplicative group is $255 = 17 \times 5 \times 3$; obviously, the largest prime-sized subgroup is 17 (and there will be 16 generators for that subgroup).  This is obvious far too small to be secure, but selecting a generator of a subgroup that size would be more typical of how we use Diffie-Hellman.


Question about dual system encryption Recently, I have been reading some dual system encryption papers. In these systems, is the adversary able to generate “semi-functional ciphertexts”?

In these systems, is adversary able to generate semi-functional ciphertexts?

Quoting the paper figlesquidge mentioned in a comment:

  Crypto 2009
  Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions
  Brent Waters

  Abstract: We present a new methodology for proving security of encryption systems using what we call Dual System Encryption. Our techniques result in fully secure Identity-Based Encryption (IBE) and Hierarchical Identity-Based Encryption (HIBE) systems under the simple and established decisional Bilinear Diffie-Hellman and decisional Linear assumptions. Our IBE system has ciphertexts, private keys, and public parameters each consisting of a constant number of group elements. These results are the first HIBE system and the first IBE system with short parameters under simple assumptions.

  In a Dual System Encryption system both ciphertexts and private keys can take on one of two indistinguishable forms. A private key or ciphertext will be normal if they are generated respectively from the system's key generation or encryption algorithm. These keys and ciphertexts will behave as one expects in an IBE system. In addition, we define semi-functional keys and ciphertexts. A semi-functional private key will be able to decrypt all normally generated ciphertexts; however, decryption will fail if one attempts to decrypt a semi-functional ciphertext with a semi-functional private key. Analogously, semi-functional ciphertexts will be decryptable only by normal private keys.

  Dual System Encryption opens up a new way to prove security of IBE and related encryption systems. We define a sequence of games where we change first the challenge ciphertext and then the private keys one by one to be semi-functional. We finally end up in a game where the challenge ciphertext and all private keys are semi-functional at which point proving security is straightforward.

(bold emphasis mine)

I would have loved to add more, but your question can simply be answered with a humble “yes”.


Can hash functions improve a lousy PRNG? If I have a poor PRNG, could a cryptographically secure hash function make a better output?

Say the PRNG can produce as much numbers as you wish, reasonably random, but not good enough to be used in crypto applications.

If I split the PRNG output into chunks, say $128..512$ bits, and feed those to a cryptographically secure hash function, could it be that the result is somehow "better" or more secure than the original pseudo random string?

If I got it right Fortuna does something like that. Could it be?

Yes, you can certainly do this, and there has been a lot of theoretical work in the area. At a high level, what this is called is a randomness extractor (Wikipedia):

  A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed.

Dodis, et. al. study different practical constructions of randomness extraction, including using CBC-MAC, Cascade, and HMAC. Your proposal is most similar to the Cascade method they talk about. For which they say:

  In Section 4 we study the cascade
  (or Merkle-Damgard) chaining used in common hash functions such as
  MD5 and SHA-1. We show these families to be good extractors when modeling
  the underlying compression function as a family of random functions. However,
  in this case we need a stronger assumption on the entropy of the input distribution.

See the paper for the exact requirements. It has been a little while since I have thoroughly parsed that paper, but I believe that CBC-MAC and HMAC have better security guarantees (fewer assumptions).

Another paper you may be interested in is A model and architecture for pseudo-random generation with applications to /dev/random by Barak and Halevi. They present a construction which uses an extractor to build a PRNG. They note that their construction is similar to Fortuna. They do list some potential issues they see with the Fortuna construction that you may find interesting (depending on what you are really trying to accomplish). For their extractor in $\S$4.1, they describe some of the tradeoffs between using AES-CBC and HMAC-SHA1 and in the end state that:

  A candidate cipher for this implementation is Rijndael,
  which has a variant with 256-bit blocks. (This last alternative would probably be our choice if we
  had to actually implement a robust generator.)


What makes AES look like an ideal cipher? There are 2128! permutations on 128-bit inputs. AES supports a maximum key length of 256 bits, therefore offers at most 2256 permutations. The total number of 128-bit permutations is much larger than what offered by AES, which means AES actually only explores a very tiny portion of the permutation space.

Questions:

Given AES doesn't support > 256-bit key length, what makes people believe AES (or any "good" cipher currently being used) would look similar to the ideal cipher that chooses a 128-bit permutation randomly? Put it another way, what makes people believe AES is better than another cipher with 256-bit key length which can give 2256 different permutations?
Is it possible to develop an ideal cipher with enough key length which runs encryption and decryption in polynomial time? The key length would be at least log((2128)!). My poor math gives a result somewhat close to 128*(2128). So I guess the answer to this question would be no. But it strengthens Question 1 by giving an idea how insufficient AES key length is: The ideal cipher requires an exponentially larger key length.

AES is not an ideal cipher, nor is it intended to be an ideal cipher. AES is meant to be a practical cipher that offers a strength close to the key size. That means it is computationally infeasible to find the key even if given the plaintext and the ciphertext. AES - when correctly used with a strong mode of operation - produces ciphertext is indistinguishable from random if the adversary can choose the plaintext input to the cipher themselves (IND-CPA).

The next question is why people think that AES is better than other ciphers with the same key size. Cryptographers generally don't really think that. There are other ciphers that may have better characteristics when it comes to protection against side channel attacks. Other ciphers have a larger % of rounds to spare when it comes to protection against certain attacks. Or they may have a larger block size, or they do not have a clear mathematical structure etc. etc.

AES has been studied a lot, and few attacks have come close to breaking AES. It is relatively fast compared with other block ciphers, and it has a serviceable key and block size. The algorithm is well understood, and there are many hardware implementations of AES, including newer x64 and ARM CPUs. So it is standardized, popular, well understood, but not necessarily the most secure cipher. It doesn't need to be, for most situations it is secure enough.

When you are talking about implementing an ideal cipher you seem to go over the key requirements of a one time pad. The one time pad requires a key the same size as the plaintext / ciphertext. Moreover, you won't be able to distinguish a good key from a bad key for a single block. But what happens if you have multiple blocks to compare? With each block a specific key becomes more likely. As such, it makes very little sense to try and create an ideal block cipher.

The ideal cipher is mainly a theoretical construction, useful in proofs. But beware that inserting an actual block cipher in place of an idealized block cipher may not result in a secure construction. For instance, a hash function could well be secure when constructed using an ideal cipher, while it could be vulnerable with AES-256 due to related key attacks.


Can a hash have more than one input? From a definition stand point, can a hashing algorithm have more than one input, ex: $H(m_1, m_2, m_3)$?

If not why are algorithms like bcrypt, scrypt and pbkdf2 referred to as password hashing algorithms?

The standard definition of a hash function is from arbitrary length bitstrings to a constant length bitstring. That is, there is only one input. Password hashes, like keyed hashes (MACs, more or less), have more than one input. There is no contradiction there, since password hashes are not cryptographic hashes - thought they may be built from cryptographic hashes like PBKDF2 (or even vice versa).

(Password hashes are called that largely for historical reasons. Normal hash functions used to be used for the same purpose, but that is not as good an idea.)

In practice, you will find notation where a hash function does have multiple inputs. That usually means that the inputs are encoded into one and then passed through the hash function. The encoding can be as simple as concatenation or it can add something extra to make inputs unique and prevent collisions.


Fairness in Multi party computation Why for achieving the fairness, less than a half of the parties should be corrupted? ($t<m/2$, where $t$ is the number of corrupted parties and $m$ is the total number of the involved parties). How should I prove it? In what kind of network this proposition holds? (Broadcast or peer to peer network)

You should definitely read the original paper by Cleve in which this was proven.

To get some intuition, imagine that $2t = m$ and consider the following

For the protocol to be secure, no set of $t$ corrupt parties should be able to "reconstruct" the output by themselves.
For the protocol to be fair, the set of $m-t=t$ honest parties should be able to "reconstruct" the output by themselves.

Now, the problem is that you cannot distinguish which parties are corrupt and which are honest (otherwise the MPC problem would be trivial: simply discard the malicious nodes and work only with the honest ones), so you need to satisfy the two conditions above for any set of $t$ parties, which is clearly a contradiction.


What is stopping someone from saving encrypted info, and decoding it later? When I send encrypted data to a website, using public key encryption, what is stopping someone who is listening from storing my encrypted data, and decryption it in a few years after they have determined the private key?

From my understanding, private keys can be discovered after a few years using a fast computer.
Are there any time-sensitive safeguards used with public key encryption so that my info won't be useful in a few years?

Decoding information within a time frame is of absolute importance.

Say X is an terrorist, the information of his attack will be useful today, not years after the attack has happened. And similarly decoding your message is important today, not years later. Also there might be a possibility that when somebody has decoded your key for future use, you might have already changed it.


Cracking passwords with more than 10 characters in a few hours? I came across this article from 2 years ago: http://www.dailymail.co.uk/sciencetech/article-2331984/Think-strong-password-Hackers-crack-16-character-passwords-hour.html

They're describing how a team of "hackers" cracked passwords such as this "qeadzcwrsfxv1331" or this "Qbesancon321" in just a few hours. How is that even possible? I've seen before people describing passwords with 12 characters or more (16 in the above case) to take supposedly thousands of years to crack. What's going on in this case? Ok, so in this case the team had the hashed passwords available, but a 16 character password in a few hours?

Like Ricky Demer suggested, qeadzcwrsfxv is a common finger pattern (similar to something like asdfghjk).

The second example falls in the pattern of: Take dictionary word (besancon is the name of a city), uppercase the first letter and add a couple of digits after it (usually 123, 321, 007 or a year like 1998). Then a couple of rule-based alterations are tried: add a random letter, change a letter to a symbol (e.g. s => $) and so on.

A third way one of these passwords could have been cracked is by them being reused from another hack (e.g. the user used a variation of the password he used from linkedin).

In short, humans are very predictable in how they generate passwords.

A truly random password looks like this: T8vWdvLGhpRi9Gb. No discernable words or patterns. Numbers, lowercase and capital letters properly mixed together.  A password like this could only be broken by being reused on multiple websites or by being intercepted somehow.


How does certificate-based encryption solve key revocation problem? How does certificate-based encryption solve key revocation problem?

For example, if a user accidentally reveals its secret key or an attacker compromises it, the user may request revocation of its certificate. Alternatively, the user's company may request revocation if the user leaves the company or changes position and is no longer entitled to use the key.

My questions are:

How can we do this process in certificate-based encryption and how different is it compared to PKE (that uses CRL or OCSP for certificate revocation)?
In the case of signature, how can a user verify the validity of verification keys? How can the user check whether the key is valid and not revoked?

The revocation status of a certificate is application dependent, meaning that if the application under which you perform the encryption or decryption does not check for revocation status with the CA, then you may still proceed and encrypt or decrypt the message.
You should consider the loss of a private key of a certificate as a loss of your password in a symmetric encryption environment. The same argument applies to PKE.

The same applies to a signature verifications: a well behaved program should check the revocation list when verifying a signature, but this depends on the application developer interests. I can verify a signature as a valid one in certain programs without consulting a revocation list at all.
You can easily test this, for example, by checking on a signed windows program on a computer that is not connected to the internet (look at the Digital Signature tab in the Properties pop-up dialog box of a signed executible): The digital signature of the program would be reported as OK (if indeed nobody messed with its bits) even though the revocation list has not been consulted.


Does GCM improve the strenght of weak passwords? If I am encrypting a file with GCM/AES256 with a weak key (say a sha256), does the fact that it takes time to brute force a long message improve my security?

Example:
I use the sha256 of "ARainyDay" to encrypt a 1kB file.

To brute-force it, one must still try and decode my file 5429503678976 times (26^9).

Even considering 1ms/try, it still takes 62841 days.
That makes my key more secure then?

No, it doesn't make weak passwords magically stronger.  If they know part of the file (e.g. the header), or even is just able to recognize it, what they can do is, for each plausible password, just decrypt that small area of the file (and ignore everything else), and see if the decryption of that area is plausible.  Once the password guess passes that check, they can then do a full decryption and see if everything checks out.

To make brute forcing a weak password more difficult, I would suggest a strong (expensive) password hashing method, such as Argon2.

BTW: the estimated time of 1 msec to decrypt a 1kbyte GCM-encrypted file is far too large; I would expect that an adversary might be able to do it in perhaps within a few microseconds...


Named Elliptical Curve parameters Are named curve parameters always the same? I know this may be a stupid question however I think this is the case. For example the secp256r1 is defined in this documet http://www.secg.org/SEC2-Ver-1.0.pdf.

They are de facto conventions that somewhere may not being followed. I think the one you mention has started with the P1363, but not sure if there is something previous.

It is the first thing one have to check in any document: which is the naming convention followed there. Perhaps also is useful to see from there some of them comes. The Weierstrass Normal Form (or WNF) can be saw as:

$y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}$

And usually uses it reduced form when is defined over $\mathbb{F}_{p}$ as:

$ y^{2} = x^{3} + ax + b $

On characteristic 2 ($\mathbb{F}_{2^m}$), I think is more usual the form:

$ y^{2} + xy = x^{3} + ax^{2} + b $

Different names for the same parameters and even mixing them. Not forgetting that there are many more curve representations, one each you can find even different conventions.

Then points naming can change from one document to another, where is usual to see $G$ as the generator (also represented as $<G>$), but cannot be assumed because you can see a $P$ or $Q$ or $R$.

I think coherence is important and where ever it's used, the convention must be described at the beginning and followed to the end. This convention you mention, perhaps is the more spread.


Lagrange Gauss Reduction Algorithm Sorry if my question is trivial. My question is related to a post "Paillier Homomorphic encryption to calculate the means" where a member suggests Lagrange Gauss Reduction Algorithm for reducing a decrypted value to a rational number. How to use Lagrange Gauss Reduction Algorithm for reducing numbers? Here is the link to the original post: Paillier Homomorphic encryption to calculate the means.

Lagrange-Gauss algorithm can also be seen as LLL in dimension 2.  Here is an implementation using GP/Pari:

\\ Given A modulo N, it returns a fraction u/v s.t. A = u/v (mod N)
Gauss(A,N) = {
  local(L,L3);

  L = [1,0;lift(A),N];
  L3 = L*qflll(L);

  return(L3[2,1]/L3[1,1]);
}

EDIT: Consider the lattice defined by the two column vectors $\begin{pmatrix}1\\A\end{pmatrix}$ and $\begin{pmatrix}0\\N\end{pmatrix}$.  The vectors in the lattice are:
$$\alpha  \begin{pmatrix}1\\A\end{pmatrix} + \beta \begin{pmatrix}0\\N\end{pmatrix} = \begin{pmatrix}\alpha\\ \alpha A + \beta N\end{pmatrix}$$
As we are in dimension 2, LLL will return the shortest (non-zero) vector in the lattice.

Let's call $$\vec{v} := \begin{pmatrix}v_1\\v_2\end{pmatrix} = \begin{pmatrix}\alpha^*\\ \alpha^* A + \beta^* N\end{pmatrix} \in \mathbb{Z}^2$$
the vector returned by LLL: $v_1$ and $v_2$ are small.  Clearly, we have
$$v_2 = \alpha^* A + \beta^* N \equiv \alpha^* A \equiv v_1 A \pmod N$$
and thus
$$A \equiv \frac{v_2}{v_1} \pmod N$$
with $v_1$ and $v_2$ small.


What is wrong with using SHA1 in digital signatures? Why is a robust hash function needed? For the purposes of signing and verifying signatures, what is the value of the hash function?

Why would it matter if SHA1 is later determined to be easy to break? Since a Public/Private key process is still used, is SHA1 only a utility to create smaller data to sign?

The data itself is also sent in the clear most of the time.

A digital signature scheme has some size on which it works (e.g. what kind of messages can be signed). This message size is usually related to the key size, and smaller than most interesting messages you would want to sign.

So we use a hash function, which maps an arbitrary-length message (there is some theoretical upper size limit with most hash functions, but this is not relevant in practice) to a fixed length hash, and then use this hash as input to the signing function.

For the use for digital signatures, we need the collision resistance property of the hash function:

It should be very hard to find a pair of messages $x \neq x'$ such that $H(x) = H(x')$.

Without this property, an adversary could produce two different messages with the same hash, give me one (innocent looking one) to sign, and later come and show the other one (for which the same signature will fit, too).

Other interesting properties for cryptographic hash functions are preimage resistance (given a hash $h$, it should be hard to find a message $x$ with $h = H(x)$) – this is not that interesting by itself, since we usually already know the signed message – and second-preimage resistance (given a message $x$, it should be difficult to find a message $x' \neq x$ with $H(x) = H(x')$) – this is needed to prevent the attacker to create a second message which has the same hash as one I already signed.

Rob in his answer elaborated a bit about whether or not the found collisions (or second preimages) would be of a valid message format. While it might be that collisions with invalid messages are easier to find, with a brute-force collision search we can principally create messages of any valid format (as long as there are enough bits left to manipulate) with any given hash. If the hash function is secure, brute-force is the best way to find (second) preimages or collisions, and then the hash output size (as well as the time for one hash evaluation) becomes the limiting factor for security. (Assuming, of course, that the signature scheme itself is secure.)

For MD5, the collision resistance is effectively broken, i.e. it is not that hard to create two messages, which only differ in some part in the middle, and have the same hash. This was used in a famous attack to let a CA sign a bogus certificate.

As SHA-1 has a similar structure as MD5, it is expected that there will be found weaknesses, too, and SHA-2 (i.e. SHA-256 or SHA-512) are preferred today.

There was a competition running to define SHA-3, which should be even more secure than SHA-2. The Keccak hash function family won this competition, and in 2015 the SHA-3 standard was officially released in FIPS 202. SHA-3 has a quite different structure than MD5, SHA-1 and SHA-2, so it is expected that any weaknesses there will not carry over.

When designing a new protocol, try to do it in a way that the hash function can switched out, so you can use either SHA-2 or SHA-3 when the other one shows creaks.


Does semi-honest adversary eavesdrop honest parties communication? Assume we have a multi-party computation protocol and the protocol definition, where both of them consider a semi-honest adversary, without explicitly assuming the type of channel the parties want to use.

Also, assume three parties are involved in the protocol: two clients and a server. Let a client encrypt its input under the public key of the other client and send it to the server, where the server somehow computes the result and send it to the other client.

The protocol is proven in the case where a party is corrupted at a time by a semi-honest adversary

Question: Can we say that the protocol is insecure because a corrupted client can eavesdrop the communication between the other client and server and learn some information? Or we can say that the protocol implicitly assumes the parties are using a secure channel (e.g. TLS)?

Typically in the MPC literature it is assumed that there are pair-wise secure channels between all parties. So I would say it is the latter in the case of your question.


Hashing entropy generator output with SHA256 I'm using SHA256 to hash the output of an entropy generator to generate random numbers. Is it generally better to treat the output of the entropy generator as single messages and hash each of those separately (internal state is reset), or as a message of unknown length (internal state is preserved)?

Generally seeds for PRNG's should be mixed in with the internal state using a hash function, and the output should be at least a hash away from the internal state. You could take some hints from the implementation of SHA1PRNG in the Sun JCE or from other hash based PRNG's on how to do this.

You do not want to forget the internal state, because in that case the output is fully dependent on the seed. If there is any problem with a seed, you would have predictable output.


Algorithm/encryption technique which outputs a set number of numerical digits e.g. 20 digits from a given input What the name of the algorithm/encryption technique which outputs a set number of numerical digits e.g. 20 digits based on some input.

You can input some data e.g. text or numbers but the output is always 20 unique digits.

If you put the same input, it should give you the same output.

Your question is not clear. Any deterministic compression functions an answer to your question.

$$C:\{0,1\}^* \to \{0,1\}^\ell$$ where $\ell$ is the output range, (20 numerical digits in your case and this may require some conversion from bits to digits).

A simple one is zipping with trimming. Zip the trim to 20 numerical digits.

However, in Cryptography we want the compression functions as one-way compression functions.

You may also be asking, the Cryptographic hash functions which are also one-way compression functions with pre-image resistance, secondary pre-image resistance, and collision resistance are required.

\begin{alignat*}{2}
  H:\{0,1\}^*&\longrightarrow& \{0,1\}^\ell \\
  \mathbf{m}&\longmapsto& H(\mathbf{m})
\end{alignat*} where $\ell$ is the output range. The definitions of resistances are;

Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=H(m)$. Consider storing the hashes of passwords on the server. Eg. an attacker will try to find a valid password to your account.
Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ such that $m_1 \neq m_2$ and $H(m_1)=H(m_2)$. If possibe this can lead producing a forgery of a given message.
Collision resistance : if it is  computationally infeasible to find two inputs $a$ and $b$ such that $H(a)= H(b)$ with $a \neq b.$

The generic attacks on hash functions have the following complexities:

$$
\begin{array} {r|r}
& \text{Classical} \\
\hline
\text{Preimage attack} &  \Theta(2^{\ell})\\
\text{Second-preimage attack} & \Theta(2^{\ell}) \\
\text{Collision attack} &  \Theta(2^{\ell/2}) \\
\end{array}
$$

Your case, however, is a 20 numerical digits output, this is not secure since, 20 numerical digits has $\approx 67$ bits. In today standards, this is considered as trivially broken (computationally) since a collision attack with generic birthday attack on hash functions with $2^{67}$ output is $\sqrt{2^{67}} =  2^{33} \sqrt{2}$ with 50% probability. In, today's computing power, SHA-1 with 160-bit output is not considered secure for cryptography and removed from the standard.

You should use, at least, a secure hash function with around 256-bit output size like SHA-224, SHA-256, SHA-512 or SHA-3 series. You should not trim the output that falls into the computational feasibility of the attacks.


Can a server's ECDSA fingerprint be spoofed during SSH? I have read somewhere that Servers which have SSH access for users in the public can have their public key posted publicly (e.g., on a website), so that people who access such a server using SSH can use this key to verify the server's fingerprint.

My question: If the public key is accessible to the public, cant a malicious user get it and exploit it to 'man-in-the-middle' people who try to connect to this server?

What exactly is in this SSH fingerprint. Is it just a public key that has been hashed? Or is it server-specfic information that has been encrypted (or signed) by the server's private key?

Yes OpenSSH's fingerprint is a hash of the publickey, and (except SSHv1 keys aka -t RSA1 which is long broken and should never be used) specifically of the publickey format stored in base64 in (usually) /etc/ssh/ssh_host_${alg}_key.pub which is the wire encoding in the relevant KEX-reply message depending on key type (currently RSA, DSA, ECDSA, ED25519). See https://superuser.com/questions/421997/what-is-a-ssh-key-fingerprint-and-how-is-it-generated

Traditionally this hash has been MD5, and displayed in hex with colons between each byte. OpenSSH recently (6.8 in March 2015) switched to SHA256, displayed in base64, by default; you can get the old one with FingerprintHash option on client, or -E option on ssh-keygen -l; see the man pages for ssh_config and ssh-keygen if you have a recent version, or see online http://www.openssh.com/manual.html for the latest version.

OpenSSH also supports displaying this hash (now either SHA256 or MD5) in an ASCII-art form that is supposedly easier to compare visually. IME this is rarely used. But then IME users rarely verify the fingerprint at all.

Yes, if a MitM can intercept your first connection to an SSH server AND feed you a wrong fingerprint you are pwned. The most conservative advice is you should get the fingerprint from an admin or other 'reliable' person face-to-face, or over the phone if you know their voice well enough to distinguish from an imposter, or other out-of-band secure means like registered mail. But in today's world, especially when dealing with lots of systems and many of them far away or in the cloud, this is often impractical.
If the fingerprint is on an HTTPS website (with certificate, ciphersuites and protocol version up to current standards) -- and the website itself isn't hacked (which has been known to happen) -- that's usually good enough.

But SSH clients are supposed to, and OpenSSH in particular does, remember the previously seen publickey (the whole key, not just the fingerprint) for each server, so if you get the first connection securely and MitM intercepts a subsequent connection it detects the discrepancy and gives you a big ugly error message with lots of uppercase and atsigns about 'WARNING! REMOTE HOST IDENTIFICATION HAS CHANGED! Someone could be eavesdropping on you!'.

However, if the server legitimately replaces its key(s), as they sometimes must or otherwise do, you get this same alarm, so as with all alarms that are often false, most people soon ignore them, or set the option (StrictHostKeyChecking no) to suppress them -- and advise others to do the same.
Also, if the client 'loses' its memory (for OpenSSH in the file ~/.ssh/known_hosts), you are back to the vulnerable initial connection state. For example your PC became obsolete or just unfashionable and was replaced and you didn't copy this file, or it was lost or destroyed (or stolen) and replaced, or the filesystem or disk was accidentally overwritten or corrupted and your data lost, or you just decided to delete it.


Is 512-bit RSA still safe for signature generation? The standard CSP on Windows XP only supports RSA up to 512-bit, which means that it's the maximum key size I can use for authenticity verification of updates. The public key is embedded in the updater, and the update files are signed with the private key, using SHA256.

I know that RSA-768 was factored back in 2010, which is what makes me wonder if RSA-512 is still acceptable for signing purposes. How much effort is it for an attacker to break a 512-bit RSA key?

I don't have any experience with this myself, but Tom Ritter talked about this on twitter:

Matthew Green: Out of curiosity: do you happen to know offhand how much it costs to factor a 512-bit RSA key on EC2?
Tom Ritter: My personal costs are \$120-\$150 with my setup. You can probably do it cheaper, heard reports of \$75.

He also published a description of how to factor RSA moduli.

Another project in a similar vein: Factoring as a Service:

The Factoring as a Service project is designed to allow anyone to factor 512-bit integers in as little as four hours using the Amazon EC2 platform for less than $100, with minimal setup.

You should be able to just run the scripts from their github.


2Des is double secure of DES? I read this question in my book (that doesn't have a response).

2DES is doubly more secure than DES?

I know that 2DES can be attacked from meet in the middle attack.

In fact, from Wikipedia Meet in the middle say :

  The MITM attack is one of the reasons why Data Encryption Standard
  (DES) was replaced with Triple DES and not Double DES. An attacker can
  use a MITM attack to bruteforce Double DES with 2^57 operations and
  2^56 space, making it only a small improvement over DES.[5] Triple DES
  uses a "triple length" (168-bit) key and is also vulnerable to a
  meet-in-the-middle attack in 2^56 space and 2^112 operations, but is
  considered secure due to the size of its keyspace.[1][2]

But DES use key from 2^56. 2DES with meet in the middle have 2^57 operation (that is exactly a double of 2^56)
I'm not sure if the question ask a "doubly secure " in order to key space , so want a key big as 2^112 (that is double of 56 in previous DES).

I think that DES is double secure from this other phrase on Wikipedia that says:

  Diffie and Hellman first proposed the meet-in-the-middle attack on a
  hypothetical expansion of a block cipher in 1977.[3] Their attack used
  a space-time tradeoff to break the double-encryption scheme in only
  twice the time needed to break the single-encryption scheme.

So if 2 times Diffie/Hellman uses twice time to break the algorithm, also for 2DES we can use a double time of DES to break this algorithm.

Anyone can confirm my hypothesis?

The Meet-in-the-Middle attack was (first?) exposed publicly in the context of DES by Whitfield Diffie and Martin E. Hellman, in Exhaustive Cryptanalysis of the NBS Data Encryption Standard (published in IEEE Computer magazine, 1977). In this attack, if we count only the time spent doing DES computations (thus discount the time and cost of memory and memory accesses), then we can find the 112-bit key of 2DES from a few known plaintext/ciphertext pairs using only a little more than twice the time it takes to find the key in DES. The factor is actually closer to 17/8 for worst-case time; and closer to 3 for average time.

That's a strong indication that 2DES is over twice as safe against key search as DES is, given a few plaintext/ciphertext pairs. That's (slightly over, but most importantly only) 1 useful extra key bit out of 56 (or over 55 under CPA due to the complementation property), when examination of the key space would (wrongly) conclude 56 extra key bits.

But the question can be understood as asking to confirm that 2DES can be broken with about twice the time it takes for DES. That's a broader statement, and very wrong in practice. Fact is, cost of memory and cost and time of memory accesses make a straight MitM attack impractical.

There are practical alternatives to straight MitM, but the increase in time is much larger than a factor 2. As far as I know, the best reference on that is section 5.3 in Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Application (1996), published in Journal of Cryptology, 1999. They state that 2DES offers "only 17 more bits of security" than DES does (that would still be over a hundred thousand times more).

Additionally: key search is far from being the only cryptanalytic attack. Sometime the 64-bit block size is the weak spot, and 2DES is just as weak as DES from that standpoint (see Sweet32 attack pointed by Lery in comment). Also, a DES key can sometime be found other than by key search, e.g. by compromise of a device holding the key (in which case the duration of the attack is often essentially independent of the number of chained DES), or Differential Power Analysys (in which case 2DES or 3DES often are only marginally more secure that DES).


Disadvantage of the using a counter within plain text for encrypting with AES256 and authentication? What if we use a counter within the plain text and then encrypt the plain text with aes 256 to encrypt & authenticate?

For example:

encryptAES(32bit_counter+plain_text_of_96bit);
or
encryptAES(16bit_counter+plain_text_of_112bit);

This way we do not need to depend on other authentication algorithms and can send about 2^32*96 ~= 48 GB of data using single key.

User can also adjust their counter length & massage length and they can start using a new key by securely exchanging a new key before reaching maximum data transfer limit.

So is there any disadvantages of using this method except reduced data transfer rate?

Is this authentication method better than available cryptographic hash functions?  (How much future proof this method is, considering weakness of cryptographic hash functions to collision attacks & length extension attacks? Ref: Comparison of SHA functions).

So is there any disadvantages of using this method except reduced data transfer rate?

Actually, that's a fairly major one; however another one is the possibility of someone injecting random changes undetected.

Suppose an attacker took a ciphertext block, and replaced it with random data.  Then, when you decrypt, what you come up with is effectively random data.  If the sequence number looks correct (probability $2^{-32}$ or $2^{-16}$, depending on the tag size), then it'll be accepted.  This is a higher probability than many applications will accept.  The attacker has no control over what the decryption is, for some attacks, this might be sufficient.

  Is this authentication method better than available cryptographic hash functions?

You might turn that question around; how is this method even as good as standard methods (for example, GCM)?  It uses more bandwidth, and it has weaker modification detection probability.


Building index for Bloom filter using cryptographic hash functions I want to apply this secure index scheme for my Bloom filter, i.e. to use secret keys to insert items into the filter. In the paper to insert a word $w$ to the Bloom filter, they use a set of $r$ keys $\{k_1,...,k_r\}$ and calculate $r$ values $h_1 = h(w,k_1), h_2(w,k_2),...,h_r = h(w,k_r)$ as the bit positions. Actually I don't quite understand how the bits are really obtained from the hash values, let's say my filter has 1024 bits, should I use $h_r \% 1024$? And now since I want to reduce the computation, I use only 1 key $k$ and divided the value $h(w,k)$ to $r$ chunks of 10 bits. The value of each chunk will serve as 1 index. Will this scheme make my bits less uniformly distributed?
EDIT: added more information

At a glance, it seems that the paper you linked to does not actually specify how to convert the PRF outputs to Bloom filter indexes.  As far as I can tell, however, any scheme that does not introduce a significant bias should be fine.  For example, if the Bloom filter array size $m = 2^b$ is a power of two, simply taking the first (or last, or any) $b$ bits of the PRF output should be fine.  For non-power-of-2 array sizes, reducing the $s$-bit PRF output modulo $m$ should also be acceptable, at least provided that $m \ll 2^s$.

Indeed, the method used to convert the PRF output to the Bloom filter array index should not have any effect on security, since the conversion is only applied to PRF outputs which, by definition, are effectively indistinguishable from random.  However, obviously, a highly biased conversion method could reduce the entropy of the index distribution, and thus increase the false positive rate.

BTW, looking at the scheme presented in the paper, the use of $r$ separate PRF invocations seems somewhat inefficient, both in terms of processing speed and in terms of the size of the "trapdoor" representation.  As far as I can see, a more efficient variant of the scheme would look something like this:

  Let $m = 2^b$ be the array size and $r$ the per-element index set count of the underlying Bloom filter, and let $s$ be an arbitrary security parameter (say, $s = 256$).  Choose the PRF families $f_T : \{0,1\}^* \times \{0,1\}^s \to \{0,1\}^s$ and $f_B : \{0,1\}^* \times \{0,1\}^s \to \{0,1\}^{rb}$ (where, as in the paper, the second argument denotes the key input).

  For example, for $s = 256$, we could choose $f_T(w,k) = \text{HMAC}_{\text{SHA256}, k}(w)$ and define $f_B(d,k)$ as the first $rb$ bits of $$\text{HMAC}_{\text{SHA256}, k}(1 \,\|\, d) \,\|\, \text{HMAC}_{\text{SHA256}, k}(2 \,\|\, d) \,\|\, \dots \,\|\, \text{HMAC}_{\text{SHA256}, k}(\lceil rb / 256 \rceil \,\|\, d),$$ where the numeric prefixes are all padded to some fixed length.  Alternatively, we could just instantiate both $f_T$ and $f_B$ with KMAC (possibly with different customization inputs, although that shouldn't actually be necessary).

  Define:

  $\textsf{Keygen}(s)$: Choose a random $s$ bit master keys $K_{priv}$ and return it.
  $\textsf{Trapdoor}(w, K_{priv})$: Given an arbitrary word $w$, output its trapdoor representation $T_w = f_T(w, K_{priv})$
  $\textsf{BuildIndex}(D, K_{priv})$: Given a document $D$ with unique ID $D_{id} \in \{0,1\}^*$ and a list of distinct words $(w_1, w_2, \dots, w_t)$, initialize the $m = 2^b$ bit Bloom filter array $B$ to all zeros and, for each word $w_i$:

  Compute the trapdoor token $x_i = f_T(w_i, K_{priv})$.
  Compute the $rb$ bit codeword $f_B(D_{id}, x_i)$ and split it into $r$ indices $(y_{i,1}, y_{i,2}, \dots, y_{i,r})$ of $b$ bits each.
  Set the bits $y_{i,1}, y_{i,2}, \dots, y_{i,r}$ of the Bloom filter array $B$ to $1$.

  Finally, to hide the number of distinct words in the document, pick (with replacement) $(u-t)r$ additional random bits of the Bloom filter array $B$, where $u$ is some publicly known upper bound on the number of words in the document $D$, and set them to $1$.  Output $(D_{id}, B)$ as the index of the document $D$.
  $\textsf{SearchIndex}(T_w, D_{id}, B)$: Compute the $rb$ bit codeword $f_B(D_{id}, T_w)$ and split it into $r$ indices $(y_1, y_2, \dots, y_r)$ of $b$ bits each.  Output $B_{y_1} \land B_{y_2} \land \dots \land B_{y_r}$, where $B_i$ denotes the $i$-th bit of the Bloom filter array $B$, and $\land$ denotes bitwise AND.

With these modifications, the "trapdoor" tokens are only $s$ bits long (rather than $sr$ bits as in Goh's original scheme), and computing them requires only one PRF invocation.  Similarly, e.g. using the HMAC-based construction of $f_B$ above, an insertion or a lookup of each word requires only $\lceil \tfrac{rb}\ell \rceil$ HMAC invocations, where $\ell$ is the HMAC output length, rather than $r$ invocations as in the original scheme.  Since typically $b \ll \ell$, this also saves considerable computation time.

BTW, note that this "double PRF" design looks quite similar to the "extract and expand" paradigm used in some key derivation functions like HKDF.  Indeed, we could implement $f_T$ as HKDF-Extract (which is really just HMAC) and $f_B$ as HKDF-Expand (which is similar to the simple concatenated HMAC scheme described above).  In effect, the client wishing to query the index for a word extracts a pseudorandom key (PRK in HKDF terminology, trapdoor in Goh's terminology) from their private key using the query word as the salt, and then sends this PRK to the index server, which expands it into a distinct Bloom filter index set for each document (using the document ID as the "context specific information" to make the index sets distinct).

Also note that the scheme described above can be modified to support hierarchical indexing, arbitrary updates, occurrence search, IND2-CKA security and/or boolean (or limited regexp) queries in exactly the same ways as Goh's original scheme.  However, the shortened trapdoor tokens do prevent the use of the "heuristic security increase" technique (i.e. sending only part of the token to the server to hopefully disguise the word being queried) described in section 5.1 of the paper.

Of course, I cannot guarantee that I haven't made some silly mistake above that somehow compromises the security of the modified scheme, nor have I carried out a detailed security analysis like the one given for the original scheme in the paper.  All I can say is that, as far as I can tell, it looks to me like it should be just as secure as the original scheme.


Homomorphic Encryption - Smart Vercauteren Batching I'm going through Smart and Vercauteren's paper "Fully Homomorphic SIMD operations" and had a question about some notation used in the paper.

In section 2 of the above it is stated that for each monic polynomial $F(X) \in \mathbb{F}_2[X]$ of degree $N$ that splits into $r$ distinct irreducible factors of degree $d = N/r$ viz. $F(X)=\prod_{i = 1}^{r}F_i(X)$, the polynomial $F(X)$ defines the field $\mathbb{K} = \mathbb{Q}(\theta) = \mathbb{Q}[X]/(F)$ where $\theta$ is a fixed root in the algebraic closure of the base field.

Questions:

Should it not be stated that $\mathbb{Q}(\theta) \cong \mathbb{Q}[X]/(F)$ rather than $\mathbb{Q}(\theta) = \mathbb{Q}[X]/(F)$ ?
I assume that $\theta$ is just a root of $F(X)$ in the extension $\mathbb{Q}/\mathbb{F}_2$?
In the expression $\mathbb{Q}[X]/(F)$, is what is being referred to the

quotient of $\mathbb{Q}[X]$ by the ideal generated by $F(X)$, i.e. $\mathbb{Q}[X]/(F(X))$?

Yes, technically this is an isomorphism, so $\cong$ should be used. The isomorphism is question identifies $\theta$ with $X$.
Not quite (for the original question or your restatement).  The notation $\mathbb{Q}(\theta)$ means adjoining $\theta$, a root of $F(X)$ in the algebraic closure of $\mathbb{Q}$ (namely, $\mathbb{C}$), to $\mathbb{Q}$.  The finite field $\mathbb{F}_2$ has nothing to do with it.  (And I think $\mathbb{Q}/\mathbb{F}_2$ is meaningless, since there is no field embedding of $\mathbb{F}_2$ into $\mathbb{Q}$.)
Yes.  Such a structure is more commonly known as a number field (i.e., a finite dimensional field extension of the rationals).


ElGamal: Generation of "g" value? I haven't been able to find a clear explanation on this (and I'm probably just confused in general).  I have the following parameters of ElGamal signatures:

$p$ = safe prime
$q = (p-1)/2$
$g$ = an element of $F_p$ with order $q$.
$r$ = random $1 < r < q $
$s$ = private key
$Y$ = public key, $Y = g^s$

My question is, is there an easy way to generate a $g$ value, or should I just generate a random value, then check that it is in the group?

If $q$ is prime (which is a common additional constraint) then the possible orders for a random $F_p$ between $2$ and $p-2$ inclusive is either $q$ or $2q$ so you can avoid having to check the order by picking one at random, squaring it and using the result.


MD5 Collision Attack Explained In one of my assignments, I came across this line

  Due to MD5’s length-extension behavior, we can append any suffix to both messages and know that the longer messages will also collide. This lets us construct files that differ only in a binary “blob” in the middle and have the same MD5 hash, i.e. prefix || blobA || suffix and prefix || blobB || suffix.

I am not quite understanding what "binary blob" means in this context. Does the blob have to be something in particular to ensure that the two files will continue to have MD5 collision?

Here, I think BLOB is meant to be interpreted as binary large object, and it refers to the 128 bytes of data that differ between the two files but which produce the same MD5 hash output.  Those are the two parts of the files that differ between the two programs but which yield the same MD5 partial result.

So look at it this way.  You start out hashing each file at the beginning and compute the interim hash value through the prefix.  Obviously both hashes will, at this point, be the same because the prefixes in both files are the same.

Now a new interim hash result is computed using the above mentioned result so far and the new chunk of data, the portion they refer to as BlobA and BlobB.  These data chunks differ but were constructed to yield the same MD5 output.  So after these middle sections are hashed, the partial hash for each file is still identical.

The hash process then continues on each file through the suffix, which like the prefix, is identical for both files.  So the output (final) MD5 hash will be the same.  At this point, my understanding of the passage you quoted is that if you have 2 files that hash to the same MD5 value, you can now append anything you like to the end of those files (as long as it is the same data for both files) and the MD5 hash will change for both files in exactly the same way, so they will continue to have identical hashes one to the other.


Concept Question for Secure Computation I think this should be a simple question and I might be missing something fairly fundamental, but I haven't been able to find the answer.

Basically, suppose there are parties $A$ and $B$. Party $A$ gets a secret input $s$. Party $B$ has no input. They wish to securely compute the function $f(s) = (\bot, \bot)$ so nobody learns any information.

Suppose the protocol they use goes as follows: $A$ sends $s$ to $B$ in the clear. Clearly, this 'should not' be considered secure, as $B$ wasn't supposed to learn anything but she learned $s$. However, by the simulator-based definition of security, I don't understand why we can't efficiently simulate $B$'s view.

I.e. if we generate a simulated transcript just by picking a random $s$ and sending it to $B$, how can he distinguish between that and a real transcript?

As in the linked question, what you are missing is that the simulated view for a given input pair must be indistinguishable from the simulated view for the same input pair.

So if $A$'s input $s$ is $0$, then the real view of $B$ will be $0$ with probability $1$. On the other hand, if your simulator just chooses a uniform bit, the simulated view of $B$ will be $0$ with probability $1/2$. That's distinguishable, so your simulator doesn't work. (Same if $s=1$ of course.)

A slightly more involved argument shows that any simulator will have the same issue, so there is no suitable simulator, and the protocol is not secure.


How secure is file header encryption for large files? I'm having trouble location information about whether or not encrypting a file's header is good enough. The files in question are media files that range in size from 500mb to 4GB.

If I had no performance or time constraints, I would simply encrypt the entirety with AES256. However, with my current implementation (in C#), it takes about 3 minutes to decrypt a 2GB file. This is about 2m45s beyond my time limits.

How vulnerable is that file's contents without the file header?

Apologies if this question is silly, this is my first foray into file security.

It depends on the format. The size suggests it is a video. However, video formats seems to be designed to be seekable. That means, the attacker seems to be able to:

Create some header (guessing the resolution and some other information)
If the beginning was damaged, play and seek in the file.


Choosing a Random Number Generator algorithm to encrypt a message What are the best cryptographically secure pseudo-random number generator algorithms, and what are their strengths/weaknesses?  I can't seem to come up with a list of them (or maybe I do, but they have such weird names that I don't recognize them).

I'm trying to write a simple program that takes a message and a key and encrypts or decrypts the message by using the key as the seed to a psuedo-random number generator that then generates the key to be used to encrypt/decrypt the message.  However, I keep getting frustrated at how hard it is to find a good, safe random function no matter what language I try, so I decided to try to make one myself.

takes a message and a key and encrypts or decrypts the message by using the key as the seed to a psuedo-random number generator that then generates the key to be used to encrypt/decrypt the message.

This sounds like a stream cipher. You should probably stop looking for a pseudorandom generator and instead look for a stream cipher. But “stream cipher” is both overspecific — why a stream cipher rather than another type of cipher? — and not enough — a stream cipher only encrypts, it doesn't guarantee authenticity. Without authenticity, many systems are vulnerable to oracle attacks which can allow an attacker to recover plaintext by submitting modifications of the ciphertext. So in fact you probably need an authenticated encryption (AEAD) algorithm. If in doubt, use crypto_box from NaCl or libsodium, but pretty much any AEAD interface in any reasonably modern cryptography library would be fine.

  I keep getting frustrated at how hard it is to find a good, safe random function no matter what language I try, so I decided to try to make one myself.

If you want to implement a random generator as a learning exercise, go ahead, it's a good learning exercise. But keep in mind that this is only a learning exercise. A well-established crypto library will almost surely do it better than you. Does your implementation properly wipe memory after use? Does your implementation properly report any failure of the entropy source? Might your implementation reveal confidential data via side channels such as timing and memory access patterns? Decried as it is, the authors of OpenSSL have thought about such things. If you haven't then they've done a better job than you.

For the sake of people who came here because the question's title is about PRNG choice: If you really need a pseudorandom number generator, it may help to know that another common name is “deterministic random bit generator” (DRBG). Any of the three algorithms from NIST SP 800-90A (Hash_DRBG, HMAC_DRBG, CTR_DRBG) is a good choice. But once again, note a PRNG has an interface which includes periodic reseeding; you can't easily use it directly to build a stream cipher. If what you want is to encrypt a message then what you want is not a PRNG. A PRNG is what you'd use to generate the key and the IV/nonce. And keep in mind that if you think you need to implement a PRNG, you're probably wrong. Use your operating system and your cryptographic library's random generator interface — as I explain above, they've done a better job than you're likely to.


How is a per round key generated in DES algorithm? I am reading over a slide that I found online regarding the DES algorithm for encryption and I am a little confused about the per round key generation. From the slide below, I understand that each per round key is obtained by shifting left either 1 or 2 bits depending on the round. The thing I do not understand is the permutations for Left half C_i and right half D_i

In the slide, it says that the left half C_i is 14 17 11 24 1 5 3 28 15 6 21 19 23 19 12 4 26 8 16 7 27 20 13 2. Are the numbers in this example random? A textbook I am reading also uses the same numbers for round C_i and I cannot see the connection here. C_0 does not contain 14, so I am not really sure how left shifting bits causes the 14 from D to go to C. Am I misunderstanding the problem here?

Numbers $\{14,17,11,24,1,5,3,\dots\}$ come from permuted choice PC-2. So let me explain 16 round DES key scheduling:

DES input key size is 64 bit which contains 56 bit key and 8 parity bits. Parity bits are 8th bit of every 8 bits (on byte). So they are all multiple of eight: $\{8, 16, 24, 32, 40, 48, 56, 64\}$.
Permuted choice PC-1 is used to remove these bits from the 64 bit input key. So PC-1 gives 56 bits as output.

In round $i\ (1 \le i \le 16)$, there is a 56 bit input, $C_{i-1}$ as left half and $D_{i-1}$ as right half (each 28 bits). These two halves are rotated left (for decryption, right rotate is used). For encryption, rotate amount in rounds $\{1, 2, 9, 16\}$ is one and in other rounds it's two. For decryption, one bit right rotation in rounds $\{2,9,16\}$ and two bit right rotation in all other rounds. As inputs of rotation are $C_i$ and $D_i$, outputs of rotation are $C_{i+1}$ and $D_{i+1}$ which are passed to the next round ($i+1$) as input.

After all, in round $i$ there is a 48 bit output, named $K_i$. This sub key is generated from permuted choice PC-2, which takes $C_i$ and $D_i$ as a 56 bit input and outputs the sub key.

Now i think now you understood where those numbers come from. The overall process is illustrated in the picture below (Encryption):

Image Source: Understanding Cryptography by Christof Paar and Jan Pelzl, Chapter 3


Choosing which is public vs private key When I calculate two RSA keys, what if anything, would make any difference which I call the public vs which I call the private key?

In any RSA-type cryptosystem, a public key necessarily has a modulus $n$, and sometimes has an exponent $e$ if it's not prescribed by the cryptosystem.  Sensible cryptosystems like RSA-KEM can prescribe $e = 3$, but some defective standards, based on mistakes like RSAES-PKCS1-v1_5, may require $e$ to be $e = 65537$ or larger and may allow $e$ to vary.

A private key can come in any of several forms:

the factors $p$ and $q$ of $n = pq$
a private exponent $d$, which solves $e \cdot d \equiv 1 \pmod{\lambda(n)}$
Chinese remainder theorem exponents $d_p \equiv d \pmod{p - 1}$ and $d_q \equiv d \pmod{q - 1})$

Any of these forms of the private key is equivalent, given knowledge of $n$: from $p$ and $q$ you can compute $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$ and solve $e d \equiv 1 \pmod{\lambda(n)}$ with the extended Euclidean algorithm; from $d$ you can recover a multiple $e \cdot d - 1$ of $\lambda(n)$ and without much additional difficulty proceed to factor $n$; etc.  Often, as in, e.g., OpenSSL, many redundant parts of the private key are stored together to speed up the computation.

The main question, then, is: Are the public exponent $e$ and the private exponent $d$ interchangeable?  And the answer is: No.

In Rivest, Shamir, and Adleman's seminal paper, the proposed method was to choose $d$ at random to be coprime with $\phi(n) = (p - 1)(q - 1)$ and then to derive $e$ from $d$ by solving $ed \equiv 1 \pmod{\phi(n)}$.  One could do it the other way around: choose $e$ at random to be coprime with $\phi(n)$, and then to derive $d$ from $e$ by solving $ed \equiv 1 \pmod{\phi(n)}$.  So, if you were stuck in 1978, it might look like the roles of the two exponents are interchangeable—but if you were stuck in 1978, your encryption scheme would also be trivially breakable,* so maybe you don't want to stay in 1978.

The main cost for a user of RSA is computing modular exponentiation, which for exponent $x$ costs $\lfloor\log_2 x\rfloor$ squarings and $H(x) - 1$ multiplications, where $H$ is Hamming weight.  The most efficient exponent is 3—but you can only do this for the public exponent!  If you always picked the private exponent $d = 3$, you would still have to publish $e$ in order for anyone to encrypt messages—but if you did that, then armed with knowledge of $e$ and $d$ I could find $\lambda(n)$ and factor $n$ and break the whole cryptosystem!

‘OK, fine,’ you say, ‘so $d = 3$ is no good, but what if I just picked $d$ to be small to speed up decryption?’  As it happens, if $d$ is merely smaller than about $\sqrt[4] n$, I can use Wiener's attack or a variant thereof to recover it!  It is therefore crucial that the private exponent $d$ be near uniformly distributed in the whole possible space, which is effectively the case even if you choose the public exponent $e$ to always be something small like 3 or 65537.

Thus while it is perfectly safe in sensible RSA-type cryptosystems to always use $e = 3$, it is dangerous to choose even moderately small $d$; the exponents are very much not interchangeable.

P.S.  You may be tempted, by the seductive symmetry of the equations $c = m^e \bmod n$ and $m = c^d \bmod n$, to treat encryption and signature as interchangeable too.  Don't do it!  It's a trap!  If you try to shoehorn a message into this shape, you'll likely end up shooting yourself in the foot; there's much more to encryption and much more to signature, and beyond the use of exponentiation they bear very little resemblance—and if you naively try to combine the two with the same keys you will probably shoot yourself in the other foot too.  At that point, you'd better hope you're an octopus.

* They recommend what is effectively RSA-ECB for encryption, and a trivially forgeable hashless signature scheme.  The first secure signature scheme by modern standards—assuming suitably scaled parameters—wasn't published until a year later by Rabin in 1979, using the qualitatively different exponent $e = 2$, and the first secure encryption scheme by modern standards wasn't published until some time after that.


Can Secp 256 K1 curves "map" to a value on FIPS 186-3 or P-256? I'm looking at Secp 256K1 vs UProve's FIPS 186-3 or P-256 implementation.  Is there any relationship between the curves such that I can consistently "map" or "project" values from one curve to another?

Is this a good idea?  (What faults could crop up when doing so?)

My goal is to allow for two independent crypto systems based on ECDSA or subgroups to share the same keys via a conversion of some type

If what you want is some kind of algorithm that takes a public key $Q = aP$ on one curve and converts it into $Q' = a P'$ on the other curve, then the answer is almost certainly no. There are no "interesting" maps between curves with different group structures.

If you just want to use the same secret key for both curves, so $Q = aP$ on one curve and $Q' = aP'$ on another, $P,P',Q,Q'$ public, that isn't obviously a bad idea. It seems plausible that the obvious DDH-like problem is hard. However, doing this does introduce a bunch of technical problems, e.g. how do you prove that your public keys correspond to the "same" private key (which can be solved, but is tricky when the group orders are different).


How does the small n attack work? I'm studying the Lamport's Hash one-time password scheme.

This is the scheme:

Alice wants to authenticate herself to Bob from a workstation that knows nothing about her. Alice only knows her password.
Bob knows

Alice types her name and her password into her Workstation
The Workstation sends "Alice" to Bob
Bob sends n to the Workstation
The workstation computes x = hash^(n-1) (pwd) and sends it to Bob
Bob hashes it once and compares it with database. If it matches, Bob considers the response valid, replaces the stored quantity with the received quantity, and replace n by n-1.

This scheme has a security weakness called small n attack.

This is the explanation given in "Network Security: Private Communications in a Public World":

  Suppose an intruder, Trudy, were to impersonate Bob's network address and wait for Alice to attempt to log in. When Alice attempts to log into Bob, Trudy sends back a small value for n, say 50. When Alice responds with hash^(50) (pwd), Trudy will have enough information to impersonate Alice for some time, assuming that the actual n at Bob is greater than 50.

I don't understand this. I would need a different explanation.

The reason Lamport's scheme is secure against a passive attacker is that even if they see $H^{n-1}(p)$ for a given $n$, the server would require the preimage of that hash, $H^{n-2}(p)$ on the next login.

The active attack, in comparison, allows Trudy to find an earlier iteration than the server is expecting. That allows calculating several login hashes by iteratively hashing the captured one. It is even possible to do it transparently to the user, by replacing the hash they give by the one the server is expecting.

Alice types the name and password.
Workstation sends "Alice".
Bob sends $n$. Trudy intercepts it and replaces it by for example $n' = n-10$.
Workstation computes $h = H^{n'-1}(p) = H^{n-11}(p)$. Trudy intercepts and replaces by $H^{n-1}(p) = H^{10}(h)$.
Bob hashes once, sees a match.

Now Trudy can calculate the next ten hashes that Bob expects, like the next one: $H^{n-2}(p) = H^{9}(h)$. This allows several logins as Alice.


Collision resistant hash function implies one-way function I'm struggling to give a formal proof that $CRH \implies OWF$ using the definition below.

Intuitively, I see why a $CRH$ would be "hard to predict" and might be used as a $PRF$, but I'm unable to give a formal proof.

$\mathcal{H} = \{\mathcal{H}_n = \{h:\{0,1\}^* \rightarrow \{0,1\}^n \}\}$ is a $CRH$ if it can be efficiently sampled and
$$\forall_{A;PPT} \exists_N \forall_{n>N} \Pr_{h \rightarrow H_n} [A(1^n, h) = (x, x') \land x \neq x' \land h(x) = h(x')] = neg(n)$$

Proving the existence of $PRG$ or $PRF$s would suffice.

Related but answered question here.

Collision-resistance implies one-wayness.
Proof by reduction: if you have an algorithm $A$ which is able to invert $H: b^* \rightarrow b^n$,
we can build an algorithm $B$ which is able to find a collision (with almost the same time and probability).
Here $b$ means $\{0,1\}$.

Let's consider only input strings of some length $l\ge n$.
Notice that $H$ splits the set $b^l$ into the following $2^n$classes:
$$
\{C_h = \{x: x\in b^l \land H(x)=h \}\}_{h\in b^n}.
$$
On expectation (if function behaves randomly), each class consists of $k = 2^{l-n}$ elements.
But for our concrete function some of the classes could be empty, while some of them have more elements than others.

Algorithm $B$ behaves as follows:

Picks random $x\in b^l$ and evaluates $h = H(x)$.
Runs $A$ on input $h$: $x' = A(h)$.
If $x \neq x'$, returns a collision $(x, x')$. Goes to step 1 otherwise.

Easy to see that probability of success on step 3 is $1 - \frac{1}{k}$ (which is quite a lot, and you can increase $k$ or just make several rounds of algorithm to achieve any probability you want).
The explanation is: when you're picking $x$ on first step, you're picking one of ${C_h}$ with probability proportional to a number of elements in the class: $Pr[C_h] = \frac{|C_h|}{2^l}$.
Then, on the step 3, probability of failure, i.e. $x = x'$, is $1/|C_h|$,
taking into account uniformly random choosing of $x$ and the fact that $A$ "doesn't know" which element $x$ from the class $C_h$ you selected (you've given him just $h$).
So, the common probability of failure is calculated as:
$$
Pr[\texttt{"failure"}] =
\sum_{h\in b^n} {Pr[C_h] \cdot Pr[\texttt{"failure on C_h}"]} =
\sum_{h\in b^n} {\frac{|C_h|}{2^l} \cdot \frac{1}{|C_h|}} = 2^n\cdot \frac{1}{2^l}.
$$

Remark that we do not require any random properties of $A$ nor $H$.
We achieve this probability estimate just using randomness of $B$ (uniformly random choosing of $x$ on step 1).


(AES in mind) How can we show two irreducible polynomials have a bit-wise linear isomorphism This refers to answer 2 on a similar question:Design properties of the Rijndael finite field

I am unsure what many of the terms mean in this answer. I think a bit-wise linear isomorphism of irreducible polynomial A refers to: $$A(x) = x^8+x^4+x^3+x+1=100011011$$ or $11B$ in hex. And I assume B refers to another irreducible polynomial over $GF(2^8)$ (btw Is there a list of these? I cannot find them). If I am right, I still cannot fully understand what is meant by:$$L(X+_AY)=L(X)+_BL(Y)$$ or $$L(X \times_AY)=L(X)\times _BL(Y)$$Specifically, I am not sure what $X$ and $Y$ are (but I think they are other polynomials) or what $+_A$, $+_B$, $\times_A$, $\times_B$ mean. A full numerical example would be very helpful, even if only one of the two equations above.

To answer this question, we'll first want to step back and discuss what a finite field is, and what a representation is.

A finite field is a group of finite size (always $p^k$, for some prime $p$ and integer $k$, in this case, $2^8$), along with addition and multiplication operators, where certain identities are true (e.g. $a \times (b + c) = a \times b + a \times c$), see this link for the list.

It turns out that, given a specific size $p^k$, the field is essentially unique (in the sense that, if we have two different sets of the same size where they both preserve the identities, they will always be a mapping between the two sets which preserve both the addition and multiplication operations, hence those two sets are essentially the same.

This is nice, however we need a way to talk about these elements; what we do is assign the element names; for $GF(2^8)$, we have precisely 256 elements, and so we typically give each element a unique 8 bit name.  Such a way of assigning names is known as the 'representation'.

For $GF(2^8)$, there are a number of reasonable ways to assign these names, one such way is to select an irreducible polynomial, and compute the multiplication modulo that polynomial.  That is the approach that AES takes, with the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$.  Let us call this specific representation (which is a way of assigning names to field members) $A$.

However, that isn't the only way of assigning names; we could consider a different irreducible polynomial, say, $x^8 + x^4 + x^3 + x^2 + 1$.  That gives a different way of assigning names to field elements, that is, a different representation, we may call this representation $B$.

Now, we define $L$ to be the function that takes a field element (using the $A$ naming convention), and return the name of that same field element (using the $B$ naming convention).  It turns out $L$ isn't unique; we'll ignore that for now.  It turns out that $L$ is an isomorphism, as the field it maps from (the $A$ representation) and the field it maps to (the $B$ representation) are the same (because they're both different ways of given labels to the same underlying field).

It turns out that, if we just look at $L$ as a mapping between 8 bits to 8 bits, it is bit-wise linear.

In the $A, B$ representations I just gave, one such mapping is:

$$L(01) = 01$$
$$L(02) = 03$$
$$L(04) = 05$$
$$L(08) = 0F$$
$$L(10) = 11$$
$$L(20) = 33$$
$$L(40) = 55$$
$$L(80) = FF$$

Because $L$ is linear, it is easy to deduce $L(X)$ for any other $X$ not listed.

And, what $+_A$ means is the addition operation in the $A$ representation; that is, $X +_A Y$ takes the two field elements $X, Y$ (named using the $A$ convention), and evaluates to the field addition of those elements (also expressed in the $A$ naming convention.  Hence, when we say:

$$L(X+_AY)=L(X)+_BL(Y)$$

$X, Y$ are both arbitrary field elements (in the $A$ naming convention), and what we're saying is that the $L$ mapping preserves addition; that is, if we add two arbitrary elements $X, Y$ (in the $A$ representation) and then map the sum, we always get the exact same value as we would have if we first mapped $X$ and $Y$ into the $B$ representation, and then added them (in the $B$ representation).

We call out $+_A$ and $+_B$ because they aren't necessarily the same operation (actually, in this case they are, but not in general); $+_A$ assumes the inputs are in the $A$ representation, and $+_B$ assumes they are in the $B$ representation.

You asked for a numeric example, here's a simple one (using the $\times$ operator; it turns out that the addition operation isn't that interesting).

If we pick $X = 03$ and $Y = 05$, we have (on the left side):

$L(03 \times_A 05) = L(0F) = L(01) \oplus L(02) \oplus L(04) \oplus L(08) = 08$

(Note: we have $L(0F) = L(01) \oplus L(02) \oplus L(04) \oplus L(08)$ because of the bitwise linearity of $L$)

On the right side, we have:

$L(03) \times_B L(05) = (L(01) \oplus L(02)) \times_B (L(01) \oplus L(04)) = 02 \times_B 04 = 08$

That is, both sides come up with the same value.  This will always be true no matter what values we picked for $X, Y$


Is this permutation secure? Let vector ${\bf d} \in \{ \pm 1 \}^n$ be the message we want to send. In my system, ${\bf d}$ is multiplied by an $n \times n$ Fourier matrix ${\bf F}$, as follows
$$ {\bf x} = {\bf F} {\bf d}  $$
where
$$ {\bf F} =
 \begin{pmatrix}
  1 & 1 & 1 & \cdots & 1 \\
  1 & e^{jw} & e^{j2w}&\cdots & e^{j(n-1)w} \\
  \vdots  & \vdots  & \vdots & \ddots & \vdots \\
  1 & e^{j(n-1)w} &e^{j2(n-1)w}& \cdots & e^{j(n-1)(n-1)w}
 \end{pmatrix}$$
We perform secret permutation $P$ for ${\bf x}$ provided that only the legitimate parties know the permutation and $P$ changes for every transmission.

Does multiplying by ${\bf F}$ help to diffuse?

Is this actually breakable?

If so, what kind of cryptanalysis can be used?

This is problematic as stated. You need to specify a probability distribution for that complex matrix, but the complex field is infinite. This then implies that you need to also carefully define some detection/quantization mechanism.
So, why complex numbers?