Is there a deterministic one-way collision-free crypto algorithm? I use usernames encrypted using a function f as ids of records. Users see records identified by f(username). I must not know real usernames.

I want to be protected from attack when adversary who has a username u1 and knows f generates another username u2 such that f(u1) = f(u2), logs in with this username and sees the data of user with username u1.

So, f must be:

deterministic: I use f(x) as identifier. It rejects RSA encryption with throwing out secret key.
one-way: I must not be able to get a real value from encrypted value.
collision-free to prevent attack describes above. It rejects md5/sha because as far as I understand they are easily crackable, especially because I don't use salt (unavoidable technical reasons).
quick to compute: I must handle tens of thousands messages per second. It rejects b/crypt.

Note that I don't care about length of output (it may be fixed or variable).

I was looking at MAC and Digital Signature algorithms but can't figure out which of them have required properties.

At SEJPM indicated, MD5 and SHA-1 probably are resistant enough for you never to get a collision. However, that doesn't mean that either of them is secure. Neither is SHA-2 or SHA-3. That is, given that the usernames do not have a special structure that makes them hard to guess.

The problem is that user names can - generally - easily be guessed. So whatever you do to them, a deterministic algorithm will expose them. You can just perform a dictionary attack and find the resulting value in the set of stored user names. This way most usernames will easily be found.

If you want to protect them you may need a second system (trusted third party, an entity other than the user or service provider) that performs username encryption / decryption or password hashing with a pepper - a secret value just like a key.

But in general it is better to make sure that knowing the username gives the adversary few - if any - advantages. This is the case in the majority of cases, although may systems may not indicate if a username or password is incorrect - making guessing of the combination of both just that little bit harder.


bcrypt and pbkdf2 double hashing If I want to protect myself from implementation of algorithm issues and inherent design flaws of algorithms in password hashing, what would be most secure way to combine two hashes?

bcrypt(pbkdf2(pw))
pbkdf2(bcrypt(pw))
f, l = split(pw); pw = bcrypt(f) + pbkdf2(l)  # loses entropy, bad
pw = bcrypt(pw) + pbkdf2(pw) ## one broken, both broken, particularly bad

Something else? Should I do variation of 1-2 where I'll add entropy?

Why isn't this common/best-practice when storing user data in databases? Using any single hash algorithm seems risky when you combine implementation + design risks. Using SHA seems odd choice, as it's designed to be fast.
Seems odd that end-user needs to think about this and figure out safe way to store PWs.

I don't want to make perfect-world bcrypt or perfect-world pbkdf2 better by this means, I simply want to assume that there are scenarios where in particular environment one of them may be bad to begin with at least. Or in future one of them is found to be not as nearly secure as it was thought to be, giving me safety margin to migrate to another combo of hashes, without going into panic mode.

You have two algorithms, $A$ and $B$, that claim to compute two (essentially) injective, hard-to-invert and costly-to-compute functions $F$ and $G$. Your fear is that either of the algorithms instead compute functions $F'$ and $G'$, that may be neither injective, hard-to-invert, nor costly-to-compute. This may happen because of programming mistakes or (these days) deliberate sabotage.

What you want is some way to combine $A$ and $B$ such that the corresponding combination of $F$ and $G$, $F'$ and $G$, and $F$ and $G'$ is (essentially) injective, hard-to-invert and costly-to-compute. (If both are defective, then it will obviously not be possible to do anything.)

Observe that $F(G(\cdot))$ and $G(F(\cdot))$ are bad constructions (they fail injective).

The construction $(F(\cdot),G(\cdot))$ does not fail injective and costly-to-compute, but may fail hard-to-invert.

If we assume that $F$ and $G$, $F'$ and $G$, and $F$ and $G'$ are in some sense independent (that is, say, $F'$ is not $G$), then $$F(\cdot) \oplus G(\cdot)$$ should be ok.

Why don't we do this? To a certain extent, you can verify the implementations by comparing with test vectors and other known-to-be-good implementations.


Getting the s-box input from its output in differential cryptanalysis on DES If we try to get K4 using differential cryptanalysis on 4-variant DES, how can we get the input of a certain S-box if we know it's output?

This seems hard to do since the substitution operation is non-invertable for DES.

In DES cryptanalysis this is in general achieved by trying all 4 possible preimages for the given S-box output.

In particular, for S-box $S_i$ a 6-bit input (say $b_1b_2 ... b_6$) produces a 4-bit output $a_1a_2a_3a_4$. The s-boxes can then be written as a 2-dimensional array of size 4x16.
The input bits $b_1b_6$ determine the row of the s-box table and the input bits $b_2b_3b_4b_5$ determine the column. The value of the output corresponding to the 6-bit input is the value at cell $S_i[b_1b_6][b_2b_3b_4b_5]$.

Therefore, given an output $a_1a_2a_3a_4$ there are exactly 4 possible inputs corresponding to this output, one in each row of the array corresponding to S-box $S_i.$

If additional information is available - such as Hamming weights within some side channel attacks - this can be done more efficiently.


Elliptic curves for ECDSA I'm trying to implement parameters generation for ECDSA according to SEC1 v2.0:
Input: The approximate security level in bits = t is {80, 112, 128, 192, 256}
 Output: Elliptic curve domain parameters over Fp: T = (p, a, b, G, n, h)

Here's the 2nd step of the algorithm:

Select elements $(a, b)$ is $F_p$ to determine the elliptic curve $E(F_p)$ defined by the equation:

$E : y^2 = x^3 + ax + b \bmod p$,
a base point $G = (G_x, G_y)$ on $E(F_p)$, a prime $n$ which is the order of $G$, and an integer $h$ which is the cofactor $h = E(F_p)/n$, subject to the following constraints:

$4a^3 + 27b^2 \neq 0 \bmod p$
$E(Fp) \neq p$.

$p^B \neq 1 \bmod n \space\forall\space 1 <= B < 100$
$h <= 2 ^{(t/8)}$
$n−1$ and $n+1$ should each have a large prime factor $r$, which is large in the sense that $log_n(r) > (19/20)$.

I haven't understood a lot of things in 2nd step.

How to select a and b for E(Fp)? Should it be done randomly just to satisfy 4a^3 + 27b^2 != 0(mod p) ? Yes it should, as far as i've understood.
How to find #E(Fp) -- the cardinality of E(Fp)? -- Schoof or SEA algorithm.
How to choose generator -- $G = (G_x, G_y)$ and find its order $n$? -- Random point should be chosen on a curve. Again not pretty sure about it. EDIT: The point has to have a prime order. How can a point be chosen with a prime order?

It is easier to generate a point with order $n$ than to find out the order of a random point:

Generate a random point $G'$ (generate random $x$ and solve for $y$)
Compute $G = hG'$ (multiply by cofactor)

This is guaranteed to generate a point $G$ with order either $n$ or $1$ (the point at infinity). The chance of generating the point at infinity is negligible, but you can check for it and regenerate $G$ if you want.

This procedure is described in section 3.1.3.2 "Point Selection" in SEC1v2, where it computes a generator from a seed $S$. It is more convoluted since it generates points verifiably at random.


Do any NIST PQC have "homomorphic" public keys, in the sense that any two pubkeys derive a combination pubkey? Background:

The MathMesh crypto platform (refs at the bottom) is a newly-proposed technology stack which has been somewhat cheekily called a "Grand Unified Theory of Security on the Internet". Its "Meta Cryptography" module relies on the following property of Discrete-log Diffie-Hellman:

$privKey: x, pubKey: X = x.P$

$privKey: y, pubKey: Y = y.P$

Therefore you can derive "combination keys" by either combining two public keys or two private keys.

$Z=X \oplus Y = (x \otimes y).P$

for some appropriate definition of $\oplus$ and $\otimes$.

Question:

Will this survive the transition to post-quantum asymmetric KEMs? More specifically, how likely is it that there is some definition of $\oplus$ and $\otimes$ that allows "combining" of public keys and private keys in this way for lattice, code, multivariate and/or SIKE keys?

References:

https://mathmesh.com/
7 hours of youtube video
IETF 106 slides, specifically see slides 23-27.

No, this does not survive as is in the quantum world, since all discrete logarithm schemes (including Diffie-Hellman) are broken.

And more generally, this is probably not possible in the quantum world a priori, because it would imply having group homomorphic properties, which are hindered by the fact that Shor's algorithm is actually made of two parts:

A reduction of the factoring problem to the problem of order-finding.
A quantum algorithm to solve the order-finding problem

and the problem is that the order finding part implies that it allows to find the order of a group element, thus allowing to break the discrete logarithm easily.

There is even an impossibility result from 2014 for group homomorphic encryption in the quantum world.
Its core idea is basically that you can win the IND-CPA game by choosing two messages $m_0$ and $m_1$ such that $m_0=e$, and $m_1\neq e$, for $e$ the identity element in your plaintext group, which will be mapped when encrypted to the identity element of the ciphertext group, and since you can compute the order of an element using Shor's order finding part, you can find whether the ciphertext has order 1 (in which cases it corresponds to $m_0$) or not.
And the same kind of problems will arise with digital signatures or key exchanges algorithms.

This is also the reason why it is extremely difficult to come up with zero-knowledge proofs that are quantum safe.


PKCS12 key derivation In older versions of PKCS#12 there was a key derivation function that, near as I can tell, isn't used anywhere outside of that standard:

https://tools.ietf.org/html/rfc7292#appendix-B

That discusses it. So in that standard there's a loop:

   6.  For i=1, 2, ..., c, do the following:

       A.  Set A2=H^r(D||I). (i.e., the r-th hash of D||1,
           H(H(H(... H(D||I))))

       B.  Concatenate copies of Ai to create a string B of length v
           bits (the final copy of Ai may be truncated to create B).

       C.  Treating I as a concatenation I_0, I_1, ..., I_(k-1) of v-bit
           blocks, where k=ceiling(s/v)+ceiling(p/v), modify I by
           setting I_j=(I_j+B+1) mod 2^v for each j.

   7.  Concatenate A_1, A_2, ..., A_c together to form a pseudorandom
       bit string, A.

There's an open errata against the RFC that suggests that step A ought to read more like this:

Set A2=H^r(D||I). (i.e., the r-th hash of D||I, H(H(H(... H(D||I))))

ie. it ought to replace D||1 with D||I. My question is...  should A2 be replaced with Ai? Because if not then it doesn't appear that A2 is actually used anywhere whereas AI is.

Of course, even if that's done...  if I is being changed each time then it seems to me like you'd have to be doing hash a lot. Like instead of performing the hash operation c times you'd need to do it this many times:

$$\sum _{ n=1 }^{ c  }{ n  } $$

Is that a correct interpretation?

Yes, it should be Ai, or more exactly A_i denoting subscript. Note that i (the chunk subscript) is not I (the salted password input). I submitted this to rfc-editor in Feb (see https://security.stackexchange.com/questions/112627/what-password-based-key-derivation-does-pkcs-12-use) and they said they were going to fix it; I guess it got lost.

For confirmation you can see the source document from RSAlabs-now-EMC linked there, at least as long as Dell doesn't start mangling the EMC website(s) the way EMC for years mangled the RSAlabs website.

And that PKCS12 PBE is still used, even though PBES2/PBKDF2 from PKCS5v2 is now recommended (and other options like bcrypt, scrypt, Argon2 even more).


Stretching a random seed to maximize entropy I'm using a random number generator that requires me to pass it a big (several kilobytes) pool of random data for initialization.

I've gathered entropy from various system metrics (free memory, system clock, mac address .etc) and generated a 64-bit seed value which I need to "stretch" over the big memory pool.

Whats the best way to spread this small amount of entropy over the big pool? I've considered something like encrypting a null (0x00) buffer with a stream cipher using the seed as the key. Is that a safe approach?

What you ask for is a RNG to produce some output which another RNG will use as seed. This looks quite overly complex...

The point of the seed is to be unknown to the attacker: the seed data should be such that "trying out" possible seed values should not match the actual seed except with negligible probability. With a 64-bit seed, even if the seed is "perfect" (chosen totally randomly and uniformly among the $2^{64}$ possible seed values), an attacker trying possible seed value still has a $2^{-64}$ probability of finding the correct seed at each try, and that's a bit high for comfort. We usually prefer attack probabilities of $2^{-128}$ or less. Regardless of how you generate your 64-bit seed, how you then expand that 64-bit seed into whatever ISAAC requires, and whether ISAAC is good or not, your security will never be higher than that provided by a 64-bit seed.

How ISAAC is supposed to be seeded (with what, under which properties) is not clear; the ISAAC author himself says:

  I provided no official seeding routine because I didn't feel competent to give one. Seeding a random number generator is essentially the same problem as encrypting the seed with a block cipher. ISAAC should be initialized with the encryption of the seed by some secure cipher. I've provided a seeding routine in my implementations, which nobody has broken so far, but I have less faith in that initialization routine than I have in ISAAC.

Come to think of it, this is a bit scary comment. Are you sure you want to trust the security of a system, a part of which being deemed by the author himself as being not trustworthy ?

And more generally, ISAAC was designed at a time where the competition was RC4, a generator with known biases, and not that fast. Science has improved since. See the eSTREAM project: this is the result of a kind of open competition, where cryptographers proposed new stream cipher designs, and tried to break the proposed designs. The resulting "portfolio" consists in the designs which resisted cryptanalysis, and offer good performance. The good thing about these stream ciphers is that they work with keys of reasonable size, with no underspecified part as the seeding in ISAAC. For instance, consider Sosemanuk: it accepts a key of 1 to 256 bits, and a 128-bit IV, and produces pseudo-random bytes at an reasonably high speed (it should be competitive with ISAAC, possibly even a tad faster).

This would lead to the following design:

Accumulate your source entropy in a buffer. It does not really matter how you encode each metric, as long as you do not lose information.
Hash the whole buffer with a secure hash function, preferably SHA-256. This results in a 256-bit value.
Use the 256-bit value as key for Sosemanuk (the IV can be 0). Produce random bytes. Enjoy.
(Alternatively, use the Sosemanuk output as seed for ISAAC, if you really need, for administrative reasons, to use ISAAC. But the under-specification of the seeding process could trigger weaknesses, so I would not recommend it at all.)

Note that entropy gathering is a subtle thing. MAC address and system clock, for instance, are really bad entropy sources because they can be observed by attackers: the system clock is close to the current time, which (by definition) is public data, and the machine will write its MAC address on every ethernet frame it emits. Entropy is good only insofar as it is unknown to the attacker. The good thing about SHA-256 is that it does not matter if some of your entropy is bad, as long as there is also some good entropy somewhere in your buffer. Still, you are warmly encouraged to use as entropy sources the services specifically offered by the operating system to that effect (it is called CryptGenRandom() on Windows, /dev/urandom on Unix-like systems and MacOS X): since the OS directly manages the hardware, it is in ideal position to gather entropy from hardware sources.


Use AES in Web Crypto with public/private key pair this is a very top-level question - as I'm just starting to delve into crypto.

The main objective is to be able to communicate between 2 mobile devices through a BAAS server such as Firebase so that one app can notify another one and send data.

The data to be exchanged are encrypted image documents. Security is paramount since the images may contain sensitive data.

I will be using Ionic 3 to develop the apps.

So far I have tested the following technologies:

Using WebCryptoApi in Ionic 3. I tested a few examples from WebCrypto Examples, and they
tested ok on android.
App to App communication (using Notification) using Firebase.

I plan to decode an image into Base64 (which is just a string) and use AES encryption/decryption.I plan to use the following simple workflow:

Case Scenario: User A requests file from user B:

User A creates key-pair and sends the public key to user B
User A keeps app open so that the private key is not stored anywhere.
User B encrypts the file with the public key
User B sends encrypted file to user A
User A decrypts user B's file

But Web Crypto does not seem to generate a simple AES Private/Public Key pair that enables me to encrypt/decrypt, as is the case with RSA-OAEP for example, where I can generate a public/private key pair.

AES-CTR, for example, only generates one key and uses a counter instead of a private key. But this counter is needed to encrypt as well, which makes my scenario not possible.

Is it possible to achieve my scenario with AES? If so, how should this be done? If not, what approach should I take?

I Appreciate any comments on this.

No, it is not possible to achieve this with AES.

AES is a block-cipher and AES-CTR is a symmetric encryption scheme. In particular, it is therefore not a public key encryption scheme, and there do not exist any public keys for it.


Calculate the security of a cascade cipher I’m reading “The Security of Multiple Encryption in the Ideal Cipher Model” and I’m having a hard time understanding something. How do I calculate the bounds of cascade cipher from  the following formula (where $k$ determines keysize and $n$ is the blocksize)?

  $\exp\left(k+\min\left\{\frac{k(ℓ′−2)}{2}, \frac{n(ℓ′−2)}{ℓ′}\right\}\right)$   where $ℓ$ is the cascade length and $ℓ > 1$

If there is a cascade of AES, Blowfish and DES then what will be the value of $k$? and what will be the value of $n$? is this just addition of the key size used by these block ciphers for determining the value $k$ and addition of the blocksizes for determining the value of $n$?

If the case is AES $\to$ DES $\to$ AES $\to$ DES $\to$ Blowfish, then is this just five times addition to determine $k$ and $n$?

It seems the result is specifically for multiple encryption with a single cipher (like in 3DES). It probably applies for different ciphers as well, but key and block sizes would need to be equal. You might get a lower bound by using the minimum key size, but don't quote me on that.

However, I don't think this is really relevant for a practical implementation. AES alone has a large enough key space that brute force attacks on the key are impossible. (Assume AES-256 if you care about quantum computers or are very optimistic about Moore's law.)

The formula tells you nothing about what the security is if some of the ciphers in your cascade are broken, which is the only reason you would use different ciphers in the first place. Therefore, it tells you nothing very important about the security of the cascade in practice, unless all the ciphers you used would be insecure on their own (again, 3DES). The brute force resistance is simply "enough".


Mental Poker with untrusted server (i.e. no peer to peer) The question of implementing peer to peer mental poker has already been asked on stackoverflow. And there appears to be an implementation called LibTMCG.

Also on this site a question was asked about problems such as clients disconnecting or refusing to act (show cards, bet/check/fold). LibTMCG seemed to not deal with such problems from a cursory glance.

An implementation of mental poker that is based on html naturally precludes peer to peer and must rely on an untrusted http server.

So given the constraint that the clients must communicate only with the http server how does the implementation of mental poker change? And are problems such as clients disconnecting or refusing to act (show cards, bet/check/fold) easier or more difficult given communication only with the server.

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

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

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

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


Prove that if we redefine the key space, we can assume Gen chooses a key uniformly I am working on problem 2.1 in Introduction to Modern Cryptography 2nd edition by Katz and Lindell.

  2.1) Prove that by redefining the key space, we may assume that the key generation algorithm $\textsf{Gen}$ chooses a key uniformly at random from the key space without changing $\Pr[C=c\mid M=m]$ for any $m,c$

We are told to define the key space to be the set of all possible random tapes for the generalized algorithm $\textsf{Gen}$.

I don't understand how we are supposed to prove that this algorithm $\textsf{Gen}$ chooses a key uniformly without knowing the algorithm itself. I am not really sure where to even start with this as I am new to proofs and crypto in general, and and all help will be useful!

What I do know:

$\textsf{Gen}$ is a probabilistic algorithm that outputs some key $k$ chosen according to some distribution. The finite key space $\kappa$ is the set of all possible keys that can be output by $\textsf{Gen}$

Sorry for the late answer, I got busy...

So, you know that $\mathsf{Gen}$ is a probabilistic algorithm. What's a probabilistic algorithm? It's an algorithm which, during its execution, can make some random choices, which can be modeled as coin tosses. In programming terms, the algorithm can use a special coin-tossing function, which returns $0$ or $1$ each with probability $1/2$. The random tape is where the machine will write down the result of its coin tosses (or equivalently, where an external coin-tossing device will write the result of the tosses for the machine to read them). Because the results of the coin tosses are uniformy distributed, the contents of the random tape will be uniformly distributed as well and you can use that as your key.

Consider for example a cryptosystem with $\mathcal{K} = \{0,1\}$, and $\mathsf{Gen}$ as follows (in Python-like pseudocode):

def Gen():
    coin1 = toss_a_coin()
    coin2 = toss_a_coin()
    if coin1 == 0:
        return 0
    elif coin2 == 0:
        return 0
    else:
        return 1

It is clear that the key is not chosen uniformly: $0$ is chosen with probability $3/4$. Now, consider a cryptosystem with $\mathcal{K}' = \{(0,0),(0,1),(1,0),(1,1)\}$ and $\mathsf{Gen}'$ as follows:

def Gen'():
    coin1 = toss_a_coin()
    coin2 = toss_a_coin()
    return (coin1, coin2)

Now the key is chosen uniformly. Define encryption and decryption with the keys $(0,0)$, $(0,1)$ and $(1,0)$ to be the same as with the key $0$ in the previous system (whatever that is), and encryption/decryption with the key $(1,1)$ to be the same as with the key $1$. It is clear that you get essentially the same cryptosystem, but with the key chosen uniformly.


Why can't they just fix SHA-1 if it's broken? Presently 160 bits of hash block width seems to provide adequate security against brute force attacks.  The recent developments concerning SHA-1 have reduced the effort to force collisions by 5 orders of magnitude according to the latest Wikipedia edit.

Other cryptographic primitives have been evolved to fix issues that were similarly found, such as:-

RSA -> increasing bit count
RC4 -> RC4A -> Spritz
Whirlpool0 -> WhirlpoolT -> Whirlpool

I'm specifically using the term fix, to mean keeping the SHA-1 160 bit essentials and making internal changes /improvements.  So some (but not limited to) changes might be:-

amending the round count with perhaps double rounds to tie in with the existing key schedule as 80 x 2 instead of 80 x 1
changes to key schedule to increase rounds directly
something akin to internalising SHA-1(SHA-1(message))
additional bit wise operations

Hopefully you get the idea.  Why can't we do this so that it forms a plug in upgrade whereby the existing block size can be kept?  My intention is to easily prolong the life of SHA-1 in existing code and data bases without huge and far reaching programmatic changes.  I realise that 160 bits will someday become insecure requiring it's ultimate replacement by a wider hash.

I have 3 answers: We can't fix SHA-1, we shouldn't fix SHA-1 and we already did fix SHA-1.
SHA-1 is a hash standard; many different people can and have implemented it and they all get the same results. SHA-1 is broken. We have to replace it and convince everybody to move on to a new standard. A fixed SHA-1 wouldn't be SHA-1.
We shouldn't try a minimal fix; we should build the best (fastest, most secure) hash algorithm we can. A minimal fix will keep us with the problematic basic structure of SHA-1. If are switching, we want something which will be secure for many years to come. And be as efficient as possible.

That said, we already fixed it. It's called hardened SHA-1; it is immune to the known and similar collision attacks and it is even backwards compatible with SHA-1, sort of. It detects patterns which will occur in a collision attack and are very rare in random data. Hardened SHA-1 is identical to SHA-1 on almost any input, yet won't be the same and an infinitesimally small portion of inputs we see in collision attacks of the class published.

However though there are no currently known attacks on hardened SHA-1 and it isn't much slower. Nobody has the illusion SHA-1 has competitive security with SHA-2 or SHA-3.
Even if you need to truncate to 160 bits, these are probably safer options.  If you must have backwards compatibility as a quick fix, Hardened SHA-1 is a great trick but you should make plans to switch to SHA-3


How to prove a pseudo-random function has certain expansion factor How should I answer the following problem:

Let $F = F0 \times F1$ be a pseudorandom generator with expansion factor $2n$ such that for
    all $x \in \{0, 1\}^n$
    $$F(x) = (F_0 (x) || F_1 (x))$$ and $$|x| = |F_0 (x)| = |F_1(x)|.$$
    Prove that
    $$F'(x) = (F_0 (F_0 (x)) || F_0 (F_1 (x)) || F_1 (F_0 (x)) || F_1 (F_1 (x)))$$
    is a pseudorandom generator with expansion factor $4n.$

Here I am not able to understand how expansion factor changes?

I am more interested in general proof structure for solving similar proofs.

I am beginner so more detailed explanation will be helpful.

The concatenation operator $||$ in e definition $F$ ensures an expansion $n \rightarrow 2n$ since both $F_0$ and $F_1$ map $n$ bits to $n$ bits.

The argument for $F'$ is similar since repeated application of two $n$ bit to $n$ bit functions gives an $n$ bit to $n$ bit function, and four of those are concatenated in $F'$.


Verifying Self-signed SSL Client Certificates I have a service and I want to authenticate my clients using SSL client certificates. Now I want the key exchange process to be as simple as possible, kind of like SSH: You generate a keypair and upload the public key to the server (which you already trust).

Now I want to verify the certs I get from the clients… not by their trust chain, but solely based on the certificates I have stored on the server.

Should I compare the whole certificate or only the SHA256-Hash?

Your problem boils down to the following:

Client shows $v$ (his certificate).
Server wants to know whether $v$ is the same one as previously. He may store $v$ itself, but $v$ is somewhat bulky, so the server would like to store $h(v)$ only, for a hash function $h$.

So can an attacker show up with a value $v'$, distinct from $v$, such that $h(v') = h(v)$ ? If the attacker can, he wins. If he cannot, then storing $h(v)$ is sufficient.

If the hash function is second preimage resistant, then, by definition, the attacker cannot. SHA-256 is believed to be second preimage resistant.

I must also insist that the certificate is only the public part; the server must still extract the public key from the certificate sent by the client, and use it to verify the signature sent by the client as part of the ClientKeyExchange handshake message. Normally, the SSL implementation takes care of that point.

An edge case happens with DSA public keys. A DSA public key contains some parameters (modulus $p$, subgroup order $q$, generator $g$) and the actual user-specific public value ($y$). It is allowed, as per X.509, to omit the parameters from the certificate, keeping only $y$, if the certificate is signed by a CA which also uses DSA with the same parameters. This is parameter's inheritance. This is not compatible with your idea, because the client's public key cannot then be extracted from the user's public key alone; you still need X.509 path validation. But, in practice, this won't happen: nobody really uses DSA certificates, let alone DSA with parameter inheritance.


Quantum bit level security of Supersingular Isogeny based Diffie Hellman scheme I'm a newbie in studying and learning how SIDH works.
I have a simple doubt.
So my question is in the SIKE submission  present in this link (https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions), once you download and unzip the SIKE folder, you get supporting documentation, a .pdf file. In that .pdf file, Section 5.1, 5.2  (Chapter 5), in Table 5.1, they mention that SIKE503 has a quantum security level of 64 bits and SIKE 751 has a quantum security level of 96, right?
The doubt that I have is SIDH or SIKE is not a block cipher, isn't it? Can we still use Grover's algorithm to get it quantum security level ? or am I missing something here. Any explanation will be highly appreciated. Thank you so much for your patience! Looking forward to some help

Block cipher is a concept from symmetric cryptography. Here we're talking about public key cryptography. SIKE is a public key encryption (PKE), and a key encapsulation mechanism (KEM).

Of course Grover's algorithm applies to any public key cryptosystem, but there is not a single system where we don't know a better algorithm than Grover's. SIKE is no exception.

The quantum security of SIKE is (roughly) obtained by dividing the bit-size of the prime p by 6. For example SIKE503 has about 80 qubits of security, but NIST security categories come by large increments (64, 96, 128 qubits), the closest one being 64 qubits.

There is currently debate on whether the divide by 6 rule is too pessimistic.


SHA-256 Partial Collision of initial 36 bits and more I was lucky enough to, by brute force, have found two different messages, whose SHA-256 hashes collide in the first 9 hexadecimal characters, which are 36 bits, let's call this hash-prefix.

Given the Birthday Problem, I had to put together 2^18 or rather 2^(36/2) hashes so the chance of success at finding the two messages that have hash-prefix collision would increase to about 50%. I did find them by just gradually comparing the prefixes of each hash with another. The process didn't take too long, but that's why I was lucky.

I want to find 2 different messages that, after hashing, collide in more than 36 initial bits. Can you please help me to come up with a better strategy when comparing hashes?

Here is my method for comparing the hash-prefixes:

class FindPartialCollision {
private:
    ...

public:
    ...

    bool compare(vector<string> sv, int n_Hashes) {
        for (int i = 0; i < n_Hashes; i++) {
            for (int j = i + 1; j < n_Hashes; j++) {
                if (sv.at(i) == sv.at(j)) {
                    cout << "COLLISION FOUND." << endl;
                    return true;
                }
            }
        }
        cout << "No collision found." << endl;
        return false;
    }

    ...
}

Note that vector<string> sv only contains the initial x-character string taken from each SHA-256 hash of each messages, where x is the desired length to compare.

For example, if I were to look for a pair of messages, whose hashes collide in the first 10 hexadecimal characters, the n_Hashes value passed into this method would be 16^(10/2) = 2^(40/2) = 2^20 = 1 048 576, which is already too big and would result in a huge time complexity.

Any help is much appreciated and
I'm sorry for the amateurish question.

Actually, this sort of programming question is more suited for stackexchange.

However, to answer your question, there are two obvious approaches to speed up a collision search:

Use a Hash table; that is, instead of keeping everything on one big list, divide them onto (say) 1024 different lists (in such a way that you know that items on two different lists aren't "matches").  And, given that you know that the SHA256 is already wonderfully distributed, you can (for example) select the hash table entry that a specific hash is placed on by using the first 10 bits of the SHA256 hash value; that way, you'll never have to explicitly compare two hashes that differ in the first 10 bits.  That reduces the number of comparisons you'll need to do by 99.9%.  Of course, you'll adjust the size of the hash table (that is, how many entries it contains) according to the resources you have.
Use a sort algorithm; that is, use a good algorithm to sort the hashes into ascending order; that way, any 'close' matches will be adjacent, and so that's the only comparisons you'll need to make.  A good sorting algorithm on $N$ elements can be done in $O(N \log N)$ time, hence this is much faster than individually comparing each element.

I don't know which would be better in your situation; however it ought to give you something to think about.


Should HMAC or NMAC or plain Keccak be used for a secure MAC? After some digging around in the HMAC spec I found this (paraphrased):

  Step 1: If the length of Key equals the block size of the hash
  function (512 bits/64 Bytes for SHA-256), set the key equal to the
  key. Go straight to step 4.

  Step 2: If the length of key is greater than the block size of hash
  function, hash the key to obtain a string the same length as the hash
  function output, then append 0s up to the length of the Block Size.

  Step 3: If the length of key is less than the block size of the hash
  function, append 0s to the end of the key so that the key length is
  now the same size as the block length.

So if you input a 512 bit key of:

ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a
2192992a274fc1a836ba3c23a3feebbd454d4423643ce80e2a9ac94fa54ca49f

Then it will be untouched. If however you add at least one Byte to the end e.g. 'aa', the key now becomes:

3f78f631195be2c7675973fb6c542a7b9b6cda1e6ba59bd1093ebacf70408f53
0000000000000000000000000000000000000000000000000000000000000000

Or if you have less than the block size, perhaps a 256 bit key of:

ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a

Then it now becomes:

ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a
0000000000000000000000000000000000000000000000000000000000000000

It would seem that the more secure way to use HMAC would be to input a key that is exactly equal to the block length of the cipher being used, which for SHA-256 would be 512 bits. This must give full 512 bit diffusion of the key into the HMAC. Otherwise HMAC will turn at least half of the key to zeros.

I did a bit more reading and found that the there is an NMAC spec which is similar to HMAC but requires two independent random keys:

  NMAC = H(k1 || H(k2 || m)).

Questions:

What is the security impact of having at least half the key as null Bytes in HMAC (which would happen in the majority of cases, unless care was taken to specifically choose key sizes the same length as the block size)?
In general, which is the more secure construction, HMAC or NMAC? Given that the spec for HMAC seems to not use two independent random keys, but derives the inner and outer keys from the main key, and also weakens the main key in the first 3 steps.
If I had a key longer than the block length of the hash function, would it be stronger to use the NMAC construction instead of HMAC? Perhaps by splitting the full random key in half to use as k1 and k2. For example, I have a random 768 bit key, I split that into two 384 bit keys then use that with NMAC. Under HMAC that 768 bit key would be reduced to 256 bits psuedo random concatenated with 256 bits of 00000000000000000000... In this case I think NMAC would be more secure, correct?
I know HMAC is designed specifically for the Merkle–Damgård type hashes, but can Keccak (sponge construction) be used with HMAC? Or is it better to use it with the NMAC? Or simply do H(k || m) as the Keccac authors intended? Length extension attacks are no longer an issue for Keccak.

HMAC and NMAC make assumptions of the underlying hash function $H$ for their security proofs. Additionally they are designed to eliminate known flaws in other MAC constructions using MD type hashes.

NMAC is not $H(k1$ $||$ $H(k2$ $||$ $m))$, it actually uses the keys as the initial hash values, which require a higher level of access to the internals of the hash, meaning a large variety of implementations cannot use NMAC the same way they can use HMAC.

In response to your questions..

For HMAC, when the key length is shorter than the block length, there is no exploitable impact on security due to padding with null bytes. The maximum security will be the output length of $H$ or the input length of $k$, whichever is shorter.
NMAC is considered the stronger MAC, but because it requires modification of the initial hash value, it is less used in practice. Attacks on NMAC are applicable to HMAC, but not always the other way around. I would be concerned that there may be choices of IV that weaken $H$ with respect to it being a PRF, which could invalidate the security claims, however resistance against forgery in that case is most likely not compromised; this is only the case if the compression function is weak, and in that case there are other security issues with the hash.
Once again, since NMAC modifies the IV, you cannot have keys larger than the output length of $H$ for MD type hash functions. In HMAC, a key larger than the block size is hashed down to the output size, so the maximum effective size of the key is smaller.
Keccak can be used with HMAC but not NMAC, since the sponge construction security claim requires the state to be 0, and NMAC requires the state to be the key. The keyed sponge function $H(k$ $||$ $m)$ is likely more secure than HMAC for a given key length, due to the inner state being larger than the output length.

HMAC padding to the block size essentially allows a single iteration over that part of the message space to change the IV, making it closer to NMAC, since the next input to the compression function is the message. For HMAC, you will get the maximum security if the key length is equal to the blocklength, assuming that more security than the output length of $H$ can be achieved. The padding constants are there so the IV of both the inner and outer hash function are unique, but still related to $k$.

Keyed sponge functions gain security from capacity, with the bound being $min(2^{c-1}/M$ $,$ $2^k)$, where $c$ is the capacity, unless $M$ exceeds $2^{c/2}$. This means more security over large messages with a large enough capacity, since the security of HMAC starts to drop with every subsequent input block (correct me if I am wrong on that one), and is upper bound by $2^{c/2}$, where c is the digest size. This implies that a keyed sponge function can have a smaller capacity than is required for the security proof of HMAC, making it either more efficient or more secure given appropriate choice of $c$.

As fgrieu pointed out, HMAC and NMAC were not from NSA or NIST, but rather university research. The fact that NIST endorses it does not imply there is a weakness. The internal hash chain size is our limiting security factor here, as well as HMAC being constructed to make use of a hash function without limitation.


A specific way for deniable encryption I read the summary of deniable encryption on wikipedia:
https://en.wikipedia.org/wiki/Deniable_encryption

Then I read a question, by doom123 on security.SE:
https://security.stackexchange.com/questions/34684/truly-deniable-encryption

But I had a subtly different problem which can be stated as follows:

Alice wants to send Bob the book "Mocking Jay" which is banned in Bob's country.
Alice encrypts "Mocking Jay" to data MJ with the password P1.
Using another book of similar size (or by trimming a larger book), say the "The Hobbit", she processes the data MJ and computes password P2.

The solution to this problem will allow Bob to claim that he maintains a copy of "The Hobbit" (assuming that "The Hobbit" is not banned of course), while being able to read  "Mocking Jay". The solution, in theory, should also allow Bob to plausibly deny that there's any other copy hidden in the data "MJ" other than "The Hobbit"; or like the aforementioned security.SE question, should allow "MJ" to hold any number of copies (and thus any number of passwords), providing Bob the excuse of acknowledging only one copy that he has the knowledge of.

The answer provided by the user lynks to the question posed by doom123 solves the problem for storing data on a hard-disk. Is there a general solution to this problem?

UPDATE 1
With regards to the answer provided by fgrieu I am slightly modifying the question. Is it possible to add a third layer (and an arbitrary number of further layers) of such encryption? What I mean is, with Mocking Jay, The Hobbit, and Silmarillion (assuming that the books are roughly the same in size) as inputs, is it possible to create an encrypted output say MJTHSI? I am alright with the passwords being the output as well. Decrypting with password P1 will reveal Mocking Jay. If rubber-hose is used password P2 can also be given up revealing The Hobbit (with the intention of ultimately protecting Silmarillion which can be revealed using P3).

I understand the question as asking for a method such that:

after step 3., we'll have a reasonably small password P2;
deciphering MJ using P1 will give "Mocking Jay";
deciphering MJ using P2 will give "The Hobbit", or a meaningful extract of that, at least comparable in size to MJ;
MJ is produced at step 2. without "The Hobbit" as input.

By an entropy argument, that's impossible; for that would imply that the amount of information necessary to go from "Mocking Jay" to "The Hobbit" (or a meaningful extract thereof) can be summed-up in the short password P2.

Update: a possibility is that "The Hobbit" (or a meaningful extract thereof) is embedded in the decoding program, but that brings back the problem stated in the last paragraph of the present answer.

Remove the requirement that MJ is produced without "The Hobbit" as input, and it becomes possible. We can devise an encryption process with input ("Mocking Jay", P1), ("The Hobbit", P2), or more generally any arbitrary collection of literary work and distinct associated passwords, producing a ciphertext; and a matching decryption procedure accepting ciphertext and password, that will produce the appropriate work for the password, and an error (or garbage) for other passwords. The system can be resistant to cryptanalysis and key search, even for relatively short passwords, if we accept that the decryption procedure requires a few seconds, which enables password stretching using e.g. scrypt.

Thanks to data compression, the ciphertext can be smaller than "The Hobbit" (I assume "Mocking Jay" is smaller). We can even think of reusing the compression dictionary built from "The Hobbit" to compress "Mocking Jay", so that the ciphertext is of size more comparable to a mediocre compression of "The Hobbit", if we accept that P2 is necessary in addition to P1 to read "Mocking Jay", or equivalently that P1 is some extension of P2, or that the cipher protecting "The Hobbit" is of mediocre security.

Update: I have no implementation in mind, but this is a relatively simple matter with competent use of data compression, key stretching, and symmetric cryptography.

Huge problem is: an intelligent person caring to analyses the decryption procedure or the file format specification will likely understand that it is intended for deniable encryption, and then the risk is high that rubber-hose cryptanalysis will be used; something that would be avoided if the original problem could be solved; but it can't.


RSA key length choice for TLS when confidentiality not important? I've a couple of questions about this, the scenario is embedding a key pair in a hardware device which will speak with other hardware devices over tls.  computing resources are an issue so i want to make intelligent choices about where they go on.  We're using TLS to authenticate one device to another, and to ensure integrity of messages in transit.  Immediate or long term confidentiality of messages is not a consideration.

All the recommendations are in the case of RSA to use 2048 bit keys because that will be secure until 2030.  However, in my application the RSA key is used only to provide a TLS handshake for the lifetime of that key on that device, so it doesn't need to remain secure until 2030.  The AES session key is renegotiated every 24 hours and beyond that it doesn't need to be confidential.  TLS is being used to ensure integrity in transport only, the communicated data doesn't need to be confidential.

I'm aware 768 bit numbers have been factored, but my understanding is that factoring one 768 bit number does not help much to factor other 768 bit numbers.  I haven't found docs to say how long it takes to factor a number of X bits with equipment Y.  As an an example I'm going to say 5 years with budget X and equipment Y to factor 768 bits - then people can tell me if the following analysis is solid or not.

E.g. my device will be in use for the next 5 years.  I choose RSA 768 as key size and I change the keys every 12 months.  From day 1 an attacker tries to do every attack he can on the TLS crypto. After 2.5 years technological advances mean he can recover my RSA year 1 private key. However the year 1 can no longer be used to establish a TLS session so there's no impact there. The attacker can also recover the session keys of year 1 which were negotiated with the RSA year 1 key, but as the confidentiality of year 1 data wasn't important there is similarly no impact.

So given this why aren't RSA key size recommendations given in terms of attacker motivation, key lifetime, key usage rather than blanket recommendation of 2048?
Practicalities of generating keys / certs on build machines.  Being conservative I'd say this should be avoided, would it be reasonable to generate device keys via an OpenSSL script with FIPS options on an up to date build machine with appropriate controls, or should there be a hardware crypto-module ?  Or put another way, would an expert witness lambast us in some possible future court case if we had generated device keys in software on a build machine or is that a reasonable way to go about things ?
If I tried to factorize RSA 768 on my home PC and I was a competent mathematician, how long would it take me?  Same question but I have access to a computing cluster.  It seems that in 2009 the factorizing took 3 years, 6 labs, many mathematicians and hundreds of computers..

1.
To clarify: The critical time period here is one year (after wich the certs are changed). With the cracked RSA key the attacker can decrypt the traffic and do nan-in-the-middle attacks, posing as a valid hardware device.

Let us take the numbers determined by experts. In their paper on cracking the 768-bit RSA key the researchers state that they needed about $2^{67}$ instructions. When you look up current pricing for the Amazon EC2 cloud you get two Intel Xeon E5-2670 for 2.4\$ per hour. That is roughly $$2 CPUs \times 3\ GHz \times 8\ cores \times 8 FLOPS/cycle = 384\ GFLOPS$$ for 2.4\$/hour. That makes the cost of cracking a 768-bit RSA key about a quater million Dollars (on CPUs). Or 143 instances working for one month, or 1000 instances working for 4 days, etc. This is of course very simplified but gives you a rough idea.

Computing power doubles every 2 years and with special hardware, like GPU computing you can significantly lower the pricetag (modern cards operate in the order of TFLOPS see specs on AMD or NVIDIA websites).

A computer packed with 3 GeForce GTX 780 Ti (cost all together about 3000\$) can achieve 15 TFLOPS. This cracks a 768-bit key in 113 days, well under one year. So your key is definitly not safe from a moderatly determined attacker.

As for a 1024 bit key they state it would take 1000x more time or money. Very costly, but totaly out of reach in 5 years?

Other sources state a 2048 bit key would take $2^{32}$ times longer. So you are definitly save here.

But if I understand your scenario correctly you might be able to avoid the problem altogether: The computing cost of a larger RSA key only has to be paid once. During the inital handshake of the connection (generating the AES key). If you do not have a higly dynamic environment (meaning devices coming and going all the time) this cost will not matter much.

2.
For generating a few certificates a year you do not need a special module. This is only neccessary if you need massive amounts of randomness/entropy (e.g. if you need to produce a cert every second). Here is command to find out the (estimated) entropy of your system on Linux:

cat /proc/sys/kernel/random/entropy_avail

I would be more worried about the entropy available on those hardware devices (needed for the TLS handshake). If they are very simple microcontroles that might be a problem.

3.
Kind of answered that in question one.

Hope that helps!


Does RSA - the company - know the $p$ and $q$ used to create $n$ ($p$ and $q$ being prime) With the RSA cryptosystem, you  publish $n=pq$. Does RSA $-$ the company $-$ have/store the values of $p$ and $q$?

If not, how do they find $n$ without knowing $p$ and $q$.
Also, how do they find $(p-1)(q-1)$ without knowing $p$ and $q$?

In short, should I trust a private company with my encryption?

In short , should I trust a private company with my encryption?

In short, no, you shouldn't and you don't have to. That is the beauty of the RSA encryption algorithm (which is completely separate from RSA the company). You can use RSA the algorithm without RSA the company knowing anything about it.

If you want to communicate securely with RSA the company using RSA the algorithm, you tell RSA the company your RSA (the algorithm) public key, which includes $n$ (as well as the encryption exponent $e$). They don't need to know $p$ or $q$ or $p-1$ or $q-1$.


Security proof in pairing based cryptography Let :

$G_{0}$ and $G_{1}$ be two multiplicative cyclic groups of prime order $p$,  $g$ be a generator of $G_{0}$ and $e$ be a bilinear map,

$e : G_0 \times G_0 → G_1$

and let $_{1} = ^{_{1}} $, $ _{2} = ^{_{2}} $ , ... , $ _{}= ^{_{}} $;
$ =^{(+)/} $

such that $\alpha, \beta, r, s_{1}, s_{2}, ..., s_{n} \in Z_{p}$

Given $s_{x} \in Z_{p}$ ($x \neq i, i=1, ..., n$), and knowing $e\left( C_{1}, D\right), e\left( C_{2}, D\right), ..., e\left( C_{n}, D\right)$. I would like to know if it is possible to compute the value of $e(C_{x},D)$ and/or $D$.

Secret elements: $D$, $e(C_{x},D)$.

Public elements: $_{1}$, $_{2}$, ..., $_{n}$, $_{x}$, $e(C_{1},D)$, $e(C_{2},D)$, ..., $e(C_{n},D)$.

If it is not possible, how to prove that?

The only way i can see to evaluate $e(C_x,D)$ is to recover $D$ from a previous known pairing $e(C_i,D)$. However due to the Fixed Argument Pairing Inversion 1 assumption this is computationally hard.


Does lagrange interpolation work with points in an elliptic curve? Defining the lagrange interpolation for $x=0$ as $\mathcal{L} = \sum_{i=1}^{t+1} y_{i} \cdot l_{i}$ with $l_{i}$ as the lagrange basis polynomials. Does this hold if we apply the elliptic curve generator for each share $y_{i} \times G \rightarrow Y_{i}$ ?

Defining the elliptic curve version as $\mathcal{L}_{G} = \sum_{i=1}^{t+1} Y_{i} \times l_{i}$
Using a set of shares for the secret $\alpha$ as $S_{\alpha} = \{i \in [1, t + 1] : (i, y_{i})\}$ and elliptic curve point shares as $P_{\alpha} = \{i \in [1, t + 1] : (i, y_{i} \times G)\}$

I expect $\mathcal{L}(S_{\alpha}) \times G = \mathcal{L}_{G}(P_{\alpha}) = \alpha \times G$ to be the same, as also any homomorphic properties to hold.

As far as I know, I haven't seen anyone formulating this or use it in practice in any existing implementation. But the math seems correct. I just don't want to start implementing it without being sure that it works.

This is "half an answer" while I think about the other half :)

EDIT: other half added below.

The mathematical model that I find most useful for all discrete logarithm based cryptography is that of a vector space over a finite field. In many ways, the multiplicative-group implementation and the elliptic curve implementation are isomorphic, although it can be confusing because it's natural to write the former multiplicatively and the latter additively.

For example, the multiplicative-group setup usually has you pick two primes $p, q$ with $q$ dividing $(p-1)/2$, and the embedding function $x \mapsto g^x \mod p$ where $g$ is an element of multiplicative order $q$ modulo $p$ (e.g. $g^q \equiv 1$ modulo $p$).

In the elliptic curve setup, you have a base point $P$ of order $q$, there is no small-$p$ and the embedding function is $x \mapsto x \times P$.

The important mathematical structure here is that the target of the embedding function is a vector space (of dimension 1) over $\mathbb F_p$ and in this model, the embedding function is linear. That lets you work out a lot of things.

I know of several projects that have done various secret-sharing stuff in the multiplicative-group setting, a lot of them concerned with electronic voting, and all of this should port almost 1:1 to the elliptic curve setting. In fact I wish people would do this. You can indeed generate a (Shamir) secret-shared secret key among some authorities, everyone publishes their local public key and then one computes the global election public key as a linear combination (which is what Lagrange is doing) $Y = \sum_i c_i \times Y_i$ where the $Y_i$ are the local public keys.

In principle you could define a product $\otimes$ on the target space (e.g. the curve) via $(x \times P) \otimes (y \times P) := (xy \mod q) \times P$ since the embedding function is bijective. This makes the target space into a ring and should have most of the properties that you need to do things with polynomials there, answering SO's question (I think). The practical problem here is that actually computing this product is equivalent to solving CDH. This should not be a problem in two cases though: (1) in a security proof where you just want to reason about things, (2) in a secret-sharing scheme where the parties who want to compute this product hold the necessary preimages in the finite field.

EDIT

It should all still work fine. For example:

Over a finite field you can $(k, n)$ share a secret $s$ by setting $a_0 = s$, picking $a_1 ... a_{k-1}$ at random and creating the shares $s_i = \sum_{t=0}^{k-1} a_t i^t$. To recover from $k$ shares $(i, s_i)_{t=1}^k$ you compute $ \sum_{t=1}^k \lambda_t s_t$ where the $\lambda_t$ are the Lagrange coefficients.

If your secret $S$ is in the curve, and if you can pick random curve points $A_1 ... A_{k-1}$ then you can create shares by $S_i = \sum_{t=0}^{k-1} [i^t] A_t$ where $[t]A$ denotes scalar multiplication for a scalar t and curve point $A$.
The recovery formula is $S = \sum_{t=1}^k [\lambda_t] S_t$. The reason this works is that both the $i^t$ and the $\lambda_t$ are scalars so you're never multiplying curve points.

(You can create a random curve point by picking a random scalar $r$ and computing $[r]P$. Creating a random curve point where you don't know the dlog is harder, but unnecessary here.)

What's going on under the hood here is that, since every curve point has exactly one discrete logarithm, we can define $s$ such that $S = [s]P$ and $a_1 ... a_{k-1}$ such that $A_t = [a_t]P$ where $P$ is the base point. Using linearity, the way we create the shares is thus $S_i = \sum_{t=0}^{k-1} [i^t a_t] P$ so if we choose $s_i$ such that $S_i = [s_i]P$ then for recovery we get $\sum_{t=1}^k [\lambda_t s_t]P = [\sum_{t=1}^k \lambda_t s_t] P$. But the coefficient in the brackets here is exactly the recovery formula for secret sharing over a finite field, so we recover $[s]P = S$ as expected.

(This is incidentally also an example of how you can happily reason about taking discrete logs in security proofs.)


What is the simplest digital signature algorithm known? The hardest part about this question is explaining what I mean by simple. I'm measuring simplicity as, simply, the amount of lines of code it takes to implement that algorithm in a simple programming language - say, the untyped lambda calculus, Scheme, vanilla ES5 JavaScript. Of course, this is not possible to measure directly, but some things are just obvious. For example, any algorithm depending on any kind of algebra (multiplication, exponentiation, division, modulus, whatever) is not simple because implementing Bignum takes an obscene ton of lines itself!

For example, this wikipedia article claims the Schnorr signature is the simplest known scheme, polluting the Google results with such a blatantly wrong claim, because this proposal can clearly be implemented with much less code in absolutely any language without native big-integers.

That is why ECDSA, DSA, RSA aren't simple, they depend on way too many number-theoretic functions. I'm looking for a signature scheme that emerges from some kind of natural process, for example, L-systems, cellular automatas. Those are truly simple to implement in any kind of language, no dependencies!

So, what is the simplest digital signature algorithm known?

Let's first clear up one thing. We want a secure signature scheme. (And by secure, we mean a scheme that is widely accepted as being secure by experts in the field, that is, cryptologists.) That means we can restrict attention schemes from the cryptographic literature that have reasonable security arguments, which rules out most stuff based on cellular automata etc.

There are as you say many notions of simplicity.

If you want to measure lines of code, you could begin by noting that any reasonable signature scheme will almost certainly employ a hash function. Which means that signature schemes based on hash functions should be fairly compact, especially schemes like Lamport one-time signatures. If you want to move beyond one-time schemes, things become more complicated, but perhaps not too much as measured by lines of code.

However, many languages today provide built-in (or nearly built-in) bignum arithmetic, which means that a scheme like Schnorr suddenly becomes extremely easy to implement, once you have a hash function implementation.

An even simpler scheme (probably) is RSA-FDH, which is nearly trivial once you have a hash function implementation and bignum arithmetic.

Another interesting metric is understanding, either the mechanics of the system or its security. On both of those metrics, RSA-FDH scores extremely high. All you need to understand the mechanics of the system is basic number theory. The intuitive security argument is easy to understand. The security proof is also fairly easy to understand (once you understand the intuition behind security proofs and random oracles).

The mechanics of Schnorr signatures are somewhat more complicated, especially if you use elliptic curves. I hesitate to say anything at all about the intuitive security of Schnorr signatures (I find that the only intuition is that its security is non-obvious). The security proof is much more complicated than the RSA-FDH proof.

Some schemes based on bilinear pairings are deceptively easy to describe, but only if you hide most of the complexity involved.

The mechanics of hash-based signatures are often fairly involved and complicated, and the security proofs I have seen have been fairly complicated.

A third metric is how easy it is to make a secure implementation. This is equivalent to a huge can of worms, which among other things involves your entire tool chain. You may suddenly find that your actual cryptographic schemes matters much less than the language you write in. Historically, Schnorr-like schemes have proven very difficult to implement, while something like RSA-FDH should be much easier. (However, I am not an implementation expert, so don't trust me here.)


Preferred SHA-2 hash algorithm for MGF1 in RSA Does it make any difference to the security and efficiency if we use SHA-256 or SHA-512 for the Mask Generation Function MGF1 that generates the masking / padding within the OAEP encryption scheme and the PSS signature scheme?

A lot of implementations also seem to sport support for SHA-224 and SHA-384 for MGF1. Does it make any sense to use these truncated hash functions for something that needs to generate a mask of a particular size (close to the size of the key size for RSA)? Or would that simply add unnecessary overhead?

It seems to me that SHA-512 would be more efficient because of the output size alone. However, most implementations seem to default on SHA-1, SHA-256 or the same hash as used to hash the data for PSS.

Since the input sizes are fixed, length-extension attacks are not relevant, so any of the SHA-2 functions reasonably implements the random oracle model assumed by OAEP or PSS via MGF1—even the default of SHA-1 works with MGF1.

Obviously it will cost slightly more to use SHA-224 or SHA-384 than to use SHA-256 or SHA-512 because SHA-224 and SHA-384 are effectively truncations of SHA-256 and SHA-512: to get the same amount of output as (say) twelve SHA-384 invocations each costing a SHA-512 computation, you could pay for a mere nine SHA-512 computations instead.  So the truncated options don't provide any benefit.  And, of course, SHA-512 than SHA-256 is generally faster on CPUs with 64-bit adders.

All that said, it is hard to imagine that this could substantially affect security or performance since you're about to do a 2048-bit modular exponentiation anyway, which will be the bulk of the cost—but, of course, you're in a better position to do that measurement in your application!  (Make sure to choose $e = 3$ to minimize time spent in exponentiation.)


securing the keystore When generating a public-private key pair you have the option to secure the keystore with a password.

where is that password stored, is it a hashed version that is stored and if that is so which hashing algorithm is used ?

There are a lot of fancy things one can do when we start talking about sharing access a key store that Maarten mentions in this comment. I'll stick with just a very simple setup. You have a private key file (e.g., ssh private key). You don't want that file accessible to an attacker who steals your laptop, so the software asks you to supply a password to control access to that file.

The way these typically work is that symmetric keys are generated using your password (e.g., using bcrypt or PFKDF2). The keys are then used to encrypt the private key file. This would be done using an authenticated encryption mode of operation. These modes produce the ciphertext and a tag, which can be used to ensure that the ciphertext has not changed (note: a MAC like HMAC over the ciphertext would also work).

Now, when you supply a password again in the future to decrypt the file, the software runs that password through the same function to generate a key. If the same password is supplied, the same key is generated. Then it can attempt to decrypt the file. If the wrong key is supplied, or the ciphertext has been altered, decryption will fail due to the mode of operation used.

So it is the authentication tag over the ciphertext that is used to determine if either the wrong password was supplied or the ciphertext was altered.


How to provide encryption of user's data that can be performed by multiple (specific) users? Let me explain my dilemma. I'm a software developer and I'm writing a Windows application that should provide encryption of user's data. There could be multiple users in the database, each having their own username and password.

I currently encrypt data as such:

When a user logs in, I use PBKDF2 to authenticate their user name & password.
If login succeeds I keep the hash part from PBKDF2 in RAM & use it later as a key to encrypt and decrypt that user's data using AES-256 algorithm.

This seems to work, except that I now have a new set of requirements that don't work with my scheme above:

There are two types of users: employees and administrators.
Employees can access only their own accounts.
Administrators can access accounts of any other non-admin users.
When new administrators are added, they too should be able to access data of existing non-admin users.

So I was trying to devise a plan for encryption but I can't seem to figure it out.

Any suggestions?

First of all, reuse of keys for multiple purposes is severely frowned upon when it comes to key management. If you just derive a single secret from PBKDF2 for authentication then you can still split it further into multiple keys / password hashes using a KBKDF such as HKDF.

Furthermore, if you want to decrypt data with multiple keys then you can simply create a random "data key" and encrypt that with the keys required.

If the key is a symmetric key then that key may however not be available, especially for the administrators. In that case you could just encrypt with a public key of a key pair generated for that administrator. You can encrypt the private key of that key pair using the symmetric key derived using PBKDF2 and the KBKDF. That way you only need the admin to log in when decryption is required instead of for encryption and decryption.

That said, I'd strongly advice you to hire a data encryption expert if you've got these kind of questions. There may be a lot of other requirements to secure the system.


Using hash of plaintext as nonce in NaCl secretbox- bad idea? I need a nonce to encrypt my stuff using NaCl secretbox. I will be transmitting the nonce along with the ciphertext, which I have been told is OK to do. It occurs to me that one could simply use the hash of the plaintext as the nonce instead, since it will not collide and is easily accessible (I need to generate it anyway for something else). Somehow this strikes me as a possibly risky idea. Is this a bad thing to do?

In the traditional sense, a nonce is a number that is only used once (with the same key). Though occasionally there are other requirements. For example, we may require that the nonce be unpredictable. For more on this I recommend you read this answer and this answer.

Now, you don't go into enough detail on what you are doing to say whether or not you need unpredictability of the nonce. A hash of the plaintext (depending on how long the plaintext is) will not get you unpredictability. So, if you are using CBC mode, this is definitely risky.

More importantly, however, it is not clear whether you really get the "number used only once" property with your proposal. Will the same plaintext ever be sent encrypted with the same key? If the answer is that is it possible, then your idea is a bad thing to do. Exactly what the outcome would be depends on application level details (most importantly, what block cipher mode you are using) that you have not provided.


Tls 1.3 ClientHello legacy_session_id as zero length vector alignment Looking at tls 1.3 draft 23: https://tools.ietf.org/html/draft-ietf-tls-tls13-23

Section 4.1.2 shows, for a freshly established connection (no previous session from tls 1.2 or earlier) the legacy_session_id for ClientHello must be a zero length variable vector, which allows a max length of 32.

My interpretation of section 3.3 makes this zero length vector a single byte of value 0, followed by a zero byte-length entry, ie followed by nothing.

This seems to misalign structs comprised of the ClientHello. Is this correct?

Yes exactly. Nothing in the TLS spec is ever required to align on a boundery of a power of 2 in fact.


Using single EC cert/keying material to derive symmetric encryption key (for storage)? The situation involves a single party (single certificate) who would want to AES encrypt a file that they can later decrypt. Assume the EC certificate + EC keys have a purpose i.e. "File encryption" (similar to EFS perhaps), issued to a human ("Mr CSO") or an application ("My cat photo app"). Certs would be off existing organizational PKI.

EDIT: Certificate's are involved as there is already a PKI being maintained. We'd like to reuse that instead of introducing another (AES)-Key-Infrastructure. The AES key is encrypted in file header and it later decrypted via the private key. It's a usability issue.

EDIT#2: It's a storage use-case, the receiver IS the sender, timeshifted. Storage medium itself is untrusted. Actually the signature might be an overkill since the internal AES is authenticated AES.

With RSA Certs, at an abstract level can be as simple as

AESKey=KDF(nonce)
AESKey_encrypted = RSA_Encrypt(public key, AESKey) ---- (1)
AESKey_signed = RSA_Sign(private key, AESKey)      ---- (2)

File = AESKey_encrypted | AESKey_signed | AES(File_clear, AESKey)

FYI, the AES is authenticated AES which is why there is no separate HMAC. Anyway, a customer wants Elliptic curve crypto (the 521p curve) instead of RSA. The EC counterpart for (2) is clear (ECDSA) but the EC counterpart for (1) is something I'd like to hear from you guys. Any other comments also appreciated. Just to remind, there is no 2nd party/2nd party's cert.

Finally, any algorithmic concerns on mixing public key + bucket of bits AND private key + same bucket of bits (1, 2 above)? To the best of my understanding, those interactions have no proven algorithmic or structural weaknesses.

You can use ECIES, though it's not widely implemented.


I want to know the hardness of computing a or b given $g^{b^{-1}}$ and ab in cyclic groups with large prime order $G$ is a multiplicative cyclic group of a large prime order $p$ and $g$ is a generator of $G$

Theorem 1: Given $g^{b^{-1}}$ and $ab$, it's hard to compute $a$ or $b$, where $a$ and $b$ are randomly picked in $Z_p$
Theorem 2: It's hard to distinguish between the following distributions: $(g^{b^{-1}},ab)$ and $(g^{b^{-1}},z)$ where $a$, $b$, and $z$ are randomly picked in $Z_p$

Is there any proof that these two theorems hold or do not hold?

Theorem 1 is not true in general; consider a group where the discrete log problem is easy.
On the other hand, it is true if we assume that the discrete log problem in $G$ is hard (that is, if we can recover either $a$ or $b$ given $g^{b^{-1}}, ab$, then we can use that as an Oracle to recover $x$ given $g^x$)
Theorem 2 is true; for any $b \ne 0$ (and we know $b \ne 0$ if $b^{-1}$ exists), the distributions of $ab$ and $z$ (for random $a, z$) are identical (and hence "hard to distinguish").


General factoring and one-way functions Let a function $f$ be one-way, if there exists a probabilistic polynomial time algorithm to find the preimage of $y = f(x)$ for uniformly chosen $x$ with non-negligible probability.

Define the function as $f(x,y) = x\times y$, where the values of $x$ and $y$ range across the integers in $[2^{n-1}, 2^n-1]$ (basically, they are $n$-bit numbers with the left-most bit set). Is $f$ one-way??

(Although with probability 0.75 the received $y$ is even, $2$ and $y/2$ cannot be output as the factors, since I want the preimages to lie in that specific range)

What you are wondering about is the difference between weak one-way function, and strong one-way function. Google should give you the definitions (e.g. here is the first link I found). The factoring function for general inputs is not a strong one-way function, since there are outputs for which it is easy to invert. But it is a weak OWF, because no polytime adversary can have more than a probability $1-1/\mathsf{poly}$ of inverting it (as far as we know).

Furthermore, even though a weak OWF is not a strong OWF in general, we know a generic way of building strong OWFs from weak OWFs - in other words, both assumptions are formally equivalent. See e.g. this online course, that deals specifically with the product function which you care about.


Where can I find source code for ideal world simulation? In many crypto papers I see they use a Real World / Ideal World Paradigm.  However, I have never see the source code of such Simulators that try to simulate the adversary.  Could somebody point me to source code that simulates an adversary in the ideal world? How does this code look like  ?

An example of a paper that uses this paradigm is on pg. 1244 of this paper.

There is no source code to simulate this. It is a theoretic construct used in security proofs. Cryptography is often about the very limits of what could be calculated. This is quite far from actual programming source code.

For example, quite often something is called "efficient" in cryptography, if the algorithm runs in polynomial time (for some parameter). However, if the source code of a program actually requires $n^{1000}$ seconds then it still runs in polynomial time, but it is not possible to calculate it for $n=2$ (over $10^{293}$ years).

The adversary can not be represented by a specific algorithm, but the adversary is the union of all polynomial time algorithms (or said differently: He is limited to poly-time algorithms, but not specified which algorithms).


Is a 1024-bit DSA key considered safe? I created my PGP key in 2000. I’ve revoked the older, weaker sub-keys in favor of a 4096-bit RSA one, but the primary key is 1024-bit DSA. I read on Wikipedia that…

  NIST 800-57 recommends lengths of 2048 for keys with security lifetimes extending beyond 2010.

Should I consider my primary key insecure?
If so, is there any way to replace it without revoking my entire key and creating a new one?
If my primary key were compromised, the attacker would be able to create signatures as me, but they wouldn’t be able to decrypt information that was encrypted to my public key, right?

"Secure" is not a binary, black-and-white thing.  Instead, it's about risk management.  Instead of asking whether something is secure, it's better to ask whether it is "secure enough for such-and-such purpose". On the one hand, 1024-bit keys are uncomfortably close to what can be cracked, given lots of computational resources.  On the other hand, for casual use, it's probably fine, and there's no need to go through a painful exercise to replace your key.  But if you're generating new keys, these days it'd be a good call to use a 2048 bit key.

On your third question, someone who recovers your 1024-bit private signing key today would not be able to decrypt past ciphertexts, but they would be able to mount man-in-the-middle attacks on you in the future (which would let them decrypt information that anyone encrypts to you in the future), assuming they are willing to mount active attacks.


How to Prevent Correlation Power Analysis Attack on AES? Which techniques could be applied to AES to prevent these kind of attacks?

I can just think of creating noise with a parallel process for random computation, so the signals have the combination of that process and the crypto process.

DPA-resistant cores
Masking (attempt to conceal the intermediate date processed by modifying the data such that the complete secret is never processed simultaneously)

For example you can introduce s-box shuffling in AES as a software solution to decrease the likelihood that the attack succeeds.

Pseudo Code s-box shuffling from Figure 2 of www.indjst.org/index.php/indjst/article/download/61626/48132:

Begin
// The assignment of Round Key
Byte RK[11][16]
// The generation of Random Value
shuffle = rand()%8
// The execution of Key Expansion
KeyExpansion(Byte Masterkey[16], Byte Roundkey[11][16])
// The assignment of the execution of eight-shuffling AES
(*ptr_shuffle[8])(Byte PT[16], Byte RK[11][16], Byte CT[16])
ptr_shuffle[0] = &AES_Original1
ptr_shuffle[1] = &AES_Original1_Macro
ptr_shuffle[2] = &AES_Original2
ptr_shuffle[3] = &AES_Original2_Macro
ptr_shuffle[4] = &AES_Bertoni
ptr_shuffle[5] = &AES_Bertoni_Macro
ptr_shuffle[6] = &AES_T-Table
ptr_shuffle[7] = &AES_T-Table_Macro
// The execution of eight-shuffling AES
ptr_shuffle[shuffle](PT, RK, CT))
End


Security of using sha(secret + rand) I have come across some security implementations in which party A will compute MD = sha256(secret + rand) and transmit MD and rand to a counterpart B. If the second party knows the secret, then when it computes sha256(secret + rand), it will match that from sender A and validate it.

This may be a loaded question, but is this secure at all? Meaning, would it be very hard for an attacker to discover the secret given the resultant hash and the random number?

Part 2: Another potentially loaded question
Would it be more/less secure to instead use an hmac using the secret as the 'data'? So HMAC(rand, secret) ?

The goal of both security systems is to ensure that both A and B possess the same key K without transmitting it, but is either more secure? Are these implementations 'traditional' or more of a 'cluge'?

Using HMAC is more principled and flexible here, because HMAC with a random secret key is a pseudorandom function, while sha256(secret + nonsecret) isn't.

In your case where the non-secret is a random value there might not be a security difference. But I mentioned also flexibility, because this sort of authentication scheme—when implemented with a proper pseudorandom function like HMAC—doesn't need a random value.  A counter or wall clock time will do.  In fact, if you've seen those two-factor authentication tokens or apps that display a six-digit code that changes every minute, those are based on the TOTP algorithm, which is basically hmac(secret, current_time / refresh_interval).


Why is 0x10001 used as an RSA exponent so often? Are there any other commonly used exponents? Why are they selected?

Here is the beginning of that answer from info security stackexchange for the reader’s convenience:

  There is no known weakness for any short or long public exponent for RSA, as long as the public exponent is "correct" (i.e. relatively prime to p-1 for all primes p which divide the modulus).

  If you use a small exponent and you do not use any padding for encryption and you encrypt the exact same message with several distinct public keys, then your message is at risk: if $e = 3,$ and you encrypt message $m$ with public keys $n_1,n_2,n_3$ then you have $c_i= m^3 \pmod{n_i}$ and use the chinese remainder theorem to recover the message by a
  non modular cube root extraction.

  The weakness, here, is not the small exponent; rather, it is the use of an improper padding (namely, no padding at all) for encryption.


Online attendance system This summer I have made a website for my school's NHS program and integrated it with google scripts to automate tasks such as accessing how many hours users have and to allow members to view how many volunteer hours they themselves have earned. The next step I want to take is to automate the sign-in process for each student's attendance. I would like members to be able to come into a meeting, log in on their google account, and mark themselves as present on the website.

The problem is that I need a system such that members must be at the meeting in order to mark themselves as present. A simple code given at the meeting which members must enter on the website will not work, for members could text other members the code that was at the meeting, thus circumventing the whole system. It is really important that the system only allows people who are present to mark themselves as present since we have very strict attendance policies.

The system last year required students to mark themselves as present on a sign in piece of paper. Not only did trouble the officers with having to manually enter all of the attendance information in, but it also caused really long lines to form outside of the room just for sign-in.

Thanks in advance!

Generate a list of unique coupon codes in a format of your choice.
Print them out prior to the meeting /event/ ceremony. Like lottery tickets.
Hand them out to attendees, one for each kid. At the end I guess.
Each kid then later enters the coupon code into a website to confirm attendance.
Repeat prior to the next event...

There's a question here regarding preparation of coupons.  Just formulate your generation algorithm carefully to avoid BUMH0LEs.


Given a certain entrophy per character, how long should a passphrase be to guarantee key strength? Given an entrophy of 1.5 bits per character, how long does a passphrase have the be to guarantee a key strength of a 128 bit random key?

Assuming an alphabet of 26, one character takes log2(26)=4.7 bits to be represented. Given this entrophy of 1.5 bits per character, can one simply answer this by:

(128/4.7) * 1.5 = 40.85

Meaning that the passphrase will have to be 41 characters long to guarantee key strength?

No, your formula isn't correct. I don't know how you came to it, so I don't know what's wrong with your intuition.

You can check whether your formula makes sense with dimensional observation — it's the same kind of reasoning that helps a lot in physics. Write all numbers with their units:

entropy rate = 1.5 bit/character
random key size = 128 bits
passphrase length = X characters
information content per character in a 26-character alphabet = log2(26) bits/character = 4.7 bit/character

Your formula: $\dfrac{128\text{ bit}}{4.7\text{ bit/character}} \times 1.5\text{ bit/character} \approx 40.85\color{red}{\text{ bit}}$

We expected a number of characters, so something is wrong here.

In order to achieve the strength of a 128-bit random key, we need a total entropy of 128 bits for the passphrase. It's a simple proportionality rule:
$$
\text{entropy per character} =
\frac{\text{total entropy}}{\text{number of characters}}
$$
so
$$
X\text{ characters} = \frac{\text{total entropy}}{\text{entropy per character}}
 = \frac{128\text{ bit}}{1.5\text{ bit/character}}
 \approx 85.3\text{ character}
$$
Sanity check: the passphrase length turns up as a number of characters. Since the number of characters has to be an integer, it needs to be at least 86 characters long.

The size of the alphabet is irrelevant here because the passphrase isn't chosen randomly over all possible sequences of letters. “Passphrase” implies that it is a sentence fragment in a human language, or close enough. 1.5 bit/letter is a common estimate for the entropy per character for English: the number of English sentences of length $L$ is approximately $2^{1.5·L}$, so if you pick one at random, you have a $1/(2^{1.5})^L$ chance of being right.


2-round generalized Feistel network Write the decryption of a 2-round generalized Feistel network given below.

  $P_i$ denotes plaintext blocks of each 32-bits.
  $RK_i$ denotes the round keys.
  $WK_i$ denotes 32-bit keys applied only at the ﬁrst round (whitening keys)

  Continue the lines for the decryption.

  The whole ﬁgure will input 4, 32-bit plaintext, encrypt it for 2 rounds and continue with decryption and will output the same input

Can anyone help me for this question?

I will give the 1 round answer which will help complete the question.

Let $X_{1,i},i=0,\ldots,3$ be the 32-bit outputs of the first round, before the swap, numbered left to right. Then,

$$P_2=X_{1,2}, \quad P_0=X_{1,0}$$
and
$$P_1=WK_0\oplus F_0(RK_0,X_{1,0})\quad
P_3=WK_0\oplus F_0(RK_1,X_{1,2}),
$$
The equations for the $P_{i}$ are as above.


What's the generally accepted way of padding more than 255 bytes? There are plenty of popular padding schemes in use today. ANSI X.923 and PKCS#7 come to mind. However, all of them work on single bytes at a time. This is hardly surprising: padding for cryptographic purposes is usually just to 16 bytes and a single byte can hold the value 255.

I was wondering if there was any generally accepted method of padding when we need to add more than 255 bytes of padding. PKCS#7 obviously wouldn't work since you'd have to have multiple bytes for every byte normally. ANSI X.923 could be modified slightly to use more than one byte at the end to store the length of the padding, but this too comes with its own problems, namely that it doesn't work for every combination of inputs unless you do some dirty workarounds to manually take care of edge-cases, and even then I'm doubtful it'd work.

The solution I came up with was to simply run PKCS#7 multiple times. What I mean by that is if we want to pad 300 bytes, then pad up to 255 normally (by adding 255 bytes of value 255), then pad again up to 300 (by adding 45 bytes of value 45). When un-padding, you'd simply remove the top layer of 45 bytes, check to see if the next 255 values were all 255, and if they are, remove them all, and repeat.

I can't find a mention of anything similar to this, however, hence the question. Is there a standardized, accepted way?

Bit padding is one way to do this. There are also padding schemes that do pad using a special length encoding. This can be more efficient as you don't have to parse all the bytes. But in general bit padding should suffice.

Bit padding first (and always) adds a single bit valued 1 to the plaintext. Then it adds bits valued zero to the right until the length you require. It is extensively used internally for hash algorithms but sometimes it is also used for block ciphers. Unpadding consists of removing all zero bits from the right and then the one bit set to 1. This padding scheme is fully deterministic; it doesn't depend on the plaintext at all.

In bytes you get values such as:

6F 77 6C 73 74 65 61 64 - 80 00 00 00 00 00 00 00

for padding a value

6F 77 6C 73 74 65 61 64

up to 16 bytes (block size).

That means one bit set to 1 (byte 7, the highest bit usually), 7 zero bits to make a full byte and then any number of zero valued bytes.

It is easy to see that you can use this for any size of input, and any size of padding.

A variation of this scheme is to simply pad with bits that are a complement of the last bit of plaintext. Then you can just remove bits that are identical to the last bit. This scheme however depends on the plaintext, which makes it more cumbersome.


Why is symmetric lightweight crypto only about block ciphers and not about stream ciphers? Why is symmetric lightweight cryptography only about block ciphers and not about stream ciphers?
AFAIK stream cipher implementations cost at least three times less than block cipher ones?

Why is symmetric lightweight cryptography only about block ciphers and not
  about stream ciphers?

Why that assumption? There is a lot of work concerning stream ciphers for lightweight cryptography (LWC). You can find a relevant list here.

Plus, last week the ChaCha20-Poly1305 cipher suites (which are considered as lightweight) have been standardized in this RFC.


How to name a signature algorithm that has no hashed component I have an API-based service that digitally signs messages with RSA or ECDSA (system decides during runtime). The input is base64 encoded SHA-256 hash and the output is:

signature of this hash
signature algorithm, something like: "SHA256WithRSAEncryption" - to indicate if RSA or ECDSA was used by the system.

I now want to add functionality to also allow authentication (using a different certificate pair). For authentication, I don't want users to hash anything, I want the clients to generate random bytes with length (256/8)=32 and pass me the Base64 encoded version of this.

Now I have a problem how to correctly name the signature algorithm since the actual input is not a hash but random bytes. I was thinking like "Raw256WithRSAEncryption" to indicate that it wasn't a hash. But then I started to think if there was some hash algorithm that would actually return the thing itself, something like "Nohash256WithRSAEncryption".

If the RSA signatures you are doing are the ones standardly identified by the names you reference, corresponding to OIDs 1.2.840.113549.1.1.{2,4,5,11-16}, namely the scheme that was 'block type 1' in PKCS1v1 and retronymed RSASSA-PKCS1-v1_5 in PKCS1v2, it requires the hash algorithm identifier to be included in the padding; see step 2 of 9.2 in RFC8017 and the Notes on the following page, or the equivalent sections in earlier versions. Thus you cannot have an v1_5 signature which does not identify a hash algorithm, even if you didn't actually use that hash in computing the signature. (This is why openssl pkeyutl -sign for RSA with padding specified or defaulted as pkcs1 requires you to specify -pkeyopt digest:name to get the correct result even though it doesn't actually do the hash.)

For ECDSA (and DSA) although the standards (FIPS 186, X9.62, SEC1) require using a suitable hash, it is technically possible for the algorithms to generate and verify signatures using any bitstring of the correct size (not necessarily from any hash algorithm). FWIW, the usual Java cryptoprovider(s) -- Sun/Oracle/OpenJDK SUN and SunEC -- provide these as "NONEwithDSA" and "NONEwithECDSA" (casing only nominal, because in JCA algorithm names are case-insensitive), and BouncyCastle provides nominal "NONEWITHDSA" and "NONEWITHECDSA" with the former also aliased as "RAWDSA"; these do not have corresponding OIDs. IBM might be different, as might Android.

(Bouncy actually also provides "RSA" aliased as "NONEWITHRSA" and "RAWRSA", but as above they produce nonstandard and noninteroperable results, unless you handle the DigestInfo encoding yourself. And SunJCE and Bouncy support as a Cipher (not Signature) different versions of the semantically wrong but traditional "RSA encryption with private key".)


What is the most practical fully homomorphic cryptosystem? Craig Gentry recently gave the first fully homomorphic cryptosystem. Quite a bit of work has been done since extending his work. It seems, however, that no system is practical for real world use.

What are the current roadblocks making FHE impractical?
Which proposed system would you say is currently the most practical?

Bottom line. The short answer is that none of them are practical ... yet.  But there is a lot of active research, and if we're lucky, maybe that will lead to enough improvements that it might become practical.  We'll see.

More information. You can find some useful information at the following questions:

What Partial Homomorphic Encryption implementations exist and how do I leverage them? discusses some schemes that fall short of being fully homomorphic but are more practical and are enough to be useful in some settings.
In what ways does Full or Partial Homomorphic Encryption benefit the cloud? discusses applications of fully homormophic encryption and links to some papers that discuss the state-of-the-art and how practical the best schemes are.

These resources may be of interest:

Shai Halevi's Homomorphic Encryption Tutorial, presented at CRYPTO 2011.
Helger Lipmaa's collection of research papers on fully homomorphic encryption.

See also the following research papers:

Kristin Lauter and Michael Naehrig and Vinod Vaikuntanathan.  Can Homomorphic Encryption be Practical?
Jean-Sebastien Coron and David Naccache and Mehdi Tibouchi.  Optimization of Fully Homomorphic Encryption.
Marten van Dijk and Craig Gentry and Shai Halevi and Vinod Vaikuntanathan.  Fully Homomorphic Encryption over the Integers.
Damien Stehle and Ron Steinfeld.  Faster Fully Homomorphic Encryption.

This is a rapidly-evolving space, so anything I write here may become out of date quickly.  You will need to follow the research literature to learn the latest and greatest.


In laymans terms, what exactly is a "One time pad"? Background

I am an undergraduate novice learning about cryptography. Recently my professor introduced us to the concept of a "One time pad".

According to my professor:

  A one time pad is a cipher that exists when one unique key is used
  once to encipher/decipher one message. It is also the only genuinely
  unbreakable cipher.

However, this simple definition seems a bit anti-climatic for describing the world's "best possible cipher" - and has left me with some lingering questions.

Questions

1) Does that mean that if I encrypt the message Hello World with the key Password123 - that this would be considered a one-time-pad?

2) What if I encrypt two different messages Hello World 1 and Hello World 2 with the same key Password123 - is this no longer a one-time-pad?

3) What if I repeat the previous scenario with a small twist. Still encrypt two different messages with the same key, but introduce a salt Password123 + [SALT] - are we now back to being a one-time-pad? (keep in mind, I am assuming the salt is sent alongside the encrypted text).

4) Does the strength of the cipher even matter as long as one unique key is used once to encipher/decipher one message. Would a one-time-pad using AES have the same strength as a one-time-pad using ROT?

So in terminology that a novice or layman like me can understand. What exactly does it mean for a cipher to be a "One time pad"?

I'll answer your questions (1, ..., 4) first:

  1) Does that mean that if I encrypt the message Hello World with the key Password123 - that this would be considered a one-time-pad?

No. The one time pad (OTP) requires the key to be truly random - otherwise it's guessable. And encrypt is vague - this could be any cipher.

  2) What if I encrypt two different messages Hello World 1 and Hello World 2 with the same key Password123` - is this no longer a one-time-pad?

No - this is called a multi time pad and is crackable. And the OTP needs the key to be the same length as the message.

  3) What if I repeat the previous scenario with a small twist. Still encrypt two different messages with the same key, but introduce a salt Password123 + [SALT] - are we now back to being a one-time-pad? (keep in mind, I am assuming the salt is sent alongside the encrypted text).

The OTP doesn't take a salt, though I suppose what you suggest is plausible. If the salt is different for each message, than that avoids multi-time pads, but sending it with the message isn't particularly secure. Like sending half a password. Plus you still have the plaintext-key length problem.

  Does the strength of the cipher even matter as long as one unique key is used once to encipher/decipher one message. Would a one-time-pad using AES have the same strength as a one-time-pad using ROT?

The OTP is a cipher$^1$ in itself. You don't use AES or ROT. And that voids the rest of the question.

The original OTP was based of the Vignère cipher. In Vignère, the key fred with message plaintext means that the key isn't long enough. Therefore, it repeats and becomes:fredfredf. Then, it's encrypted with a vigénere square, and you have the ciphertext.

The old OTP is almost identical; the key must be random though. Truly random. And the same length as the ciphertext.

The modern OTP is much simpler:

$C_i = (P_i \oplus K_i)$

Now you might wonder: that's so simple! Why don't we use it all the time? It is, after all, unbreakable.

The answer is because of its keysize. For a 5GB message (or file) you need a 5GB key. See the problem?

As an afternote, read Crypto101 (https://crypto101.io). It's a work in progress, (some sections simply contain TODO) but it'll be beneficial for anyone interested in cryptography.

$1$: The one time pad's status as a "cipher" is argued about all the time. I use that term here because it gets the meaning across.