bcrypt - collision-resistance against chosen salt and work factor?

The answer to the original question would have been: Yes, it would be impossibly difficult to exhibit workfactor, salt, password0, password1 such that bcrypt(workfactor, salt, password0) = bcrypt(workfactor, salt, password1); but even if that was feasible, it would not matter much, because in normal use at least one of the password is unknown to an adversary matter only in certain protocols where it could allow ruling out two passwords in one try.

As to the question as now worded: No, it would not be too difficult to exhibit workfactor, salt, password0, password1, input such that bcrypt(workfactor, salt, password0, input) = bcrypt(workfactor, salt, password1, input); but that's only because input is left malleable, rather than set to "OrpheanBeholderScryDoubt"! In any reasonable use of bcrypt, input is built as three distinct 64-bit constants (or at least values not malleable to the degree in the question).

The original reference on bcrypt gives it as:

bcrypt(cost, salt, pwd)
    state := EksBlowshSetup(cost, salt, key)
    ctext := "OrpheanBeholderScryDoubt"
    repeat (64)
        ctext := EncryptECB (state, ctext)
    return Concatenate(cost, salt, ctext)

with text around suggesting that the pwd input maps to key (how exactly is unspecified), and that the 24-characters "OrpheanBeholderScryDoubt" maps to three 64-bit blocks constituting ctext. Predictably, implementations have varied on the mapping from pwd to key, including in ways introducing a serious weakness. Perhaps the initial value of ctext has varied also. Further, how Concatenate formats the output has varied (including in an effort to encode the variations used in the rest).

If Blowfish is a good cipher, 64 iterations of Blowfish is also a good cipher (better by some metrics, maybe slightly worse by the cycle structure), and thus for any three distinct constant 64-bit plaintexts, the ciphertexts per that Blowfish64 should be three values indistinguishable from random, except for being distinct. By design of Blowfish and bcrypt, finding a collision with random salt and key should be expected to require over $2^{96}$ evaluations of EksBlowshSetup, thus $2^{97+\mathtt{cost}}$ ExpandKey operations, which is beyond feasible.

But for whatever reason, bcrypt's wikipedia entry as I read it now states that bcrypt computes a hash from a given input as follows:

bcrypt(cost, salt, key, input)
    state := EksBlowfishSetup(cost, salt, key)
    ctext := input
    repeat (64)
        ctext := EncryptECB(state, ctext) //encrypt using standard Blowfish in ECB mode
    return Concatenate(cost, salt, ctext)

Notice the fourth parameter input and the uncertainty on if the password is fed to key (the original intend) or input. In the following I assume this 4-arguments definition, with password in the question mapped to key.

The crux is that the current statement of the question (not the originally intended and likely usual blowfish setup) leaves the choice of input, including as a 64-bit value repeated three times, which makes collision search feasible:

set cost to the lowest possible value;
set salt to some short admissible constant;
for j from $0$ to $2^{20}-1$, compute and store state[j] := EksBlowfishSetup(cost, salt, key) where key corresponds to a password obtained as j translated to an acceptable password as 5 hexadecimal digits and an appropriate suffix; that will require a reasonable 4GiB of RAM, and bearable CPU time.
repeat for i increasing, starting from $0$:

for j from 0 to $2^{20}-1$:

set ctext to i converted to a 64-bit bitstring;
repeat 64 times:

set ctext := EncryptECB(state[j], ctext); the encryption is over a single block;

if that ctext was previously obtained for the same i and earlier j, then derive password0 from that earlier j, derive password1 from the current j, and set input as the 192-bit bitstring formed by three times i converted to a 64-bit bitstring; we have found a collision!
else, remember ctext and the corresponding j in some easily searched table (which will require only a small fraction of the RAM used previously);

having had no luck with this i, empty the table, proceed to next i.

For each i tested, we are looking for collision among $2^{20}$ random-like 64-bit values, and that has odds about $2^{20+20-1-64}=2^{-25}$. Thus we are expected to succeed after about $2^{25}$ loops on i, that is $2^{45}$ loops on i and j, that is $2^{51}$ encryptions, which is considerable but feasible. Twice more memory makes a machine nearly twice as efficient, and to some degree it is possible to substitute hard disk or SSD for the part of the RAM used to store state[j], with some minor complications. Also, this can be distributed trivially, each machine using as much memory as it has available.

Update: I have checked two implementations of bcrypt.

jBCrypt is per the original bcrypt definition, but has two issues: because it is written in Java (which is not fully compiled at least in the most common practice, and lacks built-in idioms for unsigned 8-bit variables), speed is likely significantly worst than something native, which in the particular context means proportionally less secure; also, in that version at least, cost of 31 is accepted but degenerates to less security than the minimum cost of 4, because 1<<31 is negative in Java. Oh wait, I'm not the first to step on that, here's a corrected version.

In PHP, the accepted practice is delegating bcrypt password hashing to a native implementation of crypt (see this Bcrypt.php or that highly-praised answer), which is a sound way to solve the speed issue. I was told crypt goes to crypt.c then crypt_blowfish.c. I now have located "OrpheanBeholderScryDoubt", and the code referencing it is per the original bcrypt definition. Speed is likely quite decent. I like the idea of checking the code at runtime with a quick Known Answer Test, which also stands a good chance of overwriting sensitive values; and some modest but likely useful attempts to reduce other sources of leakage.


What is SHA-256 in Conjunctive Normal Form?

There is none. Conjunctive normal form is for Boolean formulas, which have a single truth value. SHA-256 is not a Boolean formula (SHA-256(x) is not "true" or "false.") Furthermore, CNF is only applicable if you have a fixed number of variables; this is not true for SHA-256, which has variable-length input. At best you could have 256 different formulas, each for one bit of the output, and have $2^{64}+63$ different variables in each formula.

You've probably confused decision problems with function problems. Any algorithm that returns "true" or "false" can be represented, ultimately, as a gigantic Boolean formula. Anything not just returning "true" or "false" cannot, as a Boolean formula returns only "true" or "false." While there is a $2^{64}+63+256$-variable formula that evaluates to "is $x_1\ldots x_{256}$ the SHA-256 hash of the $x_{257}\ldots x_{320}$-bit number stored in $x_{321}\ldots x_{\text{last}}$," the formula is really just one of those things that exists in theory and not in practice.


Subexponential algorithms for DLP in $\mathbb{Z}_s \times \mathbb{Z}_t$

First of all, DLP is only defined for cyclic groups. The $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$ you are talking about is not cyclic, since (say) $s$ divides $t$. But you can define a "generalized" DLP by considering the cyclic subgroup generated by an element $g$.

Next, DLP in any subgroup of $\mathbb{Z}_t^+$ is trivial. Figuring out why is a nice exercise. It follows that any "generalized" DLP in $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$ will be trivial. So there's no need to consider subexponential algorithms.

(If we were talking about $\mathbb{Z}_t^*$, not $\mathbb{Z}_t^+$, subexponential algorithms would be interesting and important.)

An elliptic curve has a group structure that is isomorphic to $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$ (for some $s$ and $t$), which means that abstractly, the two mathematical objects have the same structure. But they have different representations.

Representation is extremely important for DLP. As far as anyone knows, "generalized" DLP is hard when the representation is a suitably chosen elliptic curve, but it is extremely easy when the representation is $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$. Abstractly, they're the same, but in practice, they are very different with respect to what we can compute.  For instance, recovering the isomorphism that connects the elliptic curve to $\mathbb{Z}_s^+ \times \mathbb{Z}_t^+$ (that maps from one representation to the other) is computationally hard: it is as hard as the discrete log problem on that elliptic curve.

PS. The above contains many mathematical subtleties, so please consider this as an invitation to study mathematics, and not as an answer to your questions.


Cryptographic sealing is the application of asymmetric cryptography to encrypt a session key so that it cannot be used-- until it is decided to remove the seal and use the key.  It is a protection mechanism. See this description from Oracle:

  Sealing the symmetric key involves creating a sealed object that uses
  an asymmetric cipher to seal (encrypt) the session key. The RSA
  asymmetric algorithm cannot be used because it has the size
  restrictions described in the next section, and the sealing process
  makes the session key too large to use with the RSA algorithm.

The idea of cryptographic sealing has been around for a long time. A paper from 1981, Cryptographic Sealing for Information Secrecy and Authentication., by David K. Gifford, goes into interesting detail about it:

  A new protection mechanism is described that provides general
  primitives for protection and authentication. The mechanism is based
  on the idea of sealing an object with a key. Sealed objects are
  self-authenticating, and in the absence of an appropriate set of keys,
  only provide information about the size of their contents. New keys
  can be freely created at any time, and keys can also be derived from
  existing keys with operators that include Key-And and Key-Or. This
  flexibility allows the protection mechanism to implement common
  protection mechanisms such as capabilities, access control lists, and
  information flow control. The mechanism is enforced with a synthesis
  of conventional cryptography, public-key cryptography, and a threshold
  scheme.

So, the purpose of sealing is very different from that of signing.  Sealing prevents use of a session key. I have been unable to find any RFCs that deal with sealing.  Nor have I found any applicable OIDs. The timestamping involved in sealing, as far as the encryption process goes, will be the same as normal, as far as I can see. RFC 5652 (Cryptographic Message Syntax) does not specifically mention cryptographic sealing.


Does security against a CCA1 attacker imply security against a CPA attacker?

Simply consider the two games and a reduction between them. From the contapositive you need to show that every attacker against CPA yields a CCA1 one. Now, from every CPA adversary you can always construct an adversary that breaks CCA1 but simply makes/requires no decryption query (clearly the same holds for CCA2).


Perceptual encryption is a term used to describe various applications of encryption methods intended for audio, speech, image and video data.

The basic idea is that one performs encryption for multimedia content in a way that only a certain amount of "perceptual information" is touched by the encryption. It may be considered as intentionally degrading the quality of the multimedia content by means of encryption, whereas the part of the data that remains untouched can be processed by the respective decoder without requiring access to the encryption key. However, the full "perceptual information", i.e., the full quality multimedia data, can only be recovered when given access to the the encryption key.

For instance, one may use perceptual encryption to downgrade the quality for a free online preview of some movie and only if one pays for the content one obtains access to the encryption key and thus to the full quality content.

There are various freely available
articles describing different techniques for this type of encryption (just do a Google or Google Scholar search) and also some parts of books (you can find via Google Books), e.g.:

“Recent Advances in Multimedia Signal Processing and Communications”
 by Mislav Grgic, Kresimir Delac, Mohammed Ghanbari
or
“Perceptual Digital Imaging: Methods and Applications”
by Rastislav Lukac

and just search for "perceptual encryption". I am not sure if there is something like a single definition because there are various techniques for perceptual encryption, but you should find classifications in the linked books.


Relationship between CCA/CPA-security and PRFs

IND-CPA/CCA encryption schemes do imply PRFs: Does IND-CPA imply PRF?

But the above result does not mean Enc or Dec must be a PRF. From its definition, a PRF is indistinguishable from a random function for polynomial-time attackers. We can easily make Enc look non-random but still secure. For instance, you can append some 0 bits to the end of the ciphertexts. As for Dec, its domain is not easy to get. If the encryption scheme satisfies the integrity of ciphertext (INT-CTXT), then you cannot even find valid ciphertexts and almost always get nothing from Dec.

Btw, as you noticed, PRFs are deterministic, so you should consider the "random tape" inside Enc when comparing them.


How are Zero-Knowledge Proof protocols designed?

Any statement that is checkable in P (i.e., any NP statement) can be proved in zero knowledge. This can be shown by giving a ZK proof for any NP-complete problem --- historically, 3-colorability of graphs or Hamiltonian cycle. But giving a reduction to these graph problems might seem artificial. Perhaps a better approach is to use an NP-complete problem like circuit satisfiability, which is what is suggested in:

  Marek Jawurek, Florian Kerschbaum, Claudio Orlandi: Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently. ACM CCS 2013.

I don't know if you'll necessarily consider this more "direct", since it is only direct if you already know about oblivious transfer and garbled circuits.

Even the toy examples from wikipedia have aspects that are fairly standard to many ZK proofs: in particular, pre-commitment to some answers, a randomized challenge, and amplification.

Another good example of a not-so-cryptographic ZK proof is the graph non-isomorphism proof.


Can we use numbers as a pad in the Vernam cipher - why or why not?

Yes, you can use numbers as a one-time-pad key. In fact, the CIA used to do it all the time, as did many.

When you use numbers the plaintext becomes letters by referring to a conversion table such as the venerable "Tapir" used by the STASI.

Here the addition will be modulo 10.  Vernam Cipher, or the one-time pad (OTP), can also be done modulo 2:

SENDING
-------
message: 0 0 1 0 1 1 0 1 0 1 1 1 ...
pad:     1 0 0 1 1 1 0 0 1 0 1 1 ...
XOR      ---------------------------
cipher:  1 0 1 1 0 0 0 1 1 1 0 0 ...

RECEIVING
---------
cipher:  1 0 1 1 0 0 0 1 1 1 0 0 ...
pad:     1 0 0 1 1 1 0 0 1 0 1 1 ...
XOR      ---------------------------
message: 0 0 1 0 1 1 0 1 0 1 1 1 ...

Or, it can be done modulo 26 (with English letters). For example:

Plaintext:  DARLING THE NIST CURVES HAVE BEEN COMPROMISED AND MY RANDOM NUMBER GENERATOR HAS A KLEPTOGRAPHIC BACKDOOR I FEEL SAD
Key:        NLQVT ZBOFW MFAVS RJMDE PGNEX GGQMU VOFNE PBWXT ICDWK VEEYL EGVWS ZRDKD IDJGO HWKFF MBEGA KEUNQ BEYDO
---------------------------------------------------------------------------------------------------------------------------------
Ciphertext: QLHGB MHHMA ZNSOU LAHHW WGIIY KKDOI HDWBQ XTAAT VFPUB VRHMX RAHXW QXHXH ZDCUF OWCFP XFTZO QVUCX JGZDQ MUYBN VQUZE RBR

The reason you could not insert numbers into the online encrypt/decrypt tool you found is because that tool was only designed for the modulo 26 addition of letters.

Here is one example of what a CIA one-time-pad key looked like during the Cold War:


Zero padded signatures in the Bleichenbacher attack

Why does RSA accept a 0x00 padded cube root as encoded signature?

It is not correct to assume that a valid RSA signature always starts with a byte containing a few bits set to one.

An RSA signature is calculated by padding the hash value. The padded hash value is then raised by the private exponent using modular exponentiation. The modular exponentiation of the value will return a value that is between zero and the modulus. Each of the signature values between these numbers is about equally likely.

That also means that a significant amount of signatures have fewer than $n - 8$ bits when encoded as unsigned big endian integer. It depends on the value of the modulus, but you would expect about 1 in 192 to be smaller than $n - 8$ bits overall. Here $n$ is the number of bits that the modulus occupies; for RSA this is also the key size - this answer assumed that $n$ is a multiple of 8, e.g. 1024 in the question.

The I2OSP function in RSA PKCS#1 will however make sure that all signature values are left-padded with zero-valued bytes until signatures have the same size as the modulus. So signatures that start with 00-valued bytes are valid by definition.

  Couldn't a check like this (leftmost bytes != 0x00) be used to avoid this type of attack?

So, in conclusion, no, because your check would reject perfectly valid signatures.

The only check that can be meaningfully be performed before signature verification is to match the signature size (including zero bytes) to the key size.


PKI Multiple Samples start to expose Private Keys?

There's a wide gap between plaintext recovery and key recovery.  Of course, what is of interest to users is the confidenitality of their plaintext, but if an attacker can merely recover a single plaintext (which might happen outside the domain of crypto if the user just leaves it on the tube on their way to work!), that doesn't mean they can recover the next one—while if they can recover the key, they now have all the power of the legitimate user.
Public-key encryption is necessarily randomized so that if you send the same message to three people, or even send the same message to the same person three times, I still can't tell that just by looking at the ciphertexts without breaking the crypto.


How long will my encryption remain private?

The main good reasons to change keys periodically are:

to mitigate the risk of a key compromise; at least some ways keys get compromised are a one-time event, e.g. eavesdropping of the keyboard protecting the passphrase; changing the key thus restores security until the next leak, and only messages enciphered with the leaked key are compromised (and only those actively intercepted after the leak if the scheme provides forward secrecy)
so that humans remember the procedure;
addition per comment: in order to reduce the risk coming from using the same key of a block cipher for too many blocks; e.g. for 3DES in CBC mode: if the adversary has 32 GiB of known plaintext (e.g. all-zeroes of an idle link), chances that she can decipher 8 meaningful bytes from another 32 GiB worth of data are >63%.

The main reason to increase key size (which is, or at least should be exceptional compared to key change) is to induce retirement of the obsolete tools used to process the keys; not only is it business to security vendors, it often is the best way to increase security; for examples, if 1024-bit keys are deemed no longer usable, chances are that the Smart Card holding them will be replaced by newer ones, designed with better side-channel leakage protection. In my experience, resistance against brute force is rarely the real weak point in a commercial application (except if that was engineered-in, e.g. to meet some legal requirement).


Why is RSA encryption performed in mod n, but computation of inverse in $\bmod \varphi(n)$

What's relevant here is that the Carmichael totient $\lambda(n) = \operatorname{lcm}(p-1, q-1)$ is the exponent of the multiplicative group of integers modulo $n$, i.e. the smallest positive integer such that $x^{\lambda(n)} \equiv 1 \pmod n$ for all $x$.*

This means that if $ed$ is one more than an integer multiple of $\lambda(n)$, i.e. if $ed \equiv 1 \pmod{\lambda(n)}$ or, equivalently, if $ed = k\lambda(n)+1$ for some integer $k$, then $$x^{ed} = x^{k\lambda(n)+1} = (x^{\lambda(n)})^k x \equiv 1^kx = x \pmod n.$$

(Of course, the Euler totient $\varphi(n) = (p-1)(q-1)$ is itself an integer multiple of $\lambda(n)$, so $ed \equiv 1 \pmod{\varphi(n)}$ implies $ed \equiv 1 \pmod{\lambda(n)}$.)

*) To be precise, $x^{\lambda(n)} \equiv 1 \pmod n$ only holds for $x$ coprime with $n$, since if $x$ shares a prime factor with $n$, it won't be invertible modulo $n$ and no power of it can be congruent to $1$ modulo $n$.  That's why the definition of the modular multiplicative group requires the elements to be coprime to the modulus.  However, the slightly weaker congruence $x^{\lambda(n)+1} \equiv x \pmod n$ does hold for all $x$ as long as $n$ is squarefree, and that's all we really need for RSA.  Not to mention that finding a positive $x < n$ that's not coprime to the modulus $n$ is literally equivalent to factoring $n$.


You should definitely stick with Python or my fav, SageMath (which is Python based) when playing with elliptic curve crypto.

The private key is generally just a large scalar value, which when multiplied with the curves base point (in other words when we repeatedly double the base point) the resultant point is the public key.

There are subtleties that aren’t captured here, that vary across curves and production implementations.

I’d start in SageMath it’s an easy place to begin. Check out this link for a starter.


Proof of Knowledge/Data Integrity using Hash Function

From your question, I believe that what you are looking for is a proof of storage. I will point you in the direction of one paper, and you can use that to look for other work on the topic.


How do I calculate the maximum plain text length allowable for a certain cipher text length?

Well, to figure out this sort of thing, it's easier if we work backwards.

So, we start at the back (the fact that we can store up to 512 characters in a database field), and consider how much binary data we can store.  Well, base-4 takes 3 bytes of binary data, and encodes it in 4 bytes of base-64.  Thus, we can store 3*(512/4) = 384 bytes of binary encrypted data in 512 bytes of base 64.

Now, once we can store up to 384 bytes of encrypted data, we need to consider how much plaintext that corresponds to.  Well, you don't specifically mention an IV; in this situation, we might guess that the encryptor selects a random 16 byte IV and sets the first 16 bytes of the ciphertext to that.  The second thing to consider is whether the encryptor adds a message authentication code; that is a cryptographical check value that will allow you to detect if someone else modified the database field.  Now, you don't mention that you have one, so we'll assume that you do not.  This gives us a ciphertext region of 384-16 = 368 bytes.

Lastly, you mention that you use CBC mode with PKCS7 padding.  CBC mode always generates a ciphertext that's a multiple of 16; 368 is already a multiple of 16, so we don't loose any room there.  In addition, the length of the ciphertext is exactly the length of the padded plaintext; you mention PKCS7 padding, which always adds at least 1 character of padding; this gives us a final value of 367 bytes of plaintext which can fit.


Overdeterminate system of multivariate equation

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

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

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

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


how to avoid attack on Certificate Revocation List by the owner of the private key?

Yes one could do this, the repudiation wouldn't be very convincing.

The CRL really isn't very relevant. A person can always claim his private key was stolen. His credit card was stolen or his car was stolen.
We see people commit hit and run, realize what they have done park the car somewhere and report it stolen. Denying a credit card transaction etc.
If the car is reported stolen well before the hit and run that would be convincing proof.

As with CRL it would be convincing if the revocation is clearly before the transaction. But a revocation very close in time to the transaction doesn't provide a very convincing repudation though theft is plausible it is not common. And the private key owner could still be held responsible for his private key.

CRLs should not waive responsibility the second they are posted.


An efficiently computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ is said to be $(s,\epsilon)$-one-way if for every adversary $\mathsf{A}$ of size* at most $s=s(|x|)$ the probability $\Pr\left[{\mathsf{A}(f(x))\in f^{-1}(x)}\right]$ is at most $\epsilon=\epsilon(|x|)$, where the probability is over uniform distribution on the domain and the random coins of $\mathsf{A}$.

The standard one-wayness assumption is that $s=poly(|x|)$ and $\epsilon=negl(|x|)$ . A one-way function is subexponentially-hard if for a fixed constant $0<c<1$, it is $(2^{{|x|}^c},2^{-{|x|}^c})$-one-way. Note that the latter implies the former and is, therefore, a stronger assumption.

Similar definitions apply for the other primitives too.

*Here, size refers either to the run-time if $\mathsf{A}$ is a probabilistic Turing machine, or the circuit-size in case $\mathsf{A}$ is a circuit.


Is AES-XTS considered safe to encrypt multiple files with the same keys?

From a draft of the IEEE spec,

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

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

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

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

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

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

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

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

Best of luck!


LWE: does using only a small subspace of the plaintext space influence the security of the encryption scheme?

No, as long as your plaintext space is a subset of $Z_t$, then there is not any negative impact on security.

However, if you use a smaller message space $Z_x\subset Z_t$, you should consider setting the plaintext space to $Z_x$ directly as this could improve the efficiency.


Encryption schemes and pseudorandom permutations

The term "pseudorandom permutation" is normally used for a family of (computable) bijections $f_k : M \to M$, where $M$ is some finite set, and usually $M = \{0,1\}^n$. (Usually we also have a computable inverse for each $f_k$, and some security properties.)

If we stretch the meaning a bit, we can expand this to any finite set $M$, like "the set of all byte strings shorter than $2^{100}$ bytes" (i.e. more than anything you would ever want to encrypt. But when using this set, all common encryption schemes are, while permutations, not pseudorandom, because we can guess from the length of the output to the length of the input.

If we instead use as $M$ a set like "the set of all byte strings of length 1 KB", any good deterministic encryption scheme restricted to $M$ indeed should fulfill the properties of a random permutation on $M$.

A non-deterministic encryption scheme first will have to expand the ciphertext (e.g. by writing the IV into it), and secondly is not a permutation (a permutation is deterministic).

If we can extract the randomness part and use it as a separate input to a deterministic function (or, as a chooser for a family member), we can treat the encryption itself just like before.

But normally the term "random permutation" is used only for the actual building blocks of such encryption schemes, also named "block cipher".


To make the encrypt and decrypt passwords different, whoever has access to the encryption password would also need to know the key derived from the decrypt password, and the encrypt password simply unlocks that key. Then you have something like this:

Enc password is entered
Enc password is derived to key $K_E$
$K_E$ is used to decrypt the stored decrypt key $K_D$
A random key $K_R$ is used to encrypt the data
$K_R$ is encrypted with $K_D$ and appended to the message with the IV

Upon decrypt, the correct password will be derived to $K_D$ and used to unlock $K_R$, which can then decrypt the message.

In regards to the rest of your system, reading line by line is a very bad idea. In this case you are not encrypting the line breaks, and someone looking at the encrypted data will know the approximate structure of the message. You should read the file as a stream of bytes from end to end and encrypt all of them. The ciphertext should also not use any kind of encoding, as that could cause a problem during decryption. If you need the ciphertext to be copyable as text, like into an email or text message, it should be encoded to Base64.

Also simply hashing a password for use as a key is wrong, you need a key derivation function such as PBKDF2. There are MANY questions regarding this here, I would suggest reading a few of the highest voted questions and answers.


Why aren't Complex number fields used in cryptography?

Why aren't complex number fields used in cryptography?

If you mean fields of the form $k[i]/(i^2 + 1)$ where $i^2 + 1$ is irreducible over the base field $k$, well, they are!  FourQ is a twisted Edwards curve $-x^2 + y^2 = 1 + d x^2 y^2$ over the quadratic extension field $\mathbb F_{p^2} = \mathbb F_p[i]/(i^2 + 1)$ of Mersenne prime characteristic $p = 2^{127} - 1$, where $$d = 25317048443780598345676279555970305165i + 4205857648805777768770$$ is nonsquare.  FourQ is appealing because it takes advantage of cheap arithmetic modulo a Mersenne prime on a curve together with a cheap endomorphism.  The coordinate field is in a sense the ‘complex’ extension of $\mathbb F_{2^{127} - 1}$ arising by adjoining a square root of $-1$.

(FourQ is not universally appealing: it has a relatively high cofactor, $8\cdot7^2 = 392$, and it does not provide modern standards of twist security, so it's not a drop-in replacement for X25519 or Ed25519.  But it is implemented in practice by Microsoft's FourQlib and probably deployed somewhere.)


I don't see any obvious security problems in your approach. You can look into key derivation functions, that can provide some additional security in case one of the following occurs:

Your password leaks
Your secret number leaks
A weakness is identified in the hash function

There is a few usability issues, that would have to be addressed as well:

Different sites have different password policies (minimum password length, maximum password length, required characters, forbidden characters). There is no single function mapping from binary hash value to password string, which can be used with every password policy. Your current approach of using a hexadecimal string will run into two issues: Maximum length of password being 8 or 20 characters is not unusual. Requiring at least one non-alphanumerical character is also not unusual. Solution I propose for this is that you have different functions mapping from binary hash to password string, such you can choose one suitable for each site's particular policy. I think base64 is a better default than hexadecimal.
You may sometimes need to change the password on individual sites more frequently than others. Along with the site name you could include information about when the password was generated. A granularity of one month seems like a good balance between these two factors:

How often you may need to be able to change the password.
How easy you can remember the correct time as well as the possibility to brute force this single field, in case you forgot when the password was created, but remember everything else.

You may need to change your master password and keyfile because one of the two has leaked. But changing passwords for every site right away may not be feasible. To address this purpose, I would do the following:

Create a new secret number and associated password
Create a file containing the old password and secret number both encrypted using the new secret number and password.
Before starting to use the new password check a couple of times a day for a couple of days, that you can remember the new password. Verify this by decrypting the encrypted data and compare the secret number.
Once you have proven enough times that you can remember the new password, destroy the old clear text secret such that old passwords can only be accessed by decrypting using the new password.
From this point use the new data for all new passwords and only use the decryption for passwords, that have not been updated yet.
Record when the date on which the switch over was made.


They mean that you send a message template to anybody you want to fool, say, a certificate request to a certificate authority. You make sure that the MD5 is calculated over N 64 byte blocks of data generated by the other party, and then the 128 byte block you pre-calculated.

Now you receive back the data generated by the other party, ending with your 128 byte block, aligned on 64 bytes. In our example that would be a certificate. Now you can simply replace all the data generated by the other party, recalculate your 128 byte block and get the same MD5.

The other party, for instance the certificate authority, could use the generated MD5 to generate an MD5 with RSA signature. As the signature only depends on the private key of the other party and the MD5, the signature would be valid for both the original and the "fake" certificate.


Mental Poker with untrusted server (i.e. no peer to peer)

In general, from a security analysis viewpoint, there isn't much difference between a peer-to-peer protocol and one using an untrusted server — and, insofar as there is any, the peer-to-peer case is strictly harder to secure.

This is because, if we have a secure peer-to-peer protocol, we can always implement it over an untrusted server by simply having the server do nothing but forward messages between peers.  In typical attack scenarios, we already assume that the network connections between the peers may be controlled by the attacker, so giving the attacker control of a central relay server doesn't really add anything to their assumed capabilities.

Of course, if the security of the peer-to-peer protocol has only been shown under a weaker attack scenario — such as one where the attacker cannot intercept traffic between honest peers, or where they can only eavesdrop but not modify it — then the security proof may not carry over so directly.

Another potential cause of complications may be if we want to limit what the server will let the clients do.  In general, for peer-to-peer protocols, we assume that, in the absence of attacks, the network is neutral and will carry whatever messages the peers will send.  However, even an honest game server operator might reasonably balk at, say, letting the server relay arbitrary encrypted messages between clients, in which case protocols depending on establishing secure encrypted channels between peers may not be practical.  (They may still be secure, in the vacuous sense that a protocol where nobody ever sends any messages is secure, but that's not much consolation to someone who'd actually like to do something using the protocol.)


Why would someone want a 20ns block encryption completion on a 1us bus?

The authors of the NIST 8114 draft said that the times were arbitrary for the purpose of generating discussion.  They did, indeed, generate discussion.


RSA Decryption: Doubts: knowing p or $\phi(n)$ can lead to find private exponent?

1) Say if some hacker knew $p$, why would it be easy for them to find $q, \phi (n), d$?

Since $n = p \cdot q $ this implies $q$ is also known by simple division $p = n/q$.

Then $\phi(n) = (p-1)(q-1)$ is known

By using $e \cdot d \equiv 1 \bmod \phi(n)$ then $d$ is known. This can be found by the extended Euclidean algorithm.

  $d$ is a prime larger than $p, q$ so that $1 = k\cdot \phi(n) + d\cdot e$

$d$ doesn't need to be prime. It can be larger or smaller than the $p$ and $q$ depend on the value of $e,p,q$.

  2) Now, say if a hacker knew $\phi (n)$, why would it be easy to find $p,q,d$?

$d$ is as above.

1. Method with the knowledge of $\phi (n)$

$\phi(n) = (p-1)(q-1) = (n + 1)- (p+q) $ implies $$p+q = (n +1) - \phi(n)$$ and

$$q = (n+1) - \phi(n) - p $$ since we have $$ n = pq $$ substitue

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

Now, we got a quadratic equation that can be solved by the quadratic polynomial root-finding formula;$$p = \frac{-b \pm \sqrt{b^2 -4ac}}{2a}.$$ Using the formula one gets;

$$p = \frac{(n + 1 - \phi{(n)}) \pm \sqrt{(n + 1 - \phi{(n)})^2 - 4n}}{2}$$

Therefore the knowledge of the $\phi(n)$ enables factoring the $n$ in constant time, $\mathcal{O}(1)$

2. Method with the knowledge of $\phi (n)$

$(p+q)$ can be obtained from $n$ and $\phi(n)$ as $$\phi(n) = (p-1)(q-1) = n - (p+q) +1$$
$(p-q)$ can be obtained from $(p+q)^2-4n$, since $(p-q)$ is the square root of it.

Then one can find $q$ as $$q = \frac{(p+q)-(p-q)}{2}.$$


Is it possible in PGP to provide verification/verify the ownership of a public key?

In short, it is not about proving that you have any key, it is proving that this key is bound to a specific entity. The identity of the person submitting the key must be established.

The server doesn't know which keys to trust. It can sign any key, but what would be the point of that? The idea is that users can verify by other means that the key is trusted and belongs to the person submitting the request. Verification over the phone (using the key fingerprint) or even receiving expected messages at a particular time could do that. Otherwise an adversary can inject a public key belonging to their own key pair, using your identity information.

If you start just signing keys - without making sure that you can trust that the key belongs to a person - then you're actually poisoning the server. It is important to keep that in mind and give your friends / colleagues a call if you suspect anything is wrong. Certainly do verify that keys belong to the right entity when they have not yet been sufficiently verified by others.


Which ciphers produce random ciphertext?

Strictly speaking, we can't know for sure that the output of AES is indistinguishable from random noise. It's conjectured to be true but no "proof" of that fact exists.

For most commonly-used ciphers, it is conjectured that their output is indistinguishable from random. Specifically, modern ciphers are conjectured to be "strong pseudorandom permutations", which means that an adversary given encryption and decryption oracles for the cipher can't distinguish it from a random permutation.


Proving security of $\Pi' = E_k(E_k(m))$ knowing $\Pi = E_k(m)$ is secure

As Mikero noticed, the problem in your first proof is the fact that you can't suppose that $\mathcal{A}$ knows the secret $k$, and thus it can not encrypt the challenge.
And if you don't encrypt the challenge, then the input is not what is expected by $A'$. $A'$ is waiting $Enc^2_k(m)$ or $Enc^2_k(m')$ as a challenge not $Enc_k(m)$ or $Enc_k(m')$.
When you are doing a game-based proof, an important notion is the notion of
indistinguishability. For example If you are using an algorithm $\mathcal{A}$ as an oracle. And if you want to use some properties about the output of $\mathcal{A}$, it is important to check that the input of $\mathcal{A}$ follow the distribution which is mentioned in the property.
In your example, you are giving to the adversary $Enc(m)$ and not $Enc(Enc(m))$, it's completely different in the general case.
Let consider the xor encryption $Enc_k(m)= k\oplus m$.
It's really easy to build an attacker (let say a powerfull attacker who decrypts the ciphertext without the secret key) against $Enc^2$, it's just the identity function (Because $Dec_k^2=Enc^2_k$ is the identity function for all $k$.)
Then even $Enc$ is semantically secure, then $Enc^2$ could not to be. So a) is false.
But your proof about (b) seems correct to me.


trying to understand multiplication + reduction in binary finite fields

The last XOR is done, to get rid of the $x^8$ term. Polynomials in $GF(2^n)$ do have a maximum degree of $n-1$.


Simulation-based proofs - advice tape of reduction algorithm

Yes.

We work under the assumption that the protocol is not secure, which means that for infinitely many $n$, there is a pair of inputs $(x,y)$ on which the simulation fails (i.e., when the inputs are $x$ and $y$ the view generated by the simulator for at least one of the parties can be distinguished from a real one). Thus, when running on security parameter $n$, all non-uniform algorithms can be given $(x,y)$ as advice.

By the way, the reason why adversaries are only given $\sigma$ and $b_\sigma$ in this case (instead of $\sigma$ and $(b_\sigma,b_{1-\sigma})$) is that the given simulator always succeeds when $b_{1-\sigma} = 0$, so since we give an input pair where the simulator fails, it must be that $b_{1-\sigma} = 1$ and there is no need to give it explicitly.


What is a cyclic group of prime order q such that the DLP is hard?

Cyclic group of prime order q such that the DLP is hard

A simple technique to form a cyclic group $G$ of prime order $q$ such that the underlying discrete logarithm problem (DLP) is (conjecturally) hard, applicable to large $q$ (in the order of a thousand bits), is to pick $q$ as a random prime of appropriate size such that $p=2q+1$ is prime, and random any integer $g$ with $1<g<p-1$ such that $g^q\bmod p=1$.

The $q$ elements of the cyclic group $G$ are $g^i\bmod p$ with $0\le i<q$, under modular multiplication modulo $p$.

The search of $q$ can be greatly sped up by using sieving techniques removing $q$ such that either $q$ or $2q+1$ is divisible by a small prime. The search of $g$ is fast as is (on average two attempts are enough; it is common to use $g=2$, and towards that goal pick another $q$ and $p$ if $g^q\bmod p\neq1$).

It is conjectured that the DLP is hard, that is: given $y=g^x\bmod p$ for unknown random $x$ in $\mathbb Z_q$, it is computationally infeasible to find $x$. The current public record for solving such problem is for one instance of a 768-bit $p$. Current recommendations for a decade of security are 2048 or 3072 bits, but 1024 bit is still widely used. Standard groups with $p$ of a slightly special form making modular reduction easier are given in RFC 2409 and RFC 3526.

One way to obtain a speedup without sacrificing security (conjecturally) is to reduce the size of $q$, within some limit, with $q$ a divisor of $p-1$. That's a Schnorr group. See section 3.6.6 of Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, and their algorithm 11.54. Using a 256-bit $q$ for 2048-bit $p$ is believed to be about as safe as using a 2047-bit $q$, and recommendable. 160-bit $q$ is often used when $p$ is 1024-bit. Execution time is about in proportion to the bit size of $q$, and roughly in proportion to the square of the bit size of $p$.

Slowness is a often concern! Common algorithms to compute $y=g^x\bmod p$ perform like $3(\log_2(p)/w)^2\log_2(x)$ multiplications of $w$-bit words and additions of the $2w$-bit result. For a software implementation using 32-bit words, 2048-bit $p$ and 2047-bit $x$, we are talking over 25 million muladds. Careful implementations using assembly language shine, including the GNU Multiple Precision Arithmetic Library (which has wrappers in interpreted languages, including gmpy2). Also: be aware that side channel leakage, including by timing, is a security concern depending heavily on the implementation of modular exponentiation.

There are other constructions using an Elliptic Curve over a finite field, giving another large speedup without sacrificing security (conjecturally); and yet other less common techniques. In the following I'll stick to a $G$ a subgroup of $\mathbb Z_p^*$ of prime order $q$, with $p=r\cdot q+1$; and to $r=2$ (the simple technique discussed initially) unless otherwise noted.

Construction of H1

What's wanted is a hash with output in $\mathbb Z_q$, (conjecturally) secure in the random oracle model (that is: computationally undistinguishable from a random function with the same input and output domain, knowing the definition of $H_1$ except some arbitrary constant part of that public definition).

One problem is, usual cryptographic hashes have limited width; the widest in common use is SHA-512, and a 2047-bit $q$ is nearly 4 times as wide. If we processed the message $\alpha\in\{0, 1\}^*$ using SHA-512, no matter how we post-process the result, a negligible fraction of the elements of $\mathbb Z_q$ would be reachable (less than $2^{-1534}$); and in order for $H_1$ to be secure in the random oracle model, it must be computationally impossible to recognize elements in $\mathbb Z_q$ belonging to that fraction. Another issue is that usual cryptographic hashes have each of their output bits about evenly distributed for random input, but a random element of $\mathbb Z_q$ expressed as a bitstring of same size as $q$ has its high-order bit quite biased towards 0, unless $q$ is just below a power of two.

We can solve the size problem by concatenating several independent hashes, which we can obtain using HMAC-SHA-512 with different public arbitrary keys; and one method to approximate the right distribution in $\mathbb Z_q$ (beyond computational detectability) is generating at least (say) 128 more bits than in $q$, followed by modular reduction modulo $q$ (assimilating bitstrings to integer per big-endian convention).

With that method and $q$ of 2047 bits, we need $\lceil(2047+128)/512\rceil=5$ concatenated HMAC-SHA-512. For message $\alpha\in\{0, 1\}^*$ the hash could be
$$H_1(\alpha)=\big(HMAC(\text{0x01},\alpha)\|HMAC(\text{0x02},\alpha)\|\dots \|HMAC(\text{0x05},\alpha)\big)\bmod q$$

Note: when using $q$ of up to 384 bits, which is fine if $p$ is still large enough, we won't need the complexity of concatenating multiple hashes.

Construction of H2

What's wanted is a hash with output in the group $G$ constructed in the first section, (conjecturally) secure in the random oracle model. But there's a catch!

The quote in the question precisely matches section 3.1 of Joseph K. Liu and Duncan S. Wong's Linkable ring signature: security models and new schemes, in proceedings of ICCSA 2005, which I located by asking Google Books for distinct hash functions viewed as random oracles. Right after the question's quote is:

  Assume that for any $\alpha\in\{0, 1\}^*$, the discrete-log of $H_2(\alpha)$ to the base $g$ is intractable.

The reasonable way to interpret this additional requirement is that knowing the definition of $H_2$, and given $\alpha$, one should be computationally unable to find $x$ with $g^x=H_2(\alpha)$.

Adapting Poncho's great suggestion so that it works regardless of $r$, for 2048-bit $p$ we can use
$$H_2(\alpha)=\Big(\big((HMAC(\text{0x11},\alpha)\|\dots\|HMAC(\text{0x15},\alpha))\bmod(p-1)\big)+1\Big)^r\bmod p$$

This works by generating a random element $u$ of $\mathbb Z_p^*$, and computing $v=u^r\bmod p$. The result is in $\mathbb Z_q$, because $v^q\equiv{(u^r)}^q\equiv u^{rq}\equiv u^{p-1}\bmod p\equiv 1\pmod p$, with the last step using Fermat's little theorem. With $u$ essentially uniform on $\mathbb Z_p^*$, $v$ is essentially uniform on $G$.

I wish I had proof of my intuition that, for general $r$, solving  $g^x\bmod p=v$ for $x$ is hard including with knowledge of $u$; and that we could get away with generating $u$ in $\mathbb Z_q^*$ rather than in $\mathbb Z_p^*$. Poncho proved both for $r=2$.

Words of caution: Many papers on ring signatures and e-voting that I have attempted to follow have lost me; I was often left wondering what exactly is assumed and proven about security, and what that means in practice. Some use a bilinear pairing; while there are libraries for that, I advise to dive into this stuff only if all the math above has been striking one as evidence.

I'm sure that only a small fraction of the voting population can form an informed opinion on these topics. I conclude that using such methods for voting goes straight against a major goal: that voters trust the result.


Is this a bit string of length $n$? If so why don’t they write it as $\{0,1\}^n$?

$\{0,1\}^n$ is not "a string of length $n$", it is the set of all strings of length $n$ (formally, the Cartesian product of $n$ copies of the set $\{0,1\}$). $1^n$ is an element of this set; namely the one where all bits are $1$.


Why would an RSA library tell me that the public key must be at least 512 bits in size?

Your javascript library linked to has no restrictions on key size. Many libraries out there that implement RSA will have a restriction on the key size. This is to make sure developers are following best practices as if the key size is too small, the security of the cipher is completely blown. It looks like the Java library you are using won't let you use key sizes of less than 512 bits (which is still too small, even 1024 bits for RSA is no longer recommended for long term security).

If you remove the check for 512 bits, that should take care of the error.

Final Thoughts
I think it should be noted again that 512 bit RSA keys are way too small. Since you will be interoperating with something that is not secure, you'll need to think about what that means when it comes to the security of your system. You won't be able to change what the web service is doing, but you still need to think about how it affects the security of your system.


Current standard for hash function security parameter?

Hashes should work on any number of input bits (almost all I/O parameters in cryptography are defined in bits). The output size for collision resistance should be twice the security level. So for a 128 bit level, use 256 bit hashes.


Why are the IV (constant) values fixed for HMAC/SHA?

The hash IV values aren't provided to the user for the simple reason that they are not required.

The whole idea of a hash function is that you get a practically unique value that is irrevocably linked to the input message without exposing any details of the message. Using an IV would go against this idea: it would give you a different value each time the IV is changed.

This is not the case for ciphers, which require randomization to be CPA secure. If they wouldn't then repeating messages would be identical for the same key. You could for CBC of course start with an in the plaintext, but that would mean that the ciphertext would always have to be expanded. This could be wasteful as there is no requirement that the IV is send with the ciphertext.

This shows another reason why not to include an IV in the interface of a hash function. If a unique value is required you can simply include it with the message. It will only be included in the hash calculation rather than expanding the output of the hash.

Now there are actually reasons where having different constants is beneficial.

One is when a shortened hash value could leak information about the full or less shortened hash. For instance, if an adversary has a SHA-512/256 hash then the adversary would also have the first part of the SHA-512/384 or SHA-512 hashes. For that reason these hashes do actually have different constants.

Another reason is when hashes are used 1. with the same input and 2. for different purposes. In that case it could be beneficial to have some differentiating bits included in the hash. This is a scheme that is actually present in SHA-3, where a KMAC algorithm and the SHAKE functions use a few different bits than the raw hash algorithm.

HMAC doesn't have this kind of protection. It does however use the key in two different ways so you'd have to create a pretty weird scheme to ever get into trouble by hashing a key, message and duplicate a HMAC result.

Modifying these constants should not affect the algorithm at all. If you however use your own constant values then people might get suspicious that you know more about the algorithm than themselves. You're better off using the original constants as "nothing up-your-sleeve" values.

If you need additional input of some kind, just make it part of the message, making sure that the encoding of the message is canonical. That is, make sure that different fields in the message can be distinguished, e.g. by prefixing the length before each field.


By definition, an integer $a$ is $n$-bit iff $2^{n-1}\le a<2^n$. It follows that the product of two $n$-bit primes is a composite of $2n$ or $2n-1$ bits.

In order to generate an RSA key of $2n$ bits, it is customary to generate two $n$-bit primes each at least $2^{n-1/2}$; this ensures that their product is at least $2^{2n-1}$, thus exactly $2n$-bit.

$1204$ or $2408$ bits would be unusual RSA key sizes. $1024=2^{10}$ bits used to be common, $2048=2^{11}$, $3072=3\cdot2^{10}$, and $4096=2^{12}$ bits are common modern sizes.


As per the Hasse's theorem the total number of points can be computed for both the Finite field curve and binary field curve

For the Finite Field , the number of points on E(F p) is denoted by #E(F p). The Hasse
Theorem states that:
p+1-2√p≤ E(F p) ≤p+1+2√p.

For the Binary field, The number of points on E(F2^m)() is denoted by #E(F2^m). The Hasse Theorem states that:
2^m+1-2√2^m≤#E(F2^m) ≤2^m+1+2√2^m.

For Every x co-ordinate there are 2 Y co-ordinates.
Hence the number of X co-ordinates can be deduced as per the calculation of Hasse's theorem points/2.


For the clearly cryptographic recommendations:

AES CTR + MAC: still good advice, though AES-GCM is a good alternative. His recommendation of 256-bit keys clashes with Schneier's (also 2009) recommendation of 128-bit due to the weaker 256-bit key schedule. Neither choice is broken, however.
HMAC-SHA-256 as MAC: still good advice. While SHA-3 has been published, it has not yet seen as much use and SHA-2 remains unbroken.
256-bit random UIDs: 256-bits is not going to risk collisions, like ever.
PBKDF2 or scrypt: still fine. Although PHC chose Argon2 as a possible successor, it does not have much uptake yet.
RSAES-OAEP: I am torn here. It is a secure choice for public key encryption, but like he says it is easy to get wrong. A good elliptic curve would be as secure, faster, and ECC keys are much smaller. Not bad advice.
RSASSA-PSS: unlike the above, this is fairly simple. However, signature size is also large compared to ECC. Secure, but not always the Right Answer, as he says.
Diffie-Hellman on group #14. Still good advice.

So none of it is bad advice even after seven years.


Appending hexadecimal string for MD5 algorithm

In MD5, the addition performed on $B$ at each round is modulo $2^{32}$ (that is, only the 32 low-order bits of the result are kept); same for the additions involving $A$, $F$, $K$ and $M$ at each round, and the four additions on $A$, $B$, $C$ and $D$ at the end of the 64 rounds.

Therefore, $A$, $B$, $C$ and $D$ all remain within 32 bits. At the end of the hashing, the concatenation of their representation as 32 bits forms the final hash, which is thus exactly 128-bit.


Is there any standard present to measure strength of a generated key using true random number generator?

The NIST special publication 800-90B is probably your go to here. It is the approach used to meet the FIPS 140-3 requirements which are accepted by as good assurance by a large population.
Different approaches are taken for TRNGs that are believed to produce independent, identically distributed outputs and others. One of the key measurements is the minimum entropy ($H_\infty$ in the Shannon-Renyi sense) that tracks the most probable output of some fixed size output. If the only information available to the attacker is the minimum entropy of the key, their guessing work should be at least on the order of $2^{H_\infty}$.
ETA: as pointed out in the comments, because your question is specifically about Diffie-Hellman, there are subexhaustive attacks. In particular 128-bit keys can be recovered with 64-bits of group operations using Pollard rho/baby step-giant step/Pollard kangaroo.


Is it safe to use a deterministic salt as an input to KDF (Argon2)?

It seem to be a controversial thing to do but I didn't find any convincing arguments against it

It can be a good solution if you can transmit the salt from the server to the client, e.g. in apps or desktop apps and has some nice load-distribution properties.

  the server hashes any recieved password anyway, so no plaintext records in the database

This is actually important so a leaked database doesn't immediately allow for logins.

  Would it make a good salt?

It would work. However the "issue" is that it allows for targeted pre-computation attacks. So suppose you have an adversary who already knows a set of target users. For them they can now pre-compute a lot of password hashes so once the password database is compromised there's a very low latency to password recovery for the targets if the precomputed hashes contain a match. If you're not worried about such attacks uniqueness is the only property required from salts and may be achieved in any arbitrary way.

Indeed if you have control over the client and have bidirectional communication, using a protocol like OPAQUE is preferred as it also hides the salt.


In Diffie-Hellman, can everything be sent in plaintext?

TLDR:

Diffie-Hellman key exchange works differently
Yes, DH is vulnerable to MitM.

Long answer:

Diffie-Hellman key exchange isn't about sending the public key with some kind of signature, but about negotiating the key.

Quick DH explaination (note: these values are very insecure):

Alice and Bob publicly agree on two values:

The generator - g. Let's say this is 3.
The prime modulus (obviously a prime number) - p. Let's say this is 17.

Both Alice and Bob think of a secret value, let's call this x

Alice's secret value is 15
Bob's secret value is 13

They calculate yet another values, using this formula: g^x mod p

Alice: 3^15 mod 17 = 6
Bob: 3^13 mod 17 = 12

Alice sends the result to Bob and vice versa
They both calculate the final value like this:

Alice: 12^15 mod 17 = 10
Bob: 6^13 mod 17 = 10

They have negotiated a key and Eve doesn't know what's the value of this key (the negotiation requires a lot of values to be exchanged and therefore simply listening but not participating in the exchange doesn't let you see the established key)

MitM example:

Imagine this "circuit":

Alice -- Eve -- Bob

Eve changed the values when they were exchanging them, decrypts everything that comes from Alice with the key she has exchanged with Alice, and then encrypts it with the key she has exchanged with Bob and vice versa.

Conclusion:

There's a need for some kind of "pre-shared secret" with DH. DH itself is not MitM-proof. For SSL/TLS that is Certificate Authorities. Instant messaging often uses OTR (which involves a question that only the actual other party should be able to answer - pre-shared secret).


CRL number generation sequence: can I use a time stamp?

Using a time stamp is certainly allowed, provided it is truly monotonically increasing. What I want to point out here is that computers have knowledge of the current date and time through their internal clock, which may be subject to drift and therefore to alterations to put it "back in line". Some systems will rely on NTP, a network protocol which is not the most secure protocol ever (in fact, base NTP is completely unauthenticated, thereby active attacker may fool with your clocks to some extent). Other CA, that try to work without relying on an unsecured network protocol, may be subject to heavy drifting over time, thereby requiring an occasional manual reset. Both the drift and the risk of human error may induce the CA into issuing a CRL with a non-monotonic number, which is a problem.

Another point to take into consideration is that "relying parties" (the systems that will read and process your CRL) may convert CRL numbers into relatively small integers, under the (faulty) assumption that "MAX" means "fits in a signed 32-bit integer". Beware of Year 2038! This would not be, technically, your fault (the RFC is clear in that respect), but it would still impact the already flimsy support for revocation.

For these reasons, a CRL counter, that is updated and saved across reboots, seems to be a better idea, from an engineering point of view.


Signature verifying against multiple certified public keys?

From a cryptography perspective, this works as advertised; Eve and Frita can generate signature keys where a nontrivial fraction of signatures for one key will validate with the other.

That said:

It is trivial to detect this, if anyone looks.  If we suspect that Eve and Frita are colluding (which we may, if someone demonstrates a signature that validates with both public keys), then a simple computation of $\text{gcd}( N_e, N_f )$ will reveal it.  Alternatively, if someone just checks either $N_e$ or $N_f$ for small factors, that'd show that something nonkosher is going on.  While I don't believe most CA's routinely check the public keys submitted to them for small factors, there might be some that do (and it certainly would not be expensive, compared to the other operations CA's must do).
It's not clear if this is actually an attack; $S$ is a valid signature for $M$ under $Pub_e$, and Eve cannot argue that it's not.  Eve's argument of 'maybe Frita did it' doesn't address the question of 'how did Frita forge a signature of Eve's key'.
Also, as for your question of 'maybe real signatures embed a public key identifier', no, they do not.


Is it possible to find data which makes sense when decrypted with different keys?

Yes. How to find such data depends on which encryption you are using. With one time pads it's trivial: You can freely choose another pad that when used as a key will decrypt the ciphertext to an arbitrary message (of proper length).


This is identical with CTR mode encryption with a MAC. That's known to be secure.

It doesn't say in your question if:

the Ai blocks are completely unique;
the header is included in the MIC calculation.

If those preconditions are met then I don't see any issue with the protocol.

The first one I cannot verify but seems likely, the second one is certainly true (when I look at the linked document).

Note that the MIC is somewhat short, only 32 bits. For this protocol it could be enough. On the other hand, the AES-128 based CMAC calculation is fine for a MIC.

Disclaimer: this should not be seen as a full review of the protocol, just a direct answer to the question.


What type of cipher or encryption method is this called?

Adding the previous block to the plaintext before encryption is what the CBC mode of operation does. So you're essentially treating the Caesar cipher as a block-cipher and using it in CBC mode.

This adds no security relative to a plain Caesar cipher, since the attacker can simply undo the addition before proceeding to break Caesar as usual.

  the majority of the well known ciphers

That property is shared by substitution ciphers, but not by Vigenere. Modern ciphers don't have any such obvious weaknesses either if you use them correctly.


Some terms related to secret sharing: Optimality, What does it mean?

Optimality is actually not a well-defined term for secret sharing, and can refer to a number of different issues. First, one issue that is often considered is the size of the share that each party holds in the scheme. If the size of a party's share equals the size of the secret itself, then the secret sharing scheme is called ideal. (Formally, we don't talk about "size" but that the shares comes from the same domain as the secret.) Shamir's secret sharing scheme is ideal.

Other issues which come up are the threshold: how many parties are needed to reconstruct the secret versus against how many parties security holds, what the threshold is for active/passive security and so on.

In short, the paper should define what they mean by optimal, and especially regarding what parameters.


Like Richie Frame commented, as SHA-2 padding uses the length of the message that is not possible. Specifically, even if you had some string of input that took you from the SHA-512 IV to the SHA-512/256 IV, any message you hashed with it prepended would have a different length and thus a different hash value.

Additionally, even ignoring the padding it would be infeasible to find such a string. The IV constants for SHA-512/n have been chosen using an algorithm that does not start with the normal SHA-512 IV, so it would require a preimage attack on the compression function to find one.

However, unless you need compatibility or conformance with SHA-512/256, you could just use SHA-512 and truncate. See page 27 of the FIPS document you linked.


If I interpret your question correctly, your unchanging 4-character input is probably just a PIN code that unlocks the use of the device. In this case, the sequence of 6-character strings is a series of one-time password to unlock access to a remote device.

Under this assumption, they is no simple way to predict the rest of the sequence. Indeed, it is easy to design secure device of this type. A simple solution is to output a hash of some inner state and then update the state using a secret key algorithm keyed with a key shared by the device and its remote partner. The most difficult issue is to solve desynchronization problems (e.g. what happens if you advance your local device 1000 times without transmitting anything, will the 1001-th code work ?)

Of course, it is also possible to construct insecure devices of this type. So if you have luck your exact device might be attackable.

However, the short answer is: no, in general, this is not doable.


With the random numbers generated, can I know which RNG seed was used?

If the RNG is cryptographically strong, then you should not be able to do any better than the naive brute force: try each seed until you get matching random numbers.

If this is a homework question, then I would guess that either they used a very small seed (like "3" or "15"), or the RNG is not cryptographic strength and with some time analyzing the linear congruence algorithm, you might see how to invert it.


Is it possible to distinguish a securely-encrypted ciphertext from random noise?

It... depends.

AES is a block cipher. It works over 128-bit blocks. For a given key, AES is a permutation of the $2^{128}$ possible values that 128-bit blocks may assume. As a purportedly secure block cipher, AES is supposed to be indistinguishable from a random permutation, i.e. a permutation selected randomly and uniformly among the $2^{128}!$ possible permutations of the space of 128-bit blocks.

If you consider AES used in counter mode (CTR): some piece of hardware encrypts the successive values of a counter with AES, and spews out the concatenation of the encrypted blocks. You challenge the attacker to distinguish between such a stream, and a purely random stream of equal length. Since AES is a permutation, the AES-CTR stream will never include twice the same block value (by encrypting two distinct counter values, you necessarily obtain two distinct block values). However, the purely random stream is also expected not to repeat the same 128-bit value, until you reach a length of about $2^{64}$ blocks, i.e. quite a lot.

In that sense, AES-CTR is supposed to be indistinguishable from random noise: if AES-CTR was distinguishable, then this would imply that AES (the block cipher) is not indistinguishable from a random permutation, and that would be viewed as a structural weakness in AES. With a $k$-bit key, the cost of distinguishing AES from a random permutation should be $2^{k-1}$, no less (that's the average cost of brute-forcing the key). No such structural weakness is known yet for AES (for AES-192 and AES-256 there are some related-key attacks, but they imply using several AES instances with specific keys which are linked to each other algebraically).

Now, although indistinguishability is academically important (a cipher is deemed weak if it cannot achieve it), it is rarely relevant to practical situations. Most protocols which use encryption very straightforwardly admit to using a specific encryption protocol. For instance, if you use SSL/TLS, the client and server announce in the initial handshake message what kind of encryption algorithm is used, and this is not a problem for practical security. If security crumbles when the algorithm is known, then this is also considered as a structural weakness of the algorithm.


Is there a problem with constructing a CSPRNG using MD5 or SHA1?

Well, it is quite possible to have a CSPRNG that uses MD5, or SHA-1, despite their known flaws.  In fact, see Hash_DRBG with SHA-1 for an example that is officially endorsed by the US Government.  They don't endorse it for MD5; however, they really don't endorse MD5 for any reason (except within the TLS key derivation function).

The problem with MD5 and SHA-1 is that it is possible to create two different images that hash to the same value (with MD5, it turns out that you have quite a bit of flexibility, with SHA-1, it's been estimated to be practical, however I have not heard of anyone actually generating a colliding pair).  However, creating a collision means that the attacker gets to select both pairs; with a CSPRNG, the attacker cannot influence the internal state (he can only observe). This implies that the ability to create a collision has no impact on CSPRNG security; after all, even if the attacker generates a colliding pair, he has no way of making the CSPRNG use one of the preimages he has created.

Also, one warning: just because it is possible to design a CSPRNG based on SHA-1 or MD5 doesn't mean that design that you have in mind is actually secure.

Now, when you talk about efficiency, well, SHA-1 and MD5 aren't great; they're designed to hash things quickly, not generate hashed bytes quickly (oddly enough, those aren't the same thing).  The CTR_DRBG CSPRNG from the same document is somewhat better; however, the output of a good keystream generator (such as ISAAC) is going to be faster still.


What is the size of a 1024-bit RSA cipher compared to its plaintext?

RSA is almost always used in hybrid mode, where AES (or another symmetric cipher) is used to encrypt the data itself, and RSA is then used to encrypt the random data key. That way RSA has only a static overhead: the modulus size (which is also the key size) in bytes. So for RSA-1024 that would mean an overhead of 128 bytes + whatever overhead is required for the symmetric cipher (which can be zero bytes if a stream cipher or stream cipher mode such as counter mode is used). In that case you'd have $50000 / 8 + 1024 / 8 = 6250 + 128 = 6378$ bytes if I'm not mistaken.
Using unpadded / raw or textbook RSA (i.e. RSA using only modular exponentiation) is insecure. So you always need to pad the plaintext message within RSA. In that case you would for instance use RSA-OAEP as defined in the later PKCS#1 standards. This padding scheme adds quite a lot of overhead. Generally we don't care about that, because there is plenty left over to encrypt a symmetric key when using hybrid encryption. However, if you'd use multiple RSA encryptions in sequence then you would have an overhead of 42 bytes and a payload of only 86 bytes, assuming a SHA-1 hash within OAEP for minimum overhead. A single encrypted partial message would still be 128 bytes. So you would have $\big\lceil 6250 / 86
 \big\rceil \cdot 128 = 73 * 128 = 9344$ bytes taken, an increase of $2966$ bytes (!)
A few notes to these calculations:

RSA as specified in PKCS#1 always sets the output of encryption to be the modulus size in bytes, even if the actual number is smaller. That way the size is always static and doesn't need to be indicated (unless the key size is not known in advance). If you would allow alternating sizes then you would need to indicate the output size of each encryption, or you would not be able to separate the resulting RSA ciphertext blocks.
RSA-PKCS#1 v1.5 padding can also be used. PKCS#1 v1.5 padding is an older, less secure scheme. PKCS#1 v1.5 padding has somewhat less overhead in the non-hybrid scheme.
RSA-KEM is another scheme for hybrid encryption. It doesn't encrypt a symmetric key; it encrypts a master secret used to derive a symmetric key and is arguably more secure. It doesn't add any overhead to hybrid encryption. It cannot be used to encrypt the message directly or in parts.
Message integrity / authenticity is not taken into account in above. If that's required generally we use a sign-then encrypt scheme which increases the plaintext message before encryption.
Generally other overhead is also present. For instance, CMS based encryption also indicates certificates and algorithms used to the receiver. So you cannot generally expect the plaintext message to expand only with regard to the RSA key size.
RSA-1024 has already been deprecated by NIST (for medium and long term encryption) and is generally considered too small. Note that increasing the key size actually has positive effects on the relative amount of overhead required (when concatenating RSA encryption of partial messages); a larger RSA key size would actually be beneficial w.r.t. size. Unfortunately, that comes at a price of ever increasing CPU requirements, especially for RSA decryption and (one time) key generation.


I agree with the comments that SHA-256 should be fine here.

However, if you already use HMAC-SHA-256 for PBKDF2, you could use HKDF Expand, which despite its name is defined even for output lengths shorter than input. In your case the output would be simply:

$$\operatorname{HMAC-SHA-256}(\text{key}, \text{info} || \text{0x01}),$$

where 'info' is an optional, arbitrary string to specify this particular key in case you ever need to derive another key from the same material and '0x01' is the byte with value 1.


Gentry-Halevi’s Fully-Homomorphic Encryption and hermite factor

It is computed like that:
L is lattice with dimension i. B is BKZ reduction of lattice L.

$$Root Hermite Factor=( B[0].norm() / ( L.volume() )^{(1/i)})^{(1/i)}$$

If you want to calculate RHF, you can use Sage Math.


Designing such a challenge is Impossible.

If we assume that having a connection is equal to being able to exchange any piece of knowledge at any given time then the proof of impossibility of such challenge is as follows:

Proof. First assume that there is such a challenge and Alice is capable of querying such a challenge to correctly determine whether the connection exists.

We give Bob and Carol the exact same knowledge set $K$ prior to the start of the challenge. (Obviously this knowledge set could contain a random tape: an infinite sequence of random bits) Bob and Carol are going to give answers to Alice only based on the knowledge set $K$ and what they later learn from Alice during the challenge.

Since Bob and Carol share the exact same knowledge set both of them know exactly what would be the answer of the other one to any given question about anything they already knew (knowledge set $K$). Their answers to these questions would be either "I can't/don't know" (the question asks about information outside of the knowledge set $K$) or something that both of them are exactly aware of.

To elaborate more clearly, the answers to questions and challenge which require some sort of randomness such as "quote me a title or line from any famous song, book, movie or poem", "send me a ten digit prime number" or "name a tree" would be answered based on an already shared random tape. Which means that at any given time they know exactly which member of all possible correct answers in their knowledge set is the given answer of the other one.

To further clarify things, it should be mentioned that as Bob and Carol have the exact same knowledge set $K$ all questions and challenges that are related to each other in some form would have consistent answers. For example, if Alice asks Bob "Name all of your favorite supercars" and then asks Carol "Does Bob like to have a Ferrari?" should yield consistent answers.

Accordingly, there is no challenge that questions about the knowledge set $K$ which proves the "connection" since consistent answers do not require any "exchange" of information. So, the challenge should ask a question which at least partially assesses the information that Bob and Carol acquired during the challenge.

Assume that the knowledge set $K$ plus what Bob learned from Alice during the challenge is $K_B$ and for Carol it is $K_C$. For the challenge to prove the connection $K_B$ should not be equal to $K_C$ otherwise as discussed earlier both Bob and Carol would know exactly what would be the answer of the other one to any given question and the challenge cannot prove the "connection" since consistent answers do not require any "exchange" of information.

Thus, they should have learned different things from Alice which is impossible since they receive same messages simultaneously from Alice.


Is using Euler's Totient/phi in Tonelli-Shanks (used to recover EC coordinate) safe?

As user94293 says, $q\equiv 3\bmod4 \implies q+1\equiv0\bmod 4$ hence $\frac{q+1}{4}$ is an integer. Clearly it is smaller than $q$ and larger than $0$, hence reducing it mod $q-1$ does not change anything. Hence in your circumstance everything is okay.

In a bit of a more broad context, determining whether something is "safe to use" depends on context. What can generally go wrong is that execution time of an algorithm is dependent on some secret data. An attacker will exploit this timing dependency to gain information about the secret, which is indeed a problem. So in this case you can ask yourself two more general questions:

What information could an attacker learn if you were to compute $$\left(x^3+7\right)^{\frac{q+1}{4}\bmod{q-1}}\bmod{q}$$ as opposed to
$$\left(x^3+7\right)^{\frac{q+1}{4}}\bmod{q}?$$
As long as you don't compute either one or the other depending on some secret, both are fine. Note that this includes that we could choose to compute a square root by doing
$$\left(x^3+7\right)^{\frac{q+1}{4}+1000(q-1)}\bmod{q},$$
but we won't because it is not efficient.
What data is actually being processed? I'm not aware of the details of the protocol you are working with, but in many cases $x$-coordinates of points are part of public data. In that case even if you do the exponentiation based on the value of $x$, an attacker can still not learn anything secret.

In short, it is important to remember that it is not important for an algorithm to be constant time, but to have run-time independent of secret data.


Why does DES use a block size of 64 bit?

A minimum block size is required for a block cipher mode of operation to be considered secure. If the block size is too small then issues may arise.

Many modes of operation for instance use an IV that has the same size as the block size. If the block size would be smaller then a randomly generated IV could repeat. This will happen quickly especially if many messages are encrypted using the same key.

Worse, a mode such as CBC uses the last ciphertext as vector for the next step, so the ciphertext could repeat as well, which means that the ciphertext could leak information about the plaintext. For counter (CTR) mode the counter could start to repeat, which could lead to a complete loss of confidentiality of the plaintext message.

So using a block cipher with a small block size will lead to security issues, even if the block cipher itself is considered secure.

On the other hand a block should not be too big. Larger block sizes require a more complex cipher and likely require more internal state. This is especially a problem if space is an issue, and space always is for hardware implementations of the block cipher.

Also note that modes of operation always require at least one operation of the full block cipher for the last bytes of the message. So if 1 byte is encrypted the full block cipher still needs to be executed for that single byte. Many modes of operation output a multiple of the block size, so there may be additional storage / communication overhead for larger block sizes (on top of the larger IV).

So using a block cipher with a larger block size will increase the memory requirements and as well as the CPU and storage overhead required for the ciphertext.

To simplify calculations, enhance memory efficiency (alignment) and so forth, many computer algorithms perform operations using powers of two. Although it would probably be possible to specify a block cipher as an algorithm of 65 bits the algorithm and implementation would be tricky to design correctly. Ciphers are generally specifies using byte boundaries and preferably using powers of two.

Furthermore, it makes sense to make the (encoded) key size and the block size match up. That way it is easy to encrypt one key with the other. A DES key consists of 56 bits and 8 parity bits. That means that a 64 bit DES key can be directly encrypted (wrapped) by another DES key, without requiring any mode of operation.

AES-192 - which has a key size of 192 bits and a block size of 128 bits - is awkward to correctly use because 192 is not a multiple of the block size of 128 bits.

In the end the block size is selected by the designers with the above three points in mind. The block size is therefore a compromise between security and efficiency.

Modern ciphers do not use a block size of 64 bits anymore; most cryptographers would consider 64-bit block ciphers outdated. They may not be broken, but the 64 bit block size makes them insecure in many situations. Single DES is of course considered broken, mainly because of the small effective key size.

AES has a block size of 128 bits, as this was mandatory for every AES candidate during the AES competition. But even 128 bits is sometimes considered not that secure anymore. Counter mode encryption and many authenticated ciphers that rely on it have limitations, mainly when the 128 bits are used for different purposes (a 64 bit random nonce and 64 bit counter, for instance).

So other block ciphers even use a larger block size. Threefish (which is part of Skein, one of the SHA-3 candidates) uses a block size of 256 bits. This helps it being used as a tweakable block cipher within the Skein hash algorithm.

With Blowfish using 64 bit block size, Twofish using 128 bits and Threefish using 256 I guess you can see where we're heading. That said, a block size of 256 / 512 bits may be large enough for most purposes, so this trend to larger block sizes will likely not continue forever.

Note that many modern CPU's have been designed with 64 bit and SIMD operations and may be more efficient for larger block sizes and / or larger internal state. So a smaller block size may not always be more efficient; for instance SHA-512 is commonly both more secure and faster than SHA-256 on a CPU with an AMD64 instruction set, especially for large messages.


Fast software implementations of AES were proposed in a number of research papers. The state-of-the-art approach is to do a bitsliced implementation, where bits of sequential blocks at identical positions are processed at the same time.

The fastest implementation described so far that does not use AES-NI instructions was designed by Kasper and Schwabe. Their paper is online and is highly recommended for those who are interested in fast AES implementations. It would not make sense to copy the entire paper here, but specific questions can be answered.


Naccache–Stern knapsack cryptosystem: How to calculate $p_i ^{s^{-1}} \mod p$?

In the Naccache-Stern knapsack cryptosystem, it holds that $\gcd(s,p-1) = 1$. Hence, you can compute the inverse of $s$ modulo $p-1$ (the coprimality ensure the existence of such an inverse). Computing this inverse can be done with the extended Euclidean algorithm, which gives you $u,v$ such that $su + (p-1) v = 1$: as $su = 1 \bmod p-1$, $u$ is indeed the inverse of $s$ modulo $p-1$.

As $p$ is a prime, its multiplicative subgroup has order $p-1$, hence $\sqrt[s]{p_i} \bmod p = p_i^{s^{-1} \bmod p-1} \bmod p = p_i^u \bmod p$. So, once you've computed $u$ from the extended Euclidean algorithm, finding the $s$-th root of $p_i$ modulo $p$ is reduced to computing a modular exponentiation.


Fast 128-bit MAC with second preimage resistance?

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

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

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

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

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


Probability that two different files can have same MD5 hash for both an unencrypted and encrypted version (AES256, same key between files)

What is the probability that both [Hu] = [Hmu] and [He] = [Hme]. In english, what is the chance that two different files can have identical hashes in both an unencrypted and encrypted form?

Depends on whether they are "random" files or attacker controlled.

MD5 is a 128-bit hash, so for two random files that differ the probability that they have the same MD5 hash is $2^{-128}$. If they are encrypted with strong encryption, their encrypted versions will be random files with again $2^{-128}$ probability of having the same hash. The chance that both happen for the same files is then $2^{-256}$.

For attacker chosen files it's a different matter. It is easy to construct two files with the same MD5. If the attacker knows the encryption key, they may even be able to construct two files with equal hashes in both unencrypted and encrypted forms (brute force search takes about $2^{64}$ if nothing else helps).

  My guy says it isn't possible, or the odds are dependent on the size of [Fu]. Thoughts?

As for file size, it doesn't matter beyond the files having to be large enough that collisions exist. In practice something like 512 bits (64 bytes) is enough. In theory there are inputs that are only about 64 bits and collide, but finding them may be more difficult.


If I understood correctly, instead of storing the full hash value, you just store 2-byte. As always, we assume that the attacker has the random chunk information, too.

It will be very easy to find a collision since your truncated hash contains only $2$-byte $= 16$-bit. By the birthday attack on hash functions, the attacker only needs to try $\sqrt{2^{16}}= 2^8 = 256$ different files to has a collision with 50% probability.

You can also see this questions and answers for truncated hash values;

What are the consequences of removing a single byte from a sha256 hash?
Is truncating a SHA512 hash to the first 160 bits as secure as using SHA1?


Are there any practical methods of steganography?

The International Journal of Soft Computing and Engineering has published many articles on the subject.

If you want to move away from simple bit-twiddling in lossless images, take a look at spread-spectrum techniques for images and audio files.

There are plenty of tools available for hiding data in compressed images and audio (e.g., Steghide, JPHide and Outguess). However, it is often possible to detect when they have been used (e.g., using neural networks).


There is a misconception here regarding the security of MACs. It is certainly not true that MACs give away the secret key if it is known and the key reused. You are thinking about information-theoretic MACs (or possibly GHASH). However, a secure MAC does not have any problem at all. You can use HMAC or CMAC or even GMAC, and these are secure for many MACs even if the adversary sees many pairs of message/tag (and even if the adversary can choose what messages to get MACed). So, in answer to your question:

It is impossible to have an (almost) pseudorandom permutation without a secret key. You can heuristically use a hash function as a random oracle, but this opens up another big discussion
You do not need such an object for what you want. Just use a normal secure MAC and it is safe.