Is E_k(M)||H(m) form of MAC secure? Would this encryption and signing scenario be considered tamper-proof?
plaintext = "hello world"
password = "secret key"
hash = sha3_512(plaintext)
ciphertext = encrypt(plaintext,password)
output = ciphertext+hash

I'm computing the hash of the plaintext and then adding it to the end of the ciphertext output. I know this isn't exactly MAC or HMAC, but does this scenario work? Is it secure? From my perspective, the only way to forge the plaintext is if you know the key. Otherwise, any change will be reflected in the hash. Is this secure? Assume that the cipher is non-malleable. I believe this is the scheme used by Mcrypt for file encryption. Thanks.
This is not a duplicate because it would be infeasible to brute-force the plaintext from the hash as described in the possible duplicate question, scenario 3.

The point (( also see this answer)) is that the hash calculation is free for everybody and we assume that your methodology is known by Kerckhoffs's principles. Anybody can calculate the hash of any information and this may leak the encrypted message.
In Cryptography, we consider the attackers computationally bounded, but not restricted to adapt any method on their advantage.
If the possible attacker one of the three-word agencies, that we can assume that they collect all public information, where available, including your personal information, your networks, your habits, etc. Then they can keep the hash of each information on their humongous database ( like the Utah Data Center ) and once they see a message is transmitted with $E_k(m)||H(m)$ then they will check the existence of the $H(m)$. A hit today will reveal the message you send. They will not stop here if they fail. They will store this message and regularly will check the hash with the updated database.
Therefore this is not a good way to authenticate the messages. In modern cryptography, we have Authenticated Encryption (AE) modes like AES-GCM and ChaCha20-Poly1305 that provide confidentiality, integrity, and authentication in a bundle. Remember nothing is perfect and keep the obligations like for AES-GCM to be secure.


TOTP intermittently does not return the same code when generated within the same time step So we have the need for using a TOTP to generate a code on the server to send to a mobile client, I have been testing code generation with the following 3 java repos:

https://github.com/jchambers/java-otp
https://github.com/andOTP/andOTP
https://github.com/freeotp/freeotp-android

I've taken the core TOTP generating code and I've been testing them. My issue is that I will run the arbitrary mvn unit test where using the default time step of 30 secs, I will generate a token (t0), wait 2 seconds, and generate another token (t1) and sometimes (like 1 of every 10 tries) t0 != t1. I can't figure out why this is and my math-fu is not at the level to fully grasp whether this is expected or whether I am doing something wrong.

Note that this happens for all the 3 code sources (i haven't changed the code except for providing the secret key) I mentioned above - clearly either i'm doing something wrong or this behavior is possibly expected?!

If the time step is 30 seconds, there is a 2/30 = 1/15 probability that your starting time will be a different time step from the ending time two seconds later.


Proper way of doing encryption and authentication (PBKDF2 + AES) I'm currently in the planning phase of an authentication and storage-ish service.

The client needs a file ("ENCFILE") which he will work with. This file will be encrypted with AES256, and stored on the server.

In order to authenticate and download the file, and decrypt it, the user will need:

A username
A password

The server must never have access to the password, since it will also be used to decrypt "ENCFILE" stored on the server, yet, the user must still be able to authenticate to the server somehow.

In order to decrypt the file, the client will need an IV, the AES256 key, and some HMAC-bits. So, that should be doable with a regular PBKDF2 SHA512 I guess.. (256 bits for AES, 96 bits for IV and 160 for SHA1 HMAC). Username for salt should be good? Then all things can be generated client-side.

Suggested solution for authentication to the server? SRP? But without risking the server to know/lower the security of the key for AES, so.. how to generate the shared secret? PBKDF2 in some other way/salt?

PBKDF2 can produce output of arbitrary length. With HMAC/SHA-512 it does so in 512-bit chunks, but it is not restricted to 512 bits. If you need more bits then you can have more.

If you want to use the same password for authentication and for encryption, then the proper way is to "isolate" them from each other. I suggest the following: for the user password and salt (salt is on the server, and sent back when any client asks for it), the client computes PBKDF2 and obtains at least 256 bits. The first 128 bits will be used for authentication; the other 128 bits for encryption. Presumably, knowing the first half of the PBKDF2 yields no clue about the second half, and vice versa, except if the source password is guessed through exhaustive search (we are expecting PBKDF2 to behave like a Pseudorandom Function Family, the salt selecting the function in the PRF).

For authentication, use SRP indeed. For encryption, use GCM or EAX. GCM and EAX are nice encryption modes for AES (or other block ciphers, but primarily AES) which handle both symmetric encryption and a MAC, and can do so with relaxed requirements on the IV: these modes just need a non-repeating IV, not necessarily a random IV. You don't have to derive the IV from the password, and indeed you should not do it in case you want to encrypt several files with the same password, because then all the files will get the same IV, which is known to be a problem. Just encode the IV (counter, random... whatever floats your boat, depending on the encryption mode) in the file header.

It is not scientifically needed to use more than 128 bits for encryption or for authentication. Some people find psychological comfort in having huge keys, though.

It shall be noted that since the client first requires the salt from the server, an attacker impersonating the server could feed the client with a fake salt. Forcing the client to use a specific salt might allow for precomputations (aka "rainbow tables"). However, the SRP protocol ends with a pair of verification messages which validate that "everything went well" (when using SRP with TLS, the TLS Finished messages play that role). In the envisioned case, these messages not only guarantee to the client that it talked to the expected server, but also that the salt value was the right one, not one provided by an attacker.


Good enough deterministic PRNG based on hashes Lets say I have a seed named iv which has a decent amount of entropy.

Are there any glaring issues with the following?

First 64 bytes are generated by SHA512(iv)
Next 64 bytes are generated by HMAC_SHA512(iv, Previous64Bytes)
and so on...

Obviously if I needed "perfect" security I could use something like HMAC-DRBG (NIST SP 800-90), but I need something that's good enough, easy to implement and I do not care if a supercomputer breaks it in 10 years.

Edit - More info:

This will not be used to generate more than 500 bytes of data per run
The implementation will be out in the open (javascript)
Speed of the algorithm doesn't matter

A deterministic PRNG is pretty much the same thing as a stream cipher. So you could go with AES-CTR or AES-OFB where available. They're standard, and are much faster than all these HMAC-SHA-512 based constructions.

But if you really want to use a hash, then I'd go with the similar HKDF construction:

Extraction Step:

PRK = HMAC-SHA512("", seed)

Expansion step:

T(0) = empty string (zero length)
T(1) = HMAC-Hash(PRK, T(0) | info | 0x01)
T(2) = HMAC-Hash(PRK, T(1) | info | 0x02)
T(3) = HMAC-Hash(PRK, T(2) | info | 0x03)

Where info is some string describing the purpose of your output(can be empty if you don't use a single PRK for more than one purpose), and you output T(0) | T(1) | T(2) | ...

The standard HKDF only uses a single byte, but if you need longer output, you could use a larger counter, such as a four byte integer.

With your construction, using plain SHA-512 for the first step, and HMAC-SHA-512 for the other steps is problematic. In particular if the seed is longer than 128 bytes it becomes totally insecure. Use HMAC for all steps.

If you use HMAC for every step, your construction essentially becomes OFB mode, except that you use a keyed hash instead of a block cipher.


Detection of weak keys for AES-GCM There are many papers out there that show that a message authenticated and encrypted by AES-GCM can be forged if the used key is weak (e.g. by Handschuh and Preneel, Saarinen or Procter and Cid). With weak keys I refer to the definition given by Handschuh and Preneel:

  In symmetric cryptology, a class of keys [D] is called a weak key class
  if for the members of that class the algorithm behaves in an unexpected way and if it is easy to detect whether a particular unknown key belongs to this class. For a MAC algorithm, the unexpected behavior  can  be  that the  forgery  probability  for  this  key  is  substantially  larger  than average.

All these papers give suggestions how to avoid weak keys or how to minimize the class of weak keys. However, none of these suggestions have been accepted in the NIST standard. The standard is obviously older than the papers about weak keys, yet AES-GCM is still one of the most accepted algorithms.

Thus, I would like to know if famous applications like TLS or IPSec have implemented a weak keys detection or how do they avoid weak keys? Or is the probability to get a weak key (assumed that one is using secure random number generators) still so so small that the existence of weak keys is negligible?

However, none of these suggestions have been accepted in the NIST standard.

The suggestions are to use a different group. Those are not changes that could be done to the standard without complete loss of compatibility. They are things to consider when designing and choosing new algorithms, however.

  Or is the probability to get a weak key (assumed that one is using secure random number generators) still so so small that the existence of weak keys is negligible?

Yes. From Saarinen's risk analysis:

  The probability of randomly hitting an exploitable weak key with a real-world AES-GCM cryptographic protocol such as SSH [4], IPSec [6] or TLS [12] is vanishingly small.

No protocol that I know of uses GCM with a 64-bit cipher (like 3DES or Blowfish), which Saarinen calls out as risky and recommends against.


Representing Ed25519 p curve in hexadecimal byte string I am interested in representing p = 2^255 - 19 in the Ed255519 curve as hexadecimal byte representation.

When I was looking through the original NaCL source code written by DJB, I saw a code fragment that says:

static const unsigned int minusp[32] = {
 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128
} ;

Am I safe to assume that this is the 32 byte integer representation of p = 2^255 - 19  and all I need to do is translate the 32 byte integers into 32 byte hexadecimal string representation ?

How should I represent the p for Ed25519 in hexadecimal string ?

The constant is named minusp, thus it's $-p \pmod {2^{256}}$, or $2^{255} + 19$, encoded in little-endian.

Assuming you want the hex string in big-endian, which is the way numbers are usually written, you get:

$p = 2^{255}-19$ = 7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED

$2^{256} - p = 2^{255}+19$ = 8000000000000000000000000000000000000000000000000000000000000013


How does a company like Apple keep its keys safe? Whatever key is used to sign new iOS updates (for example) must be incredibly well-protected. How does a huge corporation like Apple keep those 4096 bits safe?!

Same goes for SSL keys for websites like Facebook or Google -- a compromised key means trouble for millions of users, but at some point the key must be decrypted and used for a signature.

It is important and interesting to notice the different use cases you mention. You don't have millions of software updates you have to sign every day (or second for that matter). For SSL connections, however, you may have millions per second. Given the two use cases, it makes sense that the way you would protect the keys would be different.

We don't know (AFAIK) how apple protects their OS signing keys. But, one good way to do it would be to store them on a separate computer that is locked in a highly secure room and not connected to any network. Only a few select people have access to that room. When a new OS version comes out, you take it into that room on a USB drive (or something like that). Signing the software requires two or more passphrases to unlock the private signing key. That way no single person can do this by themselves. Once two people have entered their passphrases, the private key is decrypted, used to sign the new OS updates, then wiped from the machine.

For the SSL use case, that private key has to be used millions of times per second. It is a very different use case. At this point you must rely on the security of the software (hopefully no one can exploit services running on your system), OS provided protections (making the private key only readable to the users/groups that need it), etc. You can also use hardware to help. Things like hardware security modules. These systems store the private keys in hardware and only provide a well defined cryptographic interface to them. That way if an attacker breaks into the machine, they cannot extract the private key. These may be useful in both use cases, but I would argue that they are more useful in the SSL use case.


Could someone reuse client certificates? To my understanding, if a server “cert+key” (RSA) is compromised, than the SSL/TLS network traffic can be decrypted.

What about a client “cert+key” (RSA)? Could someone reuse client certificates?

For example: can somebody with the client “cert+key” decrypt (or in otherwise mess with) the traffic of another user?  (Yes, I know they can impersonate but that is not my question.)

If you use public key crypto in the correct way, then every user has it's own private key and corresponding public key (included in the certificate) and the keys of users are not related. Consequently, compromising the private key of one user does not affect any of the other users. So in the case of compromise of the private key of one user the remaining users are safe.

There are examples where you would run into problems, e.g., if using common modulus for RSA - but if the user's private keys are generated correctly, i.e., independently with independent and good randomness - as it should be done in practice - then there will be no problem. It is, however, known that bad randomness is partially used in practice, e.g., resulting in RSA moduli that share at least a prime factor. You can find more information for example here or another example here.

Clearly, if you use public key crypto in the wrong way and give a private key to several users, then you will have this problem or if you use bad randomness you may also run into these problems. But you should not do that!!


Unpacking the definition of negligible & non-negligible There are several threads on this topic including:

How is an epsilon of 1/1000 non-negligible?

How to calculate if probability is negligible or not

(and others)

but I do not fully understand the answers in those threads.

My question is:

I would like to see what the definition of negligible & non-negligible means in an intuitive sense and unpack the definitions and use an example to see how the definitions apply.

The definition I am using is:

$\epsilon$ is a function $\epsilon$: $Z^{+}$ $\rightarrow$ $R^{+}$ and

$\epsilon$ is non-neg: $\exists$d: $\epsilon$($\lambda$) $\geq$ 1/$\lambda^{d}$ inf often ($\epsilon$ $\geq$ 1/polynomials, for many $\lambda$)

$\epsilon$ is neg: $\forall$d, $\lambda \geq \lambda_{d}$: $\epsilon$($\lambda$) $\leq$ 1/$\lambda^{d}$ inf often ($\epsilon$ $\leq$ 1/polynomials, for large $\lambda$)

Several questions:

What do these definitions mean in an "intuitive" sense?
What does $\epsilon$, $\lambda$, d, $\lambda^d$ mean?
How can you use these definitions to show that $\epsilon$:($\lambda$)=1/$2^{\lambda}$ is negligible and $\epsilon$($\lambda$)=1/$\lambda^{1000}$ is non-negligible?

(I know one of these examples is shown in another thread but I do not understand their solution and I want to see what each piece in the definition means in 'english' and then see how the definition is applied to each of these examples to show that they are negligible and non-negligible. I am hoping someone can provide a fresh explanation to the definitions and show how the definitions are applied to these problems and problems in general.)

Thanks!

As @SEJPEM mentioned in the comment: intuitively, for every positive
polynomial $p(n)$ ($n\in\mathbb{N}$) that you take, consider the function $q(n)=\frac{1}{p(n)}$, then we say that the function $\epsilon(n)$ is negligible if from some point $N\in\mathbb{N}$ it follows that $\epsilon(n)<q(n)$. This means that $\epsilon(n)$ reaches 0 very fast because it doesn't matter whether you take $p_1(n)=n$ or $p_2(n)=n^{100000}$, by the definition there would be $N_1$ from which $\epsilon(n)<\frac{1}{n}$ and $N_2$ from which $\epsilon(n)<\frac{1}{n^{100000}}$.

Now, to interpret the definition that you copied: $\lambda_d\in\mathbb{N}$ refers to $N$ in my explanation above, then the definition of negligible function requires that for every $\lambda\in\mathbb{N}$ such that $\lambda>\lambda_d$ (in my explanation above: for all $n$ that is bigger than this $N$) it follows that $\epsilon(\lambda)<q_d(\lambda)=\frac{1}{p_d(\lambda)}=\lambda^d$.

In order to show that $\epsilon(\lambda)=\frac{1}{2^\lambda}$ is negligible you need to show that for every polynomial $p(\lambda)$ it follows that $\epsilon(\lambda)=\frac{1}{2^\lambda}<q(\lambda)=\frac{1}{p(\lambda)}$ from some point $N\in\mathbb{N}$ (this point could be different for different $p(\lambda)$-s. Now take some arbitrary $p(\lambda)$, we can discover this $N$ from which $\epsilon(\lambda)<\frac{1}{p(\lambda)}$ as follows: let $p(\lambda)=\lambda^k$ then we want to find $\lambda$ such that $\frac{1}{2^\lambda}<\frac{1}{\lambda^k}$, thus, we want to find $\lambda$ such that $\lambda^k<2^\lambda$, or in other words, we want to prove that from some $\lambda$ the term $2^\lambda$ is bigger than $\lambda^k$, and this can be proven using the definition of a limit (see this proof).

Now take $\epsilon(\lambda)=\frac{1}{\lambda^{1000}}$, in order to show that it is not negligible you need to show that there exists some polynomial $p(\lambda)$ that violates the definition. Take the polynomial $p(\lambda)=\lambda^{2000}$, there exist no $\lambda_{2000}$ (or $N$) from which $\epsilon(\lambda)=\frac{1}{\lambda^{1000}} < q(\lambda)=\frac{1}{p(\lambda)}=\frac{1}{\lambda^{2000}}$ (i.e. for every $\lambda\in\mathbb{N}$ that you take, it follows that $\epsilon(\lambda)>\frac{1}{p(\lambda)}$.

I hope that it helps.


What is the simplest post-quantum asymmetric cryptographic algorithm for key exchange? This question has been burning in the back of my head for the past few days, and a quick Google search doesn't yield any usable results.
As the title suggests: What is the easiest-to-understand post-quantum asymmetric cryptographic algorithm that currently exists (as of 10 May 2021) for key exchange?
To establish common ground, assume that I understand everything from Khan Academy's Math Syllabus. On top of that, assume that I have gone through all of the undergraduate courses for MIT's Electrical Engineering & Computer Science courses.

There is only one paper I know of which explains a post-quantum key exchange algorithm in such a way that a beginner could understand it, and that is for SIDH (Supersingular Isogeny Diffie-Hellman key exchange). The paper is called Supersingular isogeny key exchange for beginners.

Abstract. This is an informal tutorial on the supersingular isogeny Diffie-Hellman protocol aimed at non-isogenists.

If you don't care whether or not it is actually usable, then there's pqRSA which is essentially just regular RSA with (completely impractical) parameters that make it post-quantum secure.


When is an RNG a CSPRNG, a CSRNG, or a TRNG? In a recent answer to a question about CSPRNGs, it was stated that…

Nondeterministic algorithms where there is no such requirement, and ideally could be replaced by a true random generator. Example: operating system random generators, where the practical solution has been to compose a deterministic pseudorandom generator with a physical noise source, to yield output that is both nondeterministic and pseudorandom.

This got me thinking that this could potentially lead to further confusion due the terminologies used, so I decided to wrap this into a question to have a place to point people to…

Can an RNG which relies — among other things — on a non-deterministic physical noise source still be called "pseudo" random?
If, where do we draw the line between a CSPRNG and a CSRNG?
And where do we place a TRNG in this picture? Or is a CSRNG always a TRNG and vice versa, making every other (cryptographically secure) RNG a CSPRNG even when non-deterministic physical sources are part of the RNG?

EDIT
It would be nice if your answer would include some pointers to according references that underline your explanation(s). After all, a trustworthy reference can replace a thousand opinions and related discussions.

There seems to be a lot of confusing terminology here. Let me define everything to the best of my knowledge.

RNG: Some mechanism that produces random numbers.
CSRNG: An RNG that is safe for cryptographic use.
PRNG: An RNG that is a deterministic algorithm based off of a seed.
TRNG: An RNG that is based off of some unpredictable physical process.
CSPRNG: A PRNG that is safe for cryptographic use. (Assuming the seed is picked correctly)

I've never heard the term CSTRNG, but I could imagine it meaning a TRNG which is cryptographically secure. In general conversation, this is redundant because TRNGs are assumed to be cryptographically secure regardless. Even though it is not explicitly defined that way.

  Can an RNG which relies — among other things — on a non-deterministic physical noise source still be called "pseudo" random?

Depends how the noise source is used. If the source is used as a seed for a PRNG, then it is in fact pseudo, since most of the randomness is "made up" by the algorithm.

If every bit of output is influenced by a different bit of input, then it can be considered a TRNG.

  If, where do we draw the line between a CSPRNG and a CSRNG?

From my understanding, a CSPRNG is a subset of CSRNG.

CSRNG means Cryptographically Secure Random Number Generator. It may be pseudorandom, it may not. The only requirement is that it is safe for cryptographic use.

CSPRNG means Cryptographically Secure Pseudo Random Number Generator. This has the same requirements of a CSRNG (hence it being a subset), with the additional requirement that it be some sort of deterministic algorithm that accepts a seed.

  And where do we place a TRNG in this picture?

The best description I've ever heard of a TRNG is an RNG based off of physical noise that has a mathematical basis for how every bit is based off of a different part of said physical noise. (Paraphrasing)

  Or is a CSRNG always a TRNG and vice versa

I could trivially make a TRNG by recording my voice and using the bytes from the recording as randomness without any processing. That isn't cryptographically secure, making it a TRNG but not a CSRNG. This isn't common because a TRNG that isn't good for cryptography is a waste of money for the most part.

However, there are CSRNGs that are TRNGs (See: random.org).

They are separate categories with separate requirements. They do overlap, but they do not depend on each other.

  making every other RNG a CSPRNG even when non-deterministic physical sources are part of the RNG?

A PRNG with a seed derived from a TRNG is still a PRNG. This is actually how a lot of random entropy is generated quickly. It isn't efficient to generate megabytes of entropy using physical sources. (Have you ever tried generating a public/private key pair using /dev/random? It's harsh) It's usually done by using physical sources to seed a CSPRNG, which does the heavy lifting.

Also, there are a lot of RNGs that are not CSPRNGs. Xorshift, LFSR, ARC4Random (when it was based off of RC4), and Mersenne Twister to name a few. These algorithms have biases or other problems that render them bad for cryptograpic use. However, they still output numbers that seem random to the naked eye.


Secure communication between multiple peers on a public channel I am wondering how can I secure communications between multiple peers over a public channel, like an IRC channel.

With two peers it is easy - they exchange their encryption keys and decrypt the secret messages using their private keys, but how would this work with multiple peers without creating excessive duplication of messages?

Is there some way to encrypt a message that would be readable by multiple peers not sharing the same secret key?

Generate a symmetric key
Encrypt symmetric key using public keys of all recipients, and broadcast (or provide on request from a client)
Transmit all user messages encrypted under the symmetric key

This means you only have one copy of the message (but you do have lots of copies of the encrypted symmetric key).

Of course you need to solve the key distribution problem first, to ensure you're only encrypting the symmetric key using authenticated public keys.


Using HMAC as a nonce with AES-CTR encrypt-and-MAC Suppose I use the following encrypt-and-MAC construction:

$E(k_1, k_2, n, m) = E_\text{AES256-CTR}(k_1, n, m) \| \text{HMAC-SHA256}(k_2, m)$, where:
$k_1$ and $k_2$ are 256-bit keys
$n$ is a nonce
$m$ is an arbitrary-length message.

What security losses occur if I use the MAC as the nonce? (i.e. $n = \text{HMAC-SHA256}(k_2, m)$, but truncated to the appropriate length)  Are there any other disadvantages to this scheme compared with typical authenticated encryption, e.g. AES-GCM?
Clearly, this scheme is distinguishable under chosen plaintext attack, since the same plaintexts always encrypt to the same ciphertexts.  This is acceptable in my application, but I'm interested to know if there are other problems.

What you're describing is pretty similar to the SIV block cipher mode. It also uses a deterministic function of the message to derive the nonce for CTR encryption. Under some pretty widely accepted assumptions about HMAC-SHA256 this is a perfectly fine way of achieving deterministic authenticated encryption. It doesn't meet IND-CPA (as you pointed out) but if this is acceptable for your application, you should be fine.

Disadvantages are mostly in terms of efficiency. The mode you propose requires two passes of the plaintext to generate a ciphertext, but GCM only requires one. A mode like OCB also only requires one pass for authenticated encryption, but is parallelizable as well. The impact of this is, again, dependent on your application.


Why is a random component needed for ECDH key pair generation in Mbed TLS? Please forgive me if this is not the right place, however, I encountered this TLS implementation with a function that generates an ECDH key pair on an elliptic curve:
In addition to the private key and a point on the curve, the function also needs random inputs. Why and for what are the random variables required? Why isn't it just $Q=[d]G$?

It is used to implement countermeasures against side-channel attacks.
From the paper:

If f_rng is not NULL, it is used to implement countermeasures against side-channel attacks.

And

The RNG function, for blinding purposes. This may b(sic) NULL if blinding isn't needed.

See more in mbed API Documentation.

The modular inverse operation as implemented in Mbed TLS was previously vulnerable to a single-trace side channel attack. This allowed an attacker with access to precise enough timing and memory access information (typically an untrusted operating system attacking a secure enclave such as SGX or the TrustZone secure world) to fully recover an ECDSA private key after observing a number of signature operations.
To combat these sorts of attacks, we can employ blinding; we include random data in our computations, and while the end results is independent of the random value, the intermediate values are strongly dependent, and thus the correlations between the intermediate states and anything that the attacker wants (such as the private key) is much weaker.
For further information on blinding, see

Scalar Blinding on Elliptic Curves with Special
Structure by Scott Fluhrer. Section 2 specifically discusses and references various techniques.

The specific attack on Mbed TLS is detailed further in this paper,

From A to Z: Projective coordinates leakage in the wild by Aldaya et. al, in 2020.

as taken from the mbed security update

Side channel attack on ECDSA .

There is a somewhat related follow-up from the same authors

Side-channel attack on ECC key import and validation

Note PolarSSL was acquired by ARM Holdings in 2014 and As of the release of version 1.3.10, PolarSSL has been rebranded to Mbed TLS.


Storing private keys directly in a keyring Storing an RSA 2048-bit key directly in a keyring seems to work fine, and is advantageous because the application can be removed, broken, reinstalled and the key still works.

However, most apps seem to write out PCSS8 key files, and, instead, keep the random AES keys in the keyring for acccess.

Is there a good reason not to store the private keys directly in a properly encrypted user keyring?

Is there a good reason not to store the private keys directly in a properly encrypted user keyring?

maybe generic answers what are you looking are standardization and platform independence. When writing software, we (mostly) need to take care that it will eventually running on all platforms. PKCS#8 is widely accepted standard usable everywhere.

What can be important here is the context. Are the keys directly used by user (to decrypt/sign something) or by machine (service)?

When we consider the end-user context, I agree with Maarten's comment, IMHO the best option is to have the keys on hardware. (Any reasonable crypto-device is often exposed as PKCS#11). Otherwise there is no advantage of Keyring over other keystores (ok, it can be integrated with UI such as Gnome)

When using the keys from the services, PKCS#8 is well supported and widely accepted standard, so it works everywhere. And the private key may be encrypted, but the decryption key needs to be available somewere too for server side services.


Collision resistance of hash function built on modular exponentiation Consider the following hash function family for hashing integers:

$Gen(1^k)$: generate 2 $k$-bit primes p,q. Let $n = pq$. Choose random $y \rightarrow QR_n$ and output $n,y$.

$H_{(n,y)}(x) = y^x \bmod n$

My question is this hash function collision resistant if the RSA assumption holds?

sReduction to RSA
Let $\mathcal C\colon \mathbb Z \times \mathbb Z \to \mathbb Z \times \mathbb Z$ be a collision-finding oracle giving $(x, x') = \mathcal C(n, y)$ such that $x \ne x'$ and $y^x \equiv y^{x'} \pmod n$, with some probability $p$ given some distribution on RSA moduli $n$ and integers $y$.  For any positive odd $e$, define $\mathcal R_e\colon \mathbb Z \times \mathbb Z \to \mathbb Z$, a root-finding algorithm giving $m = \mathcal R_e(n, c)$ whenever  $\gcd(e, \lambda(n)) = 1$, which succeeds if $\mathcal R_e(n, m^e \bmod n) = m$, as follows:

If $c \in \{0,1\}$, return $c$.
If $\gcd(c, n)$ is a nontrivial factor of $n$, exploit it for ordinary RSA private-key computations and stop here.
Compute $(x, x') = \mathcal C(n, c)$ with $x \ne x'$, $c^x \equiv c^{x'} \pmod n$.  (If not, fail.)
Compute $\delta = (x - x')/e^i$ so that $\gcd(\delta, e) = 1$.  (I.e., divide off all factors of $e$.)
Compute $d \equiv e^{-1} \pmod \delta$ with the extended Euclidean algorithm.
Compute and yield $c^d \bmod n$.

Why does this work?
Let $c = m^e \bmod n$.  If $c$ is neither zero nor a nontrivial factor of $n$, then $c \in (\mathbb Z/n\mathbb Z)^\times$.  Since $c^x \equiv c^{x'} \pmod n$, we know $\operatorname{ord}_n c \mid x - x'$.  Further, since $\operatorname{ord}_n c \mid \lambda(n)$ and $\gcd(e, \lambda(n)) = 1$, we must have $\gcd(e, \operatorname{ord}_n c) = 1$, and thus $\operatorname{ord}_n c \mid \delta = (x - x')/e^i$.  Now $\gcd(e, \delta) = 1$, so that $e$ is invertible modulo $\delta$, with inverse $d$.  Since $ed \equiv 1 \pmod \delta$, we can conclude $\operatorname{ord}_n c \mid \delta \mid ed - 1$, i.e. $ed \equiv 1 \pmod{\operatorname{ord}_n c}$.  Thus $c \equiv c^{ed} \equiv (c^d)^e \pmod n$, and since $u \mapsto u^e \bmod n$ is a permutation of $\mathbb Z/n\mathbb Z$, $c^d \equiv m \pmod n$.  (Note that $d$ is not the inverse of $e$ modulo $\lambda(n)$, or even modulo the order of $m$: we may need to use a different $d$ for each ciphertext $c$.)
This root-finding algorithm $\mathcal R_e$ succeeds with the same probability as the collision-finding oracle $\mathcal C$, and handful of arithmetic: a GCD with $n$, a few divisions by $e$, an extended Euclidean algorithm, and a modular exponentiation.  If the collision-finding oracle works uniformly on all elements of $\mathbb Z/n\mathbb Z$, then the root-finding algorithm works uniformly to decrypt all RSA ciphertexts in $\mathbb Z/n\mathbb Z$.  But if it is restricted to quadratic residues, which appear with probability $(p + 1)(q + 1)/4pq$ in a uniform distribution on $\mathbb Z/n\mathbb Z$ for $n = pq$, then so is the root-finding algorithm.
So it's not clear to me why this is restricted to quadratic residues: the reduction works better if not restricted!
Reduction to factoring
Let's take a simpler case first.
Suppose for $n = pq$ that $p = 2p' + 1$ and $q = 2q' + 1$ are safe primes, i.e. $p'$ and $q'$ are prime too.  Then $\lambda(n) = 2p'q'$ for primes $p'$ and $q'$ nearly the size of $p$ and $q$, so the only possible orders modulo $n = pq$ are $$\{1,2,p',q',2p',2q',p'q',2p'q'\},$$ and for a quadratic residue $y$, the only possible orders of $y$ are $$\{1,p',q',p'q'\}.$$  Thus, except for $1$, the order of every quadratic residue is either $p' = (p - 1)/2$, $q' = (q - 1)/2$, or $p'q' = \lambda(n)/2 = \phi(n)/4$.  A collision $x \ne x'$ implies $\operatorname{ord}_n y \mid x - x'$.  As long as $(x - x')/\operatorname{ord}_n y$ is not too large, it is merely a small combinatorial search to factor $n$ from there.
But it's still not clear to me why you need the base $y$ to be a quadratic residue.  The combinatorial search is a little larger, but not much larger, if $y$ is an arbitrary element.  Indeed, for any modulus, as long as $y$ has large enough order, a collision is practically guaranteed to reveal factorization of $n$ either directly or via $\lambda(n)$.  Pick $y$ to attain the maximal order $\lambda(n)$, and factorization of $n$ from a collision $x \ne x'$ is even easier because $\lambda(n) \mid x - x'$, for any $p'$ and $q'$ whether prime or not.
Maybe picking maximal-order elements uniformly at random is not trivial in general—but quadratic residues never have maximal order, and when $p$ and $q$ are safe primes, any uniform random element works except with negligible probability ($\pm1$).
Related constructions
A nearly more general theorem was proven by Pointcheval (Thm. 4, p. 117) for any modulus $n$ where the prime factors of $p'$ and $q'$, and the order of $y$, all exceed $\alpha$—with the caveat that $y$ must be asymmetric, meaning that its order has opposite parity modulo $p$ and $q$, so it is not quite a generalization.  This leaves open the question of what the distribution of the order of $y$ or $y^2$ is under uniform random $y \in (\mathbb Z/n\mathbb Z)^\times$, and whether it is below $\alpha$ with negligible probability.
Shamir and Tauman proposed a similar collision-resistant hash function for a base $y$ of maximal order modulo a product of safe primes, although it is defined on $\mathbb Z/n\mathbb Z \times \mathbb Z/\lambda(n)\mathbb Z$ rather than on $\mathbb Z/\lambda(n)\mathbb Z$: specifically, it sends $$(m, r) \mapsto y^{2^{\lceil\lg\lambda(n)\rceil}m + r} \bmod n.$$
But none of these involves quadratic residues, and in two minutes of skimming I couldn't find any relevant literature that does involve quadratic residues, other than the seminal GMR signature scheme (paywall-free link) that works rather differently.
In an answer to an earlier related question on the difficulty of finding high-order elements, poncho concludes that an oracle to compute the order of an arbitrary element $y$ modulo $n$ is enough to factor $n$, by finding a nontrivial square root of unity using the odd part of the order of $y$.  But there is a gap in applying it here: if the order of $y$ is odd, as it must be if (e.g.) $p$ and $q$ are safe primes and $y$ is a quadratic residue, the attack doesn't work, because we cannot necessarily construct such an order-finding oracle from a collision oracle in case the collision oracle always returns $x$ and $x'$ differing by an odd integer.
(On the other hand: maybe it works to test, for $i = 0, 1, 2, \dots$ until you pass $2^i > n$, whether $z^{2^i (x - x')} \not\equiv \pm 1 \pmod n$ and $z^{2^{i+1} (x - x')} \equiv 1 \pmod n$, in which case you have a nontrivial square root of unity so that $n \mid (z^{2^i (x - x')} + 1)(z^{2^i (x - x')} - 1)$ from which $\gcd(n, z^{2^i (x - x')})$ recovers a nontrivial factor of $n$.)


Modifications of CBC-MAC I'm preparing myself to exam, but I have a lot of troubles with rigorous proofs. This post is very long, but this is because I remind here 2 long definitions.

  At the beginning I want to remind the definicion of CBC-MAC.

  Let $F$ be a pseudo-random function. We define the CBC-MAC as $(Gen,Mac,Vrfy)$ as follows:

  (a) $Gen$ on input $1^n$ outputs a key $(k_1,k_2) \in \lbrace 0,1 \rbrace^n \times \lbrace 0,1 \rbrace^n$ selected uniformly at random.

  (b) $Mac$ on input a key $(k_1,k_2) \in \lbrace 0,1 \rbrace^n \times \lbrace 0,1 \rbrace^n$ and message $m \in \lbrace 0,1 \rbrace^*$ does the following.

  It first unambiguously pads the message $m$ to $m^{pad}=m|1|0^l$, where $l \in \lbrace 0,\ldots,n-1 \rbrace$ and $||m^{pad}|| \equiv 0 \mod n$.
  Then it splits $m^{pad}$ into $r$ blocks of $n$-bit: $m^{pad}=m_1^{pad}|m_2^{pad}|\ldots|m_r^{pad}$.
  Let $t_0=0^n$. For $i=1,\ldots,r$, it computes $t_i=F_{k_1} \left( t_{i-1} \oplus m_i^{pad} \right)$.
  Mac outputs $F_{k_2}(t_r)$.

  (c) $Vrfy$ on input key $k_1,k_2 \in \lbrace 0,1 \rbrace^n$, a message $m \in \lbrace 0,1 \rbrace^*$ and tag $t \in \lbrace 0,1 \rbrace^n$ outputs $1$ if $Mac_{k_1,k_2}(m)=t$ and $0$ otherwise.

Now I have some exam from previous year, and I don't know at all how to prove this facts (and, it should be done in rigorous way).

  Consider the modification CBC-MAC' of the CBC-MAC where the algorithm $Mac'_{k_1,k_2}(m)$

  selects $t_0$ uniformly at random,
  computes $t_1, \ldots, t_r$ as in CBC-MAC,
  and outputs $\left( t_0,F_{k_2}(t_r) \right)$.

  The verification algorithm given tag $(t_0,s)$ performs the same computation as $Mac'_{k_1,k_2}(m)$ using the given value $t_0$ and outputs $1$ if $s=F_{k_2}(t_r)$ and $0$ otherwise.

  1) Prove that CBC-MAC' is not strongly existentially unforgeable under an adaptive chosen-message attack (definition is below this exercise).

  Consider the simplification CBC-MAC'' of the CBC-MAC where the algorithm $Mac''_{k_1,k_2}(m)$ outputs $t_r$ instead of $F_{k_2}(t_r)$.

  2) Prove that CBC-MAC'' is not strongly existentially unforgeable under an adaptive chosen-message attack.

  3) Is there a condition on the message space of CBC-MAC'' such that your proof does not hold? Explain your answer.

Reminder:

  An efficient MAC is strongly existentially unforgeable under an adaptive chosen-message attack if for all PPT adversaries $\mathcal{A}$ it holds that $Pr[MACforge_{\mathcal{A}}(n)=1]$ is negligible function, where $MACforge_{\mathcal{A}}(n)$ denotes the outcome of the following experiment:

  (a) A key $k \leftarrow Gen(1^n) \in \lbrace 0,1 \rbrace^n$ is generated.

  (b) The adversary $\mathcal{A}$ is given oracle access to $Mac_k(\cdot)$ and outputs a pair $(m,t)$. Formally: $(m,t) \leftarrow \mathcal{A}^{Mac_k(\cdot)}(1^n)$. Let $Q$ denote the set of query/response-pairs $(m',t')$ for all the queries $m'$ asked by $\mathcal{A}$ during its execution.

  (c) The output of the experiment is $1$ if and only if $(m,t) \not\in Q$ and $Vrfy_k(m,t)=1$.

If you could help me with the rigorous proof, I'd be really grateful for your time.

Thanks, Ben.

1) The adversary queries the oracle (with some randomly chosen message $m$) and gets as a result a message $m=m_1|m_2|...$ and its tag $t=(t_0,F_{k_2}(t_r))$. She then draws $\rho$ uniformly at random in $\{0,1\}^n$ and outputs the message $m=\rho\oplus m_1|m_2|...$ and its (valid) tag $t=(\rho\oplus t_0,F_{k_2}(t_r))$.

2) The adversary queries the oracle (with some randomly chosen message $M$) and gets as a result the padded message $M|1|0^l$ and its tag $t=t_r$. She then queries the oracle with the message $t_r$ and gets the corresponding tag $T$.  She eventually outputs the (unpadded) message $M|1|0^l|0^n$ and its valid tag $T$.

3) The message space consists of the set of $\{\mbox{bit_length}(S)|S\}$ where S runs through all possible bit strings of length less than $2^n$.


Name for a Ceasar Cipher that uses random offsets? In a traditional Ceasar Cipher, you pick a specific offset such as "plus three" so that to encrypt each character of a message you count three letters up from the input and to decrypt you count three letters down from the input. For example, "APPLE" would become "DSSOH" where D is A+3, S is P+3, and so on.

I saw a variant of this where the key is used as the seed of a random number generator instead of a constant offset, and those random offsets are then used to encode the message. This has the advantage that the same input characters are not mapped to the same output characters. For example, my RNG might generate a sequence of 3 7 5 0 2, so then "APPLE" would become "DWULG" where D is A+3, W is P+7, U is P+5, etc.

Since the random number generator is deterministic, you can re-seed the RNG with the original key and generate the same random sequence to decode.

Is there a specific name for this type of cipher?

In short, it is a stream cipher.

The security of the random number generator is crucial in this design. Also, the key exchange ( the seed transfer) is not defined. To be good use Diffie-Hellman Key exchange and use a KDF to derive the seed.

Modern design is AES in CTR mode where the CTR mode of operation turns a block cipher into a stream cipher and that doesn't require padding. The better use the AES-GCM that provides Confidentiality, Integrity, and Authentication. Another one is ChaCha stream cipher and in Authenticated mode it is ChaCha20-Poly1305.


Blum primes [x=3(mod 4)] zero knowledge proof? Lets say we have 2 primes, $p \equiv q \equiv 3 \pmod{4}$, and we make $n=p \times q$ public.

I can, without revealing factors, show that $n$ has two prime factors. How can i zero knowledge prove that those are Blum primes, as described before?

I believe a zero knowledge proof that $-1$ is a quadratric nonresidue would accomplish that.

If we know that $n$ has two prime factors, and that $n \equiv 1 \pmod{4}$, then $n$ is either a product of two primes both $1 \bmod 4$, or two primes both $3 \bmod 4$.

If it were the former, then $-1$ is a QR modulo $p$, and $-1$ is a QR modulo $q$, and hence $-1$ is a QR modulo $pq$.

On the other hand, if $p \equiv 3 \bmod 4$, and $-1$ is a QNR modulo $p$, and hence a QNR modulo $pq$.

As for how to implement a zero knowledge proof that $-1$ is a QNR, see this paper


Impacts of not using RSA exponent of 65537 This RFC says the RSA Exponent should be 65537.  Why is that number recommended and what are the theoretical and practical impacts & risks of making that number higher or lower?

What are the impacts of making that value a non-Fermat number, or simply non prime?

Using $e\ne65537$ would reduce compatibility with existing hardware or software, and break conformance to some standards or prescriptions of security authorities. Any higher $e$ would make the public RSA operation (used for encryption, or signature verification) slower. Some lower $e$, in particular $e=3$, would make that operation appreciably faster (up to 8.5 times). If using a proper padding scheme, the choice of $e$ is not known to make a security difference; but for many less than perfect padding schemes that have been (or are still) used, high values of $e$ (compared to the number of bits in the public modulus $n$) are generally safer.

$e=65537$ is a common compromise between being high, and increasing the cost of raising to the $e$-th power: any higher odd $e$ cost at least one more multiplication (or squaring), which is true for odd exponents of the form $2^k+1$. Also, $e=65537$ is prime, which slightly simplify generating a prime $p$ suitable as RSA modulus, implying $\gcd(p-1,e)=1$, which reduce to $p\not\equiv 1\pmod e$ for prime $e$. Only the Fermat primes $3,5,17,257,65537$ have both properties, and all are common choices of $e$. It is conjectured that there are no other Fermat prime; and if there was any, it would we unusably huge.

Using $e=65537$ (or higher) in RSA is an extra precaution against a variety of attacks that are possible when bad message padding is used; these attacks tend to be more likely or devastating with much smaller $e$. Using $e=3$ would otherwise be attractive, since raising to the power $e=3$ cost 1 squaring and 1 multiplication, to be compared to 16 squaring and 1 multiplication when raising to the power $e=65537=2^{16}+1$.

For example, RSA with $e=65537$ has a security advantage over $e=3$ when:

Sending a message naively encrypted as $\mathtt{ciphertext}=\mathtt{plaintext}^e\bmod n$; the greater $e$ makes it more likely that $\log_2(\mathtt{plaintext})\gg \log_2(n)/e$ (which is necessary for security).
Sending the same message encrypted to $k$ recipients using the same padding (including any deterministic padding independent of $n$); the greater $e$ makes it less likely that $k\ge e$  (which allows a break).
Signing messages chosen by the adversary with a bad signature scheme. For example, with the scheme of the (withdrawn) ISO/IEC 9796 standard (described in HAC section 11.3.5), the adversary could obtain a forged signature from only 1 legitimate signature if $e=3$, but needs 3 legitimate signatures for $e=65537$; trust me on that one. The security advantage of $e=65537$ is wider for attacks against scheme 1 of the (current) ISO/IEC 9796-2.

For more explanations and examples of the risk of the combination of questionable message padding and low $e$, see section 4 in Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem.

There is no known technical imperative not to use $e=3$ when using a sound message padding scheme, such as RSAES-OAEP or RSASSA-PSS from PKCS#1, or scheme 2 or 3 from ISO/IEC 9796-2. However, it still makes sense to use $e=65537$:

The only known drawbacks are the performance loss (by a factor like 8), and the risk of leaving a bug in the key generator when a prime $p\equiv 1\pmod{65537}$ is hit; and when performance matters, there is an even better choice than $e=3$, with provable security (but more complex and uncommon).
Some attacks on less than perfect RSA schemes that are (or have been) in wide use are significantly harder than with $e=3$ (as discussed above).
$e=65537$ has become an industry standard (I have yet to find any RSA hardware of software that does not allow it), and is prescribed by some certification authorities.


Can I prove my app uses randomness right way? We are developing an iOS app which employs Shamir Secret Sharing algorithm. We made all possible steps users can trust us. We can't remember their secrets nor we can save encoded fragments. But they still may not trust us with randomness. Is there any cryptographic method how user can verify we are using random number generator honestly and have no malicious interests?

Nothing you show the user within the app could prove that the numbers were truly generated randomly and that the numbers weren't leaked maliciously or accidentally.

In general, you could make your application (or the module that does the cryptography, assuming it's built into a separate binary like a library or an executable used by the main app) open source and use a reproducible/deterministic build process so that users can compile the source themselves and verify that it matches what they've installed. I'm not sure how feasible or convenient this may be on the iOS ecosystem though. (Users might need a rooted phone to be able to view the app's binary installed from the app store, etc.)


How does GCM/GMAC work? My question is simple: where is a good article to learn how GCM/GMAC works?
I mean not the description of the algorihm, but why this pair of algorithms for encryption/decryption is really inverse. For me it is not obvous, why encryption of (A+P) --> (C+T) followed by decyption gives again P and the same Tag T...

For me it is not obvous, why encryption of (A+P) --> (C+T) followed by decyption gives again P and the same Tag T...

Actually, the reason both sides get the same T is quite simple; GCM defines the tag as a function of the key, the nonce, the AAD (additional associated data) and the ciphertext.  This function happens to be something along the lines of "form a polynomial in $GF(2^{128})$ from the AAD and the ciphertext, evaluate that polynomial on a value $H$ which is a function of the key, and then add in an encryption of the nonce", however the details really aren't important for this question; what's important is that it is a determanistic function of those four things and nothing else.

When the encryptor produces the ciphertext, he computes this function (using his copy of the key, nonce and AAD), generating the tag.

When the decryptor receives the ciphertext, he also computes the function.  If the ciphertext was the same (that is, not modified in transit), and the nonce, AAD and the keys are also the same, then he'll compute the same tag (as he does the same function with the same inputs).


Padding password before SHA-512 hashing to avoid info leak via timing I've noticed that SHA-512 password hashing leaks some information about
the password length. There's a weak correlation between password length
and time to hash. It's roughly linear, but in steps of 64 or so, and
also dependent on salt length. I suppose a little extra length results
in one extra block of hash input for each round.

To avoid leaking even this small amount of information, we could pad the
password to a constant length before hashing it. The padding could be a
reproducible secure hash of the password, salt, and/or number of rounds.

Since hashing the long padded password would take longer per round, we
could use fewer rounds. Thus, overall, the hashing operation would not
take longer (except for a little time to generate the padding).

(Of course, with the padding being a function of the password, one could
dispense with the password and simply hash the padding instead. That
seems risky, though; entropy might somehow be lost in the process.)

Does anyone see a problem with this padding idea? Do any attacks come to
mind?

Edit: this is for a working system, but the target environment makes
it difficult to use anything but Python and the standard library;
there's no compiler, and adding precompiled libraries is problematic.
Thus, crypt(3) is available, but better algorithms such as bcrypt,
scrypt, and PBKDF2 are not — at least, not easily.

The idea with the padding is to pad with a constant string, hash that
with a small number of rounds, and use the output as the padding for the
full number of rounds.

In general password hashing (algorithms such as bcrypt, PBKDF2) should contain a specific work factor. It might well be that repeating the hash multiple times will already obfuscate the hash time enough to make the padding redundant.

If you consider password hashing a requirement then reducing the number of rounds on the underlying compression function (e.g. the hash) doesn't make much sense as you would reduce the work load for both the regular user and an attacker.

For now assume that your passwords contain lots and lots of entropy so you may skip the issue of the work factor. In that case your scheme might be of some use.

You should however take really good care to avoid memory allocation issues.

Say an attacker could influence memory allocation. In that case asking for e.g. a block of memory of $c - l(p)$ bytes could be problematic (with $c$ being the total length of the input to the hash function and $l(p)$ being the password). In that case an attacker could guess a length $n$, and make sure only $n$ bytes are available within the memory page / cache block / whatever. Now the padding of $p$ would either allocate within the current page or it wouldn't. Page allocation / cache misses take a lot of time, so they can be relatively easily be detected. So the attacker has a method of checking if the password has a certain length.

You could work around this by copying the password into a preallocated block of memory. You then copy the required amount of pre-generated padding bytes after it.

  (Of course, with the padding being a function of the password, one could dispense with the password and simply hash the padding instead. That seems risky, though; entropy might somehow be lost in the process.)

Heh, no, the size of the password is rather less important than the content of the password. Unless you assume the padding to contain the entire password, but in that case you forgot to define your protocol well.

  and adding precompiled libraries is problematic.

So use the source code. I don't get it, is there an invisible man throwing up these invisible walls somewhere?


extract password hashed in scrypt using hash and salt I have the hashed password and its salt. It is encrypted using SCRYPT by firebase.

How can I extract the plain text password from these two?

Or alternatively, how can I re-encrypt or convert them to hash/salt that is readable by passport-local-mongoose plugin?
here is an example of what I have at my disposal:

  "hash": "jHyvk2qCPRncEAq5H05JeO4873MIMeyakVMmUXDjRfcdvflDvOXoEn7AhTW0T4f2zb24JYyPrIwTW96C4/iZ+A==",
  "salt": "zVzcUzIS+wCC+w=="

The whole point of a PBKDF like scrypt is that you can't. So that if somebody hacks the server and retrieves the hash and the salt they cannot reconstruct your password which you might have used on other sites.


Is HMAC-MD5 considered secure for authenticating encrypted data? I've read something to the effect that the HMAC construct is able to lessen the problem of collisions in the underlying hash.

Does that mean that something like HMAC-MD5 still might be considered safe for authenticating encrypted data?

Yes, there are currently no known attacks on HMAC-MD5.

In particular, after the first collision attacks on MD5, Mihir Bellare (one of the inventors of HMAC) came up with a new security proof for HMAC that doesn't require collision resistance:

  "Abstract: HMAC was proved by Bellare, Canetti and Krawczyk (1996) to be a PRF assuming that (1) the underlying compression function is a PRF, and (2) the iterated hash function is weakly collision-resistant. However, recent attacks show that assumption (2) is false for MD5 and SHA-1, removing the proof-based support for HMAC in these cases. This paper proves that HMAC is a PRF under the sole assumption that the compression function is a PRF. This recovers a proof based guarantee since no known attacks compromise the pseudorandomness of the compression function, and it also helps explain the resistance-to-attack that HMAC has shown even when implemented with hash functions whose (weak) collision resistance is compromised. We also show that an even weaker-than-PRF condition on the compression function, namely that it is a privacy-preserving MAC, suffices to establish HMAC is a secure MAC as long as the hash function meets the very weak requirement of being computationally almost universal, where again the value lies in the fact that known attacks do not invalidate the assumptions made."

However, this does not mean you should use HMAC-MD5 in new cryptosystem designs.  To paraphrase Bruce Schneier, "attacks only get better, never worse."  We already have practical collision attacks for MD5, showing that it does not meet its original security goals; it's possible that, any day now, someone might figure out a way to extend those into some new attack which would compromise the security of HMAC-MD5.  A much better choice would be to use HMAC with a hash function having no known attacks, such as SHA-2 or SHA-3.


How to start a classical cryptanalysis on a Substitution + Shift cipher? i was thinked about problem of Cyrpto.

At first glance, it looks like a simple classic password problem, but there are a lot of difficulties to think about the way the two encryption schemes are mixed.

The process is as follows.
First, create a substitution table for 26 alphabets.

Second, we select two key values for the shift cipher.

For example, the substitution table looks like this, and the key value of shift cipher is (3,7).

Original..  : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Substitution: N E O B F M D Q V P U A W R I K Y J C S Z L G T X H

Plain Text : "APPLE"

first, The letter corresponding to 'A' is N.

cipher : APPLE --> NPPLE

second, Shift key 3 shifts the shift table to the right, and then maps the table.

Original..  : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
shift table : T X H N E O B F M D Q V P U A W R I K Y J C S Z L G

cipher : APPLE --> NPPLE --> NWPLE

third, Shift key 7 shifts the shift table to the right, and then maps the table.

Original..  : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
shift table : Y J C S Z L G T X H N E O B F M D Q V P U A W R I K

cipher : APPLE --> NPPLE --> NWPLE --> NWMLE

forth, Shift key 3 shifts the shift table to the right, and then maps the table.

Original..  : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
shift table : R I K Y J C S Z L G T X H N E O B F M D Q V P U A W

cipher : APPLE --> NPPLE --> NWPLE --> NWMLE --> NWMXE

forth, Shift key 7 shifts the shift table to the right, and then maps the table.

Original..  : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
shift table : D Q V P U A W R I K Y J C S Z L G T X H N E O B F M

cipher : APPLE --> NPPLE --> NWPLE --> NWMLE --> NWMXE --> NWMXU

The resulting encrypted string is : 'APPLE' result cipher is 'NWMXU'.

I tried to use the matrix, and I tried to perform the frequency analysis after the offset calculation for 26 ^ 2 cases (676) because I thought that the shift range exceeded the rotation range of 26 is meaningless in the shift operation anyway.

However, it has never been solved easily. I would appreciate it if you could give me some advice.

Reminder: Analyzing schemes is off topic on crypto.SE. This question will therefore be likely to be closed soon.

Your scheme can be summarized by:
pick a S-box $\sigma$ and two keys $(k_1, k_2)$ and do:

for i in 0 .. len(message) do
  c[i] = σ(m[i])
  if i & 1:
    σ >>> k2
  else
    σ >>> k1
return c

This is broken by frequency analysis with a sufficiently long message:

Find $n$ such that $n \times (k_1 + k_2) \equiv 0 \pmod{26}$.
Remark that every $n \times (k_1 + k_2)$, a character you encrypted with the same key, thus frequency analysis will work.

Worth to be noted:

this is equivalent to a alphabetic Vigenère Cipher with a long key.
modern cryptanalysis (CPA & CCA) breaks this with a 26 chosen plaintext and 1 chosen ciphertext. See bellow.

Query messages:

AA B C D E F .. Z

$\alpha\beta$
These will give the $\sigma$ table.
Assuming that AA is encrypted by αβ query a decryption for the ciphertext: $xαβ$ (prepend a random character). Drop the first character decrypted, the following letters will correspond to the shift distances $k_1$ and $k_2$.

In your example, the query would be:
E(AA) = NT
and
D(XNT) = YDH
leading to
D $\implies k_1 = 3$,
H $\implies k_2 = 7$.


Any ideas on login using Digital Signature PKCS I am curious to know about possibility to login into web application just by identifying the user based on digital signature in usb token.

any reference in this direction?

Web application, using modern browsers, may access user's Certificate Store or USB Token or Smartcard (through Certificate Store using CSP in token driver) through Browser Extension.

Methods like java applets, Active X, etc are being phased out from the new Modern Browser offerings. Recently much is being talked about WebCrypto API but as of now, WebCrypto API does not provide access to (Windows) or any other Key stores or local crypto USB/Smartcard device.

For Authentication from Browser using Digital Signature, one such free Chrome extension available is Signer.Digital chrome extension. Local system (host running behind the chrome browser on windows) setup may be downloaded from https://download.cnet.com/Signer-Digital-Chrome-Extension/3000-33362_4-78042540.html
 Installing this host and restarting Chrome will automatically add Signer.Digital Chrome Extension

The actual working of this extension is illustrated here

Javascript to call method from extension:

To Register Certificate on Server:

//Get Selected Certificate Information
SignerDigital.getSelectedCertificate()
    .then(
        function (CertInfo) {
    //Success returns Certificate Subject and Thumbprint
        },
            function (errmsg) {
                //Send errmsg to server or display the result in browser.
              }
     );

To authenticate or Login using Digital Signature:

SignerDigital.signAuthToken(authToken, "SHA-256")       //or "SHA256"
    .then(
        function (SignData) {        //Success returns Signed Auth Token
        },
            function (errmsg) {
                //Send errmsg to server or display the result in browser.
              }
     );

To sign PDF:

    //Calculate Sign for the Hash by Calling function from Extension SignerDigital
    SignerDigital.signPdfHash(hash, $("#CertThumbPrint").val(), "SHA-256")      //or "SHA256"
     .then(
            function (signDataResp) {
              //Send signDataResp to Server
        },
            function (errmsg) {
                //Send errmsg to server or display the result in browser.
              }
     );

If Failed: returns error msg starting with "SDHost Error:"

Disclosure: I work for CISPL which offers Signer.Digital Browser Extension


problem similar to DLP I'm studying a protocol whose security is based on the following assumption: given $g_1, g_2, A, B \in \mathbb{F}_p ^*$ with $g_1, g_2, A \neq 1$ and $g_1 \neq g_2$ , it is difficult to find exponents $r_1,r_2, d$ s.t. the following equation holds:
$$
g_1^{r_1}g_2^{r_2} \equiv A^dB \ \ (\mbox{mod} \ p)
$$
The paper I'm reading states "this is a type of discrete logarithm problem, hence it is assumed hard to solve". I'm not sure why this last sentence is true: initially I thought I could show this problem was harder than the DLP by saying "if I could solve this problem for given $g_1, g_2, A, B$, in particular I could solve it for $g_2 = A = 1$, so I could solve $g_1^{r_1}=B$, which is a DLP". But my argument is fallacious as $g_2$ and $A$ are different from $1$ by hypothesis. I would really like to have some proof like the one I was trying to show, so that I can bring this problem back to the DLP hardness assumpion, and don't assume anything more.
If someone know about similar-discrete-log-problem or see any way to show this problem is harder than the DLP, please help me! Thank you in advance

The standard way to prove this problem is at least as hard as the DLP problem is to show that, with an Oracle that can solve this problem, you can solve the DLP problem.

Here's how to do that (and we'll assume that the Oracle will solve random instances with nontrivial probability):

Given the DH problem $G^x = H$, find $x$, we pick random values $s_1, s_2, s_3, s_4$, and form the problem:

$$(G^{s_1})^{r_1} \cdot (G^{s_2})^{r_2} = (G^{s_3})^d \cdot (H^{s_4})$$

This is a random instance, and so the Oracle gives us, with nontrivial probability, values $r_1, r_2, d$, and so we know that:

$$s_1r_1 + s_2r_2 \equiv s_3d + xs_4 \pmod{p-1}$$

We know everything other than $x$ in the above equation, we solve it, and our work is done


For an elliptic curve, what is the difference between the base field modulus $Q$ and subgroup $r$ What is the difference between the basefield modulus $Q$ and a subgroup of prime order $r$?

They are all fields, but what is their relevance to the curve they are defined upon?

How does this relate to a scalar field?

Also: Which field is the curve defined upon?

You are asking about a subset of Elliptic Curve (EC) domain parameters over $\mathbb{F}_p$ or $\mathbb{F}_{2^m}$

Domain parameters of Elliptic Curves over $\mathbb{F}_p$ is the sextuple:

$$T= (p,a,b,G,n,h)$$

The integer $p$ defines the field $\mathbb{F}_p$,
$a$ and $b$ defines the curve equation in Weierstrass form:
$$E: y^2 \equiv x^3 + a \cdot x + b \pmod{p}$$
$G=(x_g,y_g)$ defines the base point
a prime $n$ which is order of $G$
and an integer $h = \#E(\mathbb{F}_p)/n$

So, first choose an EC, then we choose a $G$ that generates a subgroup of order $n$.

  They are all fields, but what is their relevance to the curve they are defined upon?

EC is an Algebraic Group but it is defined over the Field $\mathbb{F}_p$

  How does this relate to a scalar field?

We have scalar (point) multiplication to represent the $k$ addition of a point $P$ by itself as $kP$.

  Which field is the curve defined upon?

Above $\mathbb{F}_p$, it can be also $\mathbb{F}_{2^m}$, but these are for general Cryptographic purposes. EC's can be defined over the Complex, too.


Public Keys on Social Media Is there any problem with using social media (i.e. Facebook) as a directory of public keys?

For example, couldn't Alice put a note containing $(g^a \bmod p, g, p)$ on her Facebook page so she could receive email attachments which have been encrypted with the common secret value?

That is, Bob would encrypt his message with the value obtained from $(g^a)^b \bmod p$ and send it along with in-the-clear $g^b \bmod p$ to Alice.  She then can decrypt the message.

If everyone were to publish their public keys, wouldn't this defeat most "man-in-the-middle" attacks?

This depends largely on the trustworthiness of Facebook and your assumptions about the model and attacker.

If Facebook is corrupted, they will just exchange your information to their address/public key and can still do a man-in-the-middle.
An external attacker could modify the profile pages while they are being transmitted to other users or in their browser, with the same result. In reality, this is easy when SSL is not used or when the person (viewing your profile) is infected by malware.
If your own computer/browser is compromised, the attacker will either know the according secret $a$ anyway or he can modify your profile update to a value of his choice.

In a more practical world, this could work... if people would use email encryption in general. There are mechanics like PGP or S/MIME, but they are not widely used due to not being comfortable. This is a general problem, but Facebook (or any other social media) would surely work as a place to publish your public key/certificate. But using such a public profile from Facebook from someone else requires a certain amount of trust in the plattform (that it is actually the information from the according user).

In your example you use an Diffie-Hellman key exchange with one fixed parameter, you might want to change that to an ElGamal encryption of a new random key for the symmetric encryption., as usual in hybrid encryption schemes.


Paillier Homomorphic encryption to calculate the means Paillier Homomorphic encryption supports addition and multiplication with plaintext value.

Can I use these properties to calculate the means of cipher-text values? I try to use the following steps:

Multiply set of cipher texts (to get there sum in plaintext value)
Raise the calculated ciphertext in step1 to the power of $\dfrac{1}{c}$ where $c$ is the number of cipher texts) to get the average

The problem I have is that, paillier is defined in integer domain $\mathbb{Z}$ thus $\dfrac{1}{c}$ is always $0$ so the final results is also $0$.

Any help or suggestion?

The Paillier encryption of an integer $x_i$ is given by $c_i = (1+x_iN)r_i^N \bmod N^2$ for some random $0<r_i<N$.  Given the encryption of $x_1, \dots, x_k$, the encrypted mean is defined as $$[\![\mu]\!] = \left(\prod_{i=1}^k c_i\right)^{k^{-1}\bmod N} r^N\bmod N^2$$
for some random $0<r<N$.

If we now apply Paillier decryption procedure to $[\![\mu]\!]$, we get $$\mu = \frac{\sum_{i=1}^k x_i}{k} \bmod N$$
We assume $\sum_{i=1}^k x_i< \sqrt{N}$. Now an application of Lagrange-Gauss lattice-reduction algorithm yields $\mu$ as an element in $\mathbb{Q}$.

Based on: [FSW02] Pierre-Alain Fouque, Jacques Stern, and Jan-Geert Wackers. Cryptocomputing with rationals. In Financial
Cryptography, volume 2357 of Lecture Notes in Computer Science, pages 136–146. Springer, 2002.

Alternatively, instead of using Lagrange-Gauss algorithm, we can adapt the extended Euclidean algorithm:

 [u1, u2] = [0, N]; [v1, v2] = [1, mu];
 while (u2 > sqrt(N)) do
   Q = u2 div v2; [t1, t2] = [u1, u2] - [v1, v2]*Q;
   [u1, u2] = [v1, v2]; [v1, v2] = [t1, t2];
 endwhile

 return u2/u1

Here is a toy example with $p = 739$, $q = 839$, and $N = pq = 620021$. Suppose $x_1 = 97$, $x_2 = 74$ and  $x_3 = 46$.

We are given their respective encryptions: $c_1 = 206197787317$, $c_2 = 267770082390$, and $c_3 = 49804921902$. We have $k=3$ and $k^{-1} \bmod N = 206674$. We choose a random $r<N$, say $r = 559196$ and compute $$[\![ \mu]\!] = (c_1c_2c_3)^{k^{-1}\bmod N} \, r^N \bmod N^2 = 127639014845$$

The decryption of $[\![\mu]\!]$ yields $\mu = 206746 \pmod N$.  Lagrange-Gauss algorithm then yields $206746 \equiv \frac{217}3 \pmod N$ and thus $\mu = 217/3 = 72.33$.


Why can't Diffie-Hellman be used for signing? I understand that signing is often a case of hashing data and then encrypting the hash with the private key. What properties keep Diffie-Hellman from being useful for this?

Actually the presentation of digital signatures as "encryption with the private key" is a misleading historical way of explaining RSA signatures; but it really works only for RSA. For such a scheme to work, you need the asymmetric encryption algorithm to be a trapdoor permutation, so that the space of encrypted messages is the same than the space of decrypted messages.

Most asymmetric encryption algorithms are not trapdoor permutations. This does not mean, however, that it is not possible to reuse parts of an asymmetric encryption algorithm to design a digital signature scheme.

Consider Diffie-Hellman. It is not an asymmetric encryption scheme; only a key exchange algorithm (a key exchange algorithm can be viewed as an asymmetric encryption algorithm in which you do not get to choose what is the encrypted message you send). From DH, we can build an asymmetric encryption scheme, and this is what ElGamal is about. An ElGamal public key is much similar to a DH public key: given fixed public parameters which describe a group $G$ of size $q$ and a generator $g$ of that group, the ElGamal private key is an integer $x$ (smaller than $q$) and the public key is $g^x$. To encrypt a message $m$ with the public key, the sender:

chooses a random $y$ modulo $q$;
computes $g^y$;
computes $s = (g^x)^y$;
sends $g^y$ and $m*s$ to the private key owner (this assumes that $m$ can be mapped to a group element, and back).

We recognize Diffie-Hellman in the first three steps: $s$ is the "shared secret" resulting from using DH with the public $g^x$. The fourth steps simply "encrypts" m by multiplying it with the shared secret.

Here, the private key is an integer modulo $q$ and the public key is an element of group $G$, which could be, e.g., an elliptic curve. You cannot swap them and try to encrypt with the private key: encryption needs a group element, not an integer modulo $q$.

Nevertheless, an ElGamal signature scheme has been designed, but it really does not look like Diffie-Hellman. It rather looks like a computational zero-knowledge proof of knowledge of the private key. With $G$ being non-zero integers modulo a prime $p$, signature works like this:

hash message $m$ into value $h$ which you map to an integer;
choose a random value $k$ relatively prime to $p-1$;
compute $r = g^k \mod p$;
compute $s = (h-xr)/k \mod (p-1)$. The signature is $(r, s)$.

To verify:

hash message $m$ into value $h$ which you map to an integer;
verify that $g^h = y^r r^s \mod p$.

So there are modular exponentiations in there, but nothing which is really "just Diffie-Hellman". ElGamal signatures are called such because Taher ElGamal described that algorithm, not because of any specific link with the ElGamal encryption scheme (which is also called ElGamal because it was also published by ElGamal).

Remark: with RSA, when you verify a signature, to process (exponentiate) the signature value with the public key, and this yields $H(m)$ (the hash of the message which is signed), which you them compare with the expected hash value. This does not work so with other signature algorithms, in which the hashed message is an input to the verification algorithm; you cannot recover the hashed message from the signature and the public key alone. RSA signatures are said to be signatures with recovery because you obtain the hashed message out of the signature; ElGamal signatures (and its offsprings DSA and ECDSA) are just "regular" digital signature schemes. Having the "recovery" feature is a byproduct of RSA being a trapdoor permutation.


How bad would it be to reuse the random blinding factor in a scheme like Paillier? A secure and somewhat fast way to "re-encrypt" (refresh? anonymise?) a Paillier ciphertext, $c$, is to multiply it by an exponentiated random value:

$c \gets c \cdot r^n \mod n^2$ (with $r \in \mathbb{Z}_n$ random)

However, that mod exponentiation of a large $r$ is quite costly (many orders more than the other operations involved). So, in cases where many successive re-encrypt would be necessary, it seems very tempting to store and reuse the same $s = r^n \mod n^2$.

Hence, after two re-encryptions, the cipher would contain:

$c \cdot s^2 \mod n^2$

and so on...

Such a re-encrypt method would only use multiplications and be vastly cheaper that the common method.

Since multiplication by $s$ "should" be large-enough to trigger a modulo wrap-around, it seems like successive $s^i$ values would not give any information about any of the previous $s^k, k < i$ (and thus preserve the security of all ciphertexts). Is this correct?

The weakness seems to be in the risk that one such multiplication would not trigger a wrap-around, but maybe a solution to that would be to keep multiplying until we are guaranteed one has occurred.

As a variant: we could use a small pool of such pre-calculated exponentiated random values for each re-encryption, thus ensuring the wrap-around always occurs.

Am I missing an obvious security flaw here?

The first obvious objection is that it would do a lousy job of blinding values; if you reuse the blinding factor, then it would be practical to correlate the blinded values with their original ones (and the entire point of blinding values is to prevent anyone from doing so).

Suppose we had two original encrypted values $c$, $d$, and the corresponded blinded versions $x = c \cdot r_1^n$ and $y = d \cdot r_2^n$.  Knowing nothing else, it would be infeasible to decide whether $x$ is a blinded copy of $c$, or a blinded copy of $d$.

However, if $r_1 = r_2 = r$, we can check if $c \cdot y = d \cdot x$.  If $x$ is a blinded version of $c$, and $y$ is a blinded version of $d$, then this check gives us $c \cdot d \cdot r^n = d \cdot c \cdot r^n$, or in other words, equality holds.

In addition, you ask:

  Since multiplication by $s$ "should" be large-enough to trigger a modulo wrap-around, it seems like successive $s^i$ values would not give any information about any of the previous $s^k,k<i$ (and thus preserve the security of all ciphertexts). Is this correct?

That is also not correct.  Given $c \cdot s^2$ and $c \cdot s$, the attacker can recover $c$ by computing:

$$(c \cdot s^2)^{-1} \cdot (c \cdot s)^2 = c$$

$(c \cdot s^2)^{-1}$ is the inverse of $c \cdot s^2$ modulo $n^2$, it can be computed as long as $c \cdot s^2$ is relatively prime to $n^2$


What can a master password also be called? When having a company computer that is full disk encrypted, it is common that the boss have a master password / backdoor, so the data always can be decrypted.

I have heard some call this for "scrow" or something similar.

Does anyone know the correct name?

I think the thing you are looking for is "escrow" as in http://en.wikipedia.org/wiki/Key_escrow.
Be aware though that the security of your system is reduced to the hardness for an attacker to find the master password which might be much easier than breaking the disk encryption scheme


How come Shamir Secret Sharing uses Lagrange interpolation? I've read that Newton polynomials have better computational complexity, but Shamir's uses Lagrange polynomials instead. Does anyone know if there are particular reason why Newton polynomials aren't used instead?

The purpose of the reconstruction of the polynomial $P(x)$, is just to calculate the value of $P(0)$, which equals the shared secret value.

If Lagrange polynomials are used, a trivial optimization which cuts the number of multiplication nearly in half is
$$P(0) = (\prod_{i=0}^{n-1}{-x_i})\sum_{i=0}^{n-1}{{\frac{y_i}{-x_i (\prod_{j=0,j\neq i}^{n-1}{(x_i-x_j)})}}}.$$

If Newton polynomials are used, there is no trivial optimization because you only want to calculate $P(0)$, simply because the formula is already optimized to half of $n^2$. This means that the overhead of the recursion might outweigh the general benefits compare to the Lagrange formula.

If you had had to represent the polynomial $P(x)$ in order to calculate other values than just $P(0)$, Newton polynomials would in general have been more efficient.


uniqueness of the RSA public modulus What is the probability that two separate RSA public moduli are the same? For example, consider a 2048-bit modulus. The number seems to be huge, but the choice for prime factors p and q is much more restrictive: They both should be 1024-bit in size, not too close to $\sqrt{p*q}$ and the most significant bit should remain set. Even if $2^{1023}$ seems like a lot of numbers, not every integer in this set suits the RSA scheme.
Since public exponent $e$ should be set to $0x010001$, if I find a collision for the RSA modulus, have I also found a collision for the RSA private exponent?
Is it possible to treat the public RSA components (e.g. represented as $H(modulus, exponent)$) as a unique value for identification purposes?

If the RSA keys were generated randomly, then it is inconceivable that two different devices would happen to pick the same key.

Taking 2048 bit RSA keys as an example, there are approximately $2^{1014}$ 1024 bit primes; if we consider them pairwise (and realise that about half the pairs yield a 2047 bit number), that means there are about $2^{2026}$ RSA modulii possible.

This is an incredibly huge number.  Even if we take into account the fact that the probability for generating each modulii isn't precisely the same (depending on the actual algorithm used), it'd be far more likely that you'd win the lottery 100 times in a row than two devices happen to pick the same RSA key.

On the other hand, examples of devices having the same RSA key have been seen.  In this case, the problem wasn't that someone won the lottery 100 times; instead, they got the random part wrong.

An essential part of the above argument is that we pick them randomly; that is, we start with a 'random' value, and we use that value to select two primes.  If two different devices start with the same 'random' value, and use the same algorithm to select the primes, they'll end up with the same RSA key.

So, to answer your question: whether you can assume that two different devices always have different keys, well, that depends on whether whoever did generate the keys had proper amounts of randomness (entropy) when doing so.  If they did, you can certainly assume it; if they're broken, any such assumption is suspect.


Why are RSA ciphertexts different for the same plaintext? I am using SpongyCastle for a project on android. I have used RSA to encrypt the data and then decrypt it in another activity, the keys are stored in the shared preferences.
I discovered a thing I cannot explain.
My keys are generated only once and stored for future use without being changed. On encrypting the same plain text, I get two different outputs.
I encrypted the plaintext a and got the following outputs :
"G4srxAxUnoikOIQdlj30rmyUiGz3P0R0VE6BflSTo4UQqJVSBpQtyFSB6tt73Z693D0LMkykDEPB
    lPg0IEH/R6tOJCyCU8HxKQ8nfo5OGUYFgkup3aGPkRqb+gCLpc5YGSmLztaynKq1H6kplryx0q1+
    KTCchc6PswAMpaMwMTk="

"j2r5MsaGRNazElAxG4BIBgZYtrjdxaErbs+19ObsCyOuVwTiu0cvKcKTOPuUOOjcGVaDup53wdEk
    AHHsy8zA1gR29uSdW4C2JIDnQVGCcfzqOcbzeS4WgV+2WpLTahBj6Df8pya2YksIp3KSLSnhH3nn
    B2kf/Wi53SQmJJWSf84="

"Yz3xhiObUI5C8UA31VNH3VqUXGmotGpTz9A3U2n81lJ7p1//x4CI15r4JUZGJlN1aPnSayIuk6D8
    hMIp32o53YEmm69gve91+dCVDQkZOUE9UuA2nEcjR21nUgWPQJdwqQ7P4XFeWsBaokpwNCA6j2qb
    b1Glfp+AVpUNm7syiUY="

...

I know that RSA is $Y = X^e \pmod{n}$
Since neither $X$ (plaintext) nor $e$ (public key) changes, I'm guessing $n$ changes each time.
The decryption works just fine for each case.
So, if $n$ changes each time, for decryption to know the value of $n$ it has to be passed on with the message itself.
My questions:
Am I correct in assuming the above? If yes, where is $n$, and what is the format for storing the message? If No, what is the correct method?
The output is 172 characters each time? How does that work out?
P.S. : I am following this.
Edit:
I can conclude that from the answers that padding is responsible for this. If padding is different each time, shouldn't it be mentioned or the length of the actual message be mentioned with the ciphertext so that deciphering code can differentiate the padding from the actual message? If it is the same, wouldn't it give the same result each time, we would still need to pass the length of the actual message encrypted as it may be. (I think it's random)
I also found out that I can't encrypt more than 86 characters. Why? Is there a limit on the number of characters by RSA?
Giving me this:
06-12 18:09:37.192    9217-9217/? E/AndroidRuntime﹕ FATAL EXCEPTION: main
Process: com.chatr, PID: 9217
java.lang.RuntimeException: java.lang.RuntimeException: java.lang.ArrayIndexOutOfBoundsException: too much data for RSA block
        at crypto.RSA.encryptWithKey(RSA.java:87)
        at crypto.RSA.encryptWithStoredKey(RSA.java:93)

Also, the same error comes when I try to decrypt the ciphertext when I replace = with something else, and obviously hash fails when I change some other character. What does = signify. I'm assuming padding.

Am I correct in assuming the above?

No you are not. You are showing textbook/raw RSA, which is little more than modular exponentiation. To be secure RSA has to use padding methods. Without padding, RSA would indeed generate the same ciphertext each time. This alone would break the security requirements of a cipher. There are many other attacks on textbook RSA. Fortunately the code you linked to specifies OAEP encryption, which is assumed to be secure.

  If yes, where is $n$ and what is the format for storing the message?

$n$ is not part of the ciphertext. It is however part of both the public key and the private key. The output format of RSA/OAEP is simply a byte array of the same size - in bytes - as the modulus, almost indistinguishable from random.
In your case it is base 64 encoded, which is needed if you want to store or send the ciphertext as printable text. See also the answer on your last question below.

  If No, what is the correct method?

The method used in the code, OAEP, is specified in PKCS#1 v2.1 and 2.2 of RSA labs. As these standards keep changing location I usually use the RFC 3447 instead.

  The output is 172 characters each time? How does that work out?

The output of the RSA encryption is of course always less than the modulus. As part of the PKCS#1 algorithm it is put through the I2OSP transformation (see the RFC). This encodes the resulting number from the calculation to an octet string (or byte array) with the same size as the modulus, in bytes. To be precise, it is transformed into a byte aligned, statically sized, unsigned, big endian encoding.

Now you see the output as Base 64. That means that it consists of $(172 / 4) * 3 = 129$ bytes. However, there is one padding character =, so that means a ciphertext of 128 bytes or a ciphertext of 1024 bits. This means that your modulus and therefore your key size is also 1024 bits. You should upgrade to a higher key size.

  If padding is different each time, shouldn't it be mentioned or the length of the actual message be mentioned with the cipher text so that deciphering code can differentiate the padding from the actual message?

The trick is that first the ciphertext is converted in the number, then after modular exponentiation the padded plaintext message appears. The padding is self descriptive; it isn't just random characters.

  I also found out that I can't encrypt more than 86 characters. Why? Is there a limit on the number of characters by RSA?

There is a relatively high amount of padding, including said overhead. So the type and minimum amount of padding determines the limit that can be encrypted using a single "block" encrypt of RSA. Usually a random symmetric data key is encrypted, which in turn encrypts the plaintext. This is because RSA is highly inefficient. This type of protocol is called a hybrid cryptosystem. Instead of PKCS#1 compatible RSA, RSA KEM could also be used for encryption.


Examples of flattening code to create an R1CS When preparing logic for use in a zkSnark, one needs to first "flatten" the code so it can be written as a series of constraints.

I'm finding it hard to find examples of doing this. For instance, how would I do convert the following logic into a series of constraints:

if ((input_1 && input_2) || input_3) {
  result = input_1 + input_2
} else {
  result = input_3
}

How would you go about converting this into an arithmetic statement that can then be then re-written as a series of constraints?  Or does there exist any examples of this sort of process that someone could learn from?

This sort of programming logic for the ZK SNARK systems can be developed into Arithmetic Circuits using Zokrates, a toolbox for zkSNARKs on Ethereum. It helps you use verifiable computation in your Decentralised Applications, from the specification of your program in a high-level language to generating proofs of computation to verifying those proofs in Solidity, the Smart Contract Langauge for Ethereum Blockchain. Please find a sample programming logic written for Zokrates below.

Once you compile the code, you can proceed to the circuit setup. It creates a prover key and verification key. These keys are derived from a source of randomness, commonly referred to as “toxic waste”. Once it is generated, you can proceed to generate a Solidity contract which contains the generated verification key and a public function to verify a solution to the compiled program. Then you can compute a witness for the compiled program. A witness is a valid assignment of the variables, which include the results of the computation.

def main(field a, field b, field c) -> (field):
    field result = 0
    result = if a + b > c  then a + b else 1 fi
    result = if a + b < c  then c else 1 fi
  return result


Is "Bit Independence" of SHA-2 hashes secure? I know bit independence is good in SHA2 function output, but is it truly 100% secure?  For example:

Y = SHA512(secretKeyNonce256bit)
A = first 32ytes / 256bits of Y, used as message encryption key
B = next 16bytes/128bits used as authentication HMAC key for message
C = next 16bytes/128bits used as access code. NON-SECRET, and known to message carrier. If user provides this code, he is given the encrypted message by the carrier.

Does having knowledge of C yield some insight into A,B?  Would it be better to instead use C2=first 16 bits of SHA256(C) ?

One weakness, which extra SHA does not prevent, is if secretKey were derived from a crummy password [not the case here], C would be valuable to whoever attempted brute-like password guessing, because if a tried password produces C, it is likely that the password is correct & can produce correct A, B.  Some people may mention 128bit HMAC is on a weaker side, but I think 128 / 64bit collision resistance is sufficient for my application.

There is no known exploitable relationships between the words (32/64 bit "chunks") of SHA-2 but this is always a source of cryptanalysis.  There are some academic weaknesses against reduced round variants of SHA-2 but nothing against the full cipher.  Still hashes are cheap so why not just use multiple hash functions?

Seed = HASH(secret)  <- This should be a KDF instead see below
A = HASH(Seed)
B = HASH(A)
C = HASH(B)

If you need less bits you can just chop them down (it is good enough for NIST). Here is another option.

> Seed = HASH(secret)  <- This should be a KDF instead see below
> A = HASH(Seed XOR ConstantA)
> B = HASH(Seed XOR ConstantB)
> C = HASH(Seed XOR ConstantC)

Keep the constants the same same length as the output of HASH to avoid a biased result.

Use a KDF

I am assuming "secretKeyNonce256bit" is really a human generated password.  Using a simple unsalted hash to derive a key from a low entropy secret is a bad practice. You say "not the case here" but it is unclear if you mean it is not a password or not a "weak password". If "secretKeyNonce256bit" is a 64 byte random value from a CSPRNG then ignore this but if it is the result of any human selection you really should be using a true KDF (like PBKDF2, Bcrypt or Scrypt).


PRG exponential expansion I am just beginning to read into pseudorandom generators and I came across this definition for a PRG:
$G_n : \{0,1\}^n \rightarrow \{0,1\}^{l(n)}, \quad \text{ where $l(n)$ is a polynomial}$
Is there a reason why $l(n)$ has to be polynomial? Wouldn't there be an even better security guarantee if it was an exponential function? Simply because the adversary in the definition of pseudorandomness also is a probabilistic polynomial-time adversary.

There are two problems here. The first one is, that a PRG with an exponential output length can no longer be an efficient (i.e. polynomial time) algorithm, since it needs exponential time to even write its output.
The second problem is that any such algorithm is insecure. The distinguisher against a PRG receives a string $y\in \{0,1\}^{\ell(n)}$, that is either the output of the PRG, or a uniformly random string. It is required to be efficient, i.e. it must run in time polynomial in its input length. If the input length is exponential, say $\ell(n)=2^n$, then it can run in time polynomial in $2^n$. That is enough time to enumerate all possible seed values $s\in\{0,1\}^n$, compute $y':=G_n(s)$ and check whether $y' = y$. Since for uniformly random $y$, the probability that such a seed exists is (really really) negligible, this leads to a trivial distinguishing attack.


How can I validate a hashed password if all I have is another hash? The Scenario
I have a client-side web application that bounces requests against a server-side API.  For the sake of simplicity, every request must pass a username and password.  This is similar to old school XML-RPC where the username and password are passed as parameters in every request.
However, as this is a REST service, some of the requests (GET and DELETE) don't have message bodies and must pass the username and password as query variables in the URL:
GET http://application.url/endpoint?username=xxxx&password=xxxx

This is, frankly, a bad idea.  Requests are logged on the server, so if I send the password in plaintext, it's now sitting in a log file somewhere on the server.  I don't ever want to be sending the password in plaintext over the wire, so I'm stuck with a dilemma.
Approach 1
The first approach to solving this over-the-wire problem was proposed by a coworker:

Encrypt the password using something like Blowfish and store it in the database.
The client hashes the plaintext password plus some salt using some known scheme (i.e. SHA512).
The client send the hash and salt to the server.
The server decrypts the stored password, hashes it with the provided salt, and compares it to the provided hash.

This is an effective means of sending sensitive data across the wire (if the logs were read, no one would be able to snag the password).  But it breaks another one of my personal security rules - I have access to the user's original password!
If the password is stored in the database using reversible encryption, then it's still vulnerable to attack.  Someone could steal my database and decrypt the password.  To me, this is almost as bad as storing it in plaintext to begin with.
The server should not have access to the plain text password.
Approach 2
This approach was suggested in passing by a fellow developer and, on the surface, seems to solve some of my problems.

Hash the password with some salt and store the hash and salt in the database (no plaintext!).
The client encrypts the password using the server's known public RSA key
The client sends the ciphertext to the server.
The server decrypts the password using its private key and hashes the recovered plaintext with a known salt.
The server compares the computed hash with the hash stored in the database.

Once again, an effective way to prevent sending the plaintext password over the wire.  It has the added benefit of never storing the plaintext on the server as well.
But it still bugs me, because the server can see the plaintext after decryption.  Though I can build the system today to be secure, there's no guarantee another developer won't add logging somewhere in the future and write the plaintext to disk.
I'd be much happier if the server never had access to the plain text password.
End Goal
At the moment, approach #2 is the best solution I've come up with and will probably be what I end up implementing.  But there is an ideal solution out there ... I just don't know how practical (or even possible) it might be:

Hash the password with some salt and store both in the database (no plaintext!).
The client hashes the password on its end with its own salt.
The client sends the hash (and the salt?) to the server.
The server runs some other functionality to see if the two hashes (its and the client's) were generated by the same plaintext - it does not get the plaintext.

I could wire up some kind of challenge/response system (where the client asks for a salt, hashes the password with that salt, sends the response, and the server compares it with what it expected), but I'm trying to keep requests to a minimum.  So you'd only make one call to the server when you make the request rather than one call to authenticate and another to execute.
Is this last scenario even possible?

With the method below, the server never sees either the password or the key the password decrypts.

To generate a password:

The client generates a new RSA key, encrypts it with the password (using something like PBKDF2 to generate a symmetric key), and hands the server the RSA public key and the encrypted private key.

To Authenticate:

The server sends the client the encrypted RSA private key and a challenge. The client uses the password to decrypt the RSA private key and then signs the challenge. The client sends the signed challenge back to the server. The server verifies the signature with the RSA public key.

Caution:

Make sure changing passwords involves creating a new private key, not re-encrypting the old one with the new password.

--

This has an extra request. You can avoid that with two tricks:

Have the client store the encrypted private key so it doesn't need to ask the server for it.
Have the client store a sequence number to use as the challenge (or a timestamp and a random number), so it doesn't need to get a challenge from the server.