Generating multiple keys based on same password I want to generate an encryption key for the user to encrypt their data locally before sending to the server. The server should not have any knowledge, nor be able to compute, this encryption key.

This encryption key should be deterministic, so that regardless of which device they're on, the same key is generated and stored locally.

This makes their password an ideal choice to generate a key from.

At first I thought, easy:

Given user inputted password uip:

encryption_key (ek) = sha256(uip);
password_sent_to_server (pw) = sha224(uip);

This way, the server can never know or receive the user's inputted password, and cannot compute the encryption_key.

However, after asking this question, I've been told to use a key derivation function instead.

The problem is, I'll now need two random salts to generate ek and pw. And these salts cannot be stored on the server. So that means I'll also need to generate two deterministic salts based on either the user's email or password.

What's the right way to go about doing this?

This answer recommends using the email as the salt. So perhaps:

ek = pbkdf2(uip, email, 1)
pw = pbkdf2(uip, sha256(email), 2)

(The sha256(email) for the second salt is questionable. Was just trying to get at a different non-random salt for the second one.)

This answer recommends using pbkdf2 to generate a 512 bit key and splitting it:

output = pbkdf2(uip, email, 1, 512);
ek = firstHalf(output);
pw = secondHalf(output);

Am I interpreting these answers correctly? Any commentary on either approaches?

Neither approach is particularly good because it depends too much on the PBKDF2 function. The PBKDF2 function should always be performed in such a way that the number of iterations (the work factor) is high.

Besides that, PBKDF2 should not be asked for more output than the internal hash function (usually SHA-1, so 160 bits / 20 bytes). Otherwise you give back a part of your advantage back to the attacker (this is an unwanted property of PBKDF2 itself).

You can perform the following on the client:

master = pbkdf2(uip, email, 2000, 256);
hash = hkdf(master, 'hash')
kenc = hkdf(master, 'kenc')
ciphertext = gcm-aes(kenc, message)

then send hash and ciphertext over a TLS encrypted channel to the server (obviously you do not want to leak the hash value to an attacker).

The server should contain a hash over the previously calculated hash value, storedHash = H(hashOrg). It can then do a (secure) compare with the calculated hash value calculatedHash = H(hashGiven) to perform authentication.

Because hash cannot be reversed to the master value (which is pseudo-random, with the strength of the password and the work factor combined), it can also not calculate kenc.

The additional hash on the server just puts a bit of distance between the hash send over the secure channel and the stored value. Otherwise retrieving the database is enough for an attacker to obtain hash and simply send that value to log in.

Note that PBKDF2 is computationally intensive. You can bring that down by choosing really strong passwords. You could also use an asymmetric key pair, pasting in the public or private key value when required.

The biggest issue is that you'd still need to trust the service, especially if you would use encryption in the browser. That is not something that is easily avoided. You can avoid some of this by having your server audited or by creating an open source client application and only put the code into a repository after a thorough review. But at some point the client will still have to trust you, the service provider. There is no known good way around that.

Your client application may implement a great encryption / authentication scheme and send the password together with the authentication code and authenticated ciphertext. Simple as that.

If your users wants encryption that cannot be decrypted by the service, he/she is better off encrypting with their own PGP public key, and pasting the result ASCII armored into some input form.


Beavers Triple Vs BGW Multiplication on MPC Typically MPC protocols that are secure against semi-honest adversaries recommend the use of the revised GMW multiplication protocol by Gennaro et al. This is not the case against Active adversaries where protocols of the likes of SPDZ, VIFF and Oralndi prefer the use of the well known Beaver's multiplication triple.

My question is the following:

Given that I could use for instance VSS to provide security against active adversaries in the case of Shamir for instance, why is Beavers triple the preferred method. Is it because the randomized factors $(a,b,c)$ can be computed before hand (offline) and hence I would have a faster multiplication protocol given that stuff like PRSS is available under this security model?

Yes, preprocessing Beaver triples in an offline phase leads to a faster online phase. The online phase of an AND gate requires just two openings plus local computations.

But there are other advantages as well. Define a "linear representation" $[x]$ to be any way of representing/distributing a value $x$ among parties such that the following properties hold:

The adversary's view of $[x]$ is independent of $x$.
Given $[x]$ and $[y]$, it is possible to compute $[x+y]$ via local computations only.
Given $[x]$ and $c$, it is possible to compute $[cx]$ via local computations only.
There is a protocol that opens $[x]$ to reveal $x$, even in the presence of an adversary (can be formulated for any adversarial model).

For example, Shamir secret shares are one possible linear representation, secure against semi-honest adversaries.

If you assume a setup phase in which parties obtain many Beaver triples $[x],[y],[xy]$ on random inputs, as well as many random $[r]$, then you can do MPC in a very straight-forward way.

This recipe for making an MPC protocol is appealing because you just have to define an appropriate linear representation and plug in. This is what SPDZ, MiniMAC, BDOZ, etc., do (plus other optimizations of course).

In particular, these protocols use a linear representation that is secure against a dishonest majority. If you use computational assumptions during the offline phase, then you can in fact generate such Beaver triples. If you just stick to the VSS paradigm then you cannot get security against dishonest majority.

For a good presentation of this MPC paradigm (abstract linear representations + pre-processed Beaver triples), I recommend the video lectures of Claudio Orlandi & Ivan Damgaard from the 2015 Bar-Ilan winter school.


Is this method of deterministically using CBC secure? I'm trying to design a deterministic encryption scheme to enable searching in untrusted databases with the smallest possible IV overhead on ciphertexts. I know it's very bad practice but unfortunately it's a business requirement, so I'm just trying to offer the best security I can under the circumstances.

Right now I'm thinking about a way of using AES-CBC deterministically. My idea is based on a scheme presented in Deterministic and Efficiently Searchable Encryption by Bellare, Boldyreva and O'Neill.

Given a plaintext $x$ that we need to encrypt deterministically, we first compute $MAC_{k_1}(x)$ where $k_1$ is a key used only in this step. Next, we take the bottom four bytes of the computed MAC, call them $y$, and compute $H(y)$ where $H$ is a public hash function (e.g. SHA-256). Truncate this computed hash and use it as an IV for CBC mode. The ciphertext is $y||CBC_{k_2, H(y)}(x)$. ($k_2$ is our encryption key)

This may seem convoluted (and it is) but I'm trying to think of a way to get around the equality leakage when a predicable IV is used with CBC. With a fixed IV, different plaintexts with the same first block will encrypt to ciphertexts with identical first blocks. With the above scheme, the only way for the first block of two different plaintexts to be equal is if their computed MAC values have the same four low-order bytes, which we expect to happen only after $2^{16}$ encryptions.

We can of course decrease the likelihood of a collision by using more than four bytes of the MAC, but for length-restricted environments four bytes might be acceptably insecure.

I'm wary of this construction because of how kludgy it seems - if there's an obvious flaw please don't hesitate to point it out.

Thanks for your help, all.

Your construction seems quite similar to SIV mode, except that you're using CBC rather than CTR mode for the encryption step and that you're truncating the MAC value to only 32 bits (and re-expanding it by hashing to derive the actual IV).

The only obvious weakness I see in your scheme is the shortness of $y$ and the consequent small IV space.  I'd prefer a 128-bit $y$, but even just 64 or 48 bits would at least be a considerable improvement over 32.
With a 32-bit $y$, not only are collisions likely after about $2^{16}$ encryptions, but with about $2^{32}$ encryption oracle queries an attacker could even arrange for a chosen message prefix to be encrypted with any possible IV, which would allow them to carry out block-by-block dictionary attacks.  Depending on your implementation setting, that many oracle queries may or may not be feasible, but it's a bit too close to a practical attack for me to feel comfortable about.

(Also note that this attack can be easily carried out against multiple target messages simultaneously with little if any extra effort.  In fact, if the attacker only needs to decode one message out of several, having multiple targets will speed it up.)

Other than that, your construction looks OK to me.  Note that you don't necessarily need to use a hash function for the IV expansion step: simply padding $y$ to a full cipher block and applying the block cipher encryption function would do.  This method of deriving CBC IVs from a nonce is even explicitly endorsed by NIST SP 800-38A in appendix C.


Why do m and m' both hash to H2? I'm trying to understand the following text:

I'm having trouble understanding why $m$ and $m'$ both hash to $H_2$. I tried doing truth tables for $m_1'$ and $m_2'$ given the equations but I don't seem to be getting anywhere with them.

Is it also possible to justify that claim with high probability that $m \neq m'$?

OK, lets go through this step by step:

Given:

$H_1 = E(m_1)$

$H_2 = E(E(m_1) \oplus m_2)$

and

$H_1' = E(m_2 \oplus E(m_1))$ because $m_1' = m_2 \oplus E(m_1)$

$H_2' = E(H_1' \oplus H_2 \oplus m_2 \oplus H_1)$ because $m_2' = H_1' \oplus H_2 \oplus m_2 \oplus H_1$

then substitute $H_1'$ in $H_2'$:

$H_2' = E(E(m_2 \oplus E(m_1)) \oplus H_2 \oplus m_2 \oplus H_1)$

then substitute $H_2$:

$H_2' = E(E(m_2 \oplus E(m_1)) \oplus E(E(m_1) \oplus m_2) \oplus m_2 \oplus H_1)$

and $H_1$:

$H_2' = E(E(m_2 \oplus E(m_1)) \oplus E(E(m_1) \oplus m_2) \oplus m_2 \oplus E(m_1))$

re-arrange the parameters of XOR:

$H_2' = E(E(E(m_1) \oplus m_2) \oplus E(E(m_1) \oplus m_2) \oplus E(m_1) \oplus m_2)$

now we can see that two parts can be stricken out:

$H_2' = E( \require{cancel}\cancel{E(E(m_1) \oplus m_2) \oplus E(E(m_1) \oplus m_2)} \oplus E(m_1) \oplus m_2)$

so we are left with:

$H_2' = E(E(m_1) \oplus m_2)$

meaning that $H_2' = H_2$.

Given that $m_1'$ and $m_2'$ are unlikely to be equal to $m_1$ and $m_2$ we can clearly see that many pairs of related, but different messages hash to the same result, creating collisions.

Here $E$ is of course the AES function.


Malicious Model and Arbitrary selecting inputs on MPC and PSI Imagine the following setting: a party considers a secret sharing or multiparty protocol that is secure against semi-honest adversaries. The adversary selectively chooses the inputs such that it could learn the inputs of its counterparts from what is derived from the output.

A simple example could be taken from any Linear Secret Sharing Scheme Alice secret shares $x$ and Bob $y$ and want to compute $x+y$. Under this scenario, Alice could choose $x=0$, so that she learns Bob's input.

A more complex scenario is what sometimes is described as the full universe attack on Private Set Intersection (the problem of 2 parties computing the intersection of their sets). The attack in this case is as follows: Alice holds a vector $X$ and Bob a vector $Y$, and want to compute the intersection $X ∩ Y$. In this case the attack consists on Alice replacing its set $X$ by a set $X'$ containing all possible inputs on the universe.

From my understanding of what the security definition of MPC is (and the use of an ideal functionality) this attack would be possible under a semi-honest model. My question is the following: Is such attack possible when a malicious adversary is considered? And more importantly, can I consider such adversarial behavior as malicious, or is it indifferent from the MPC security model?

From my understanding of the implications of a malicious adversary and the capabilities of protocols that are secure against malicious adversaries, such as BGW, SPDZ or MASCOT, such an attack would still be possible. However I have recently come across this work on PSI https://eprint.iacr.org/2013/515.pdf, where they classify such attack as a malicious attack, given that the adversary is manipulating its input to learn other parties inputs.

In general, such attacks are "allowed" in the malicious model. This is due to the fact that secure computation guarantees that the process of computation reveals nothing. A secure protocol should behave like an ideal model where a trusted party computes the result. Now, in some cases, this is a problem. However, in practice, in many cases it is OK.

Consider the case of PSI: in practice, the length of the inputs is known to both parties. Thus, it may not be possible for one party to input the entire universe (which may also be huge). Having said this, this is possible if a protocol is used that depends on the entire universe (e.g., PSI by running secure computation via a circuit that computes over vectors of bits, so that the $i$th bit of a party's vector equals 1 if and only if it has the $i$th element of the universe in its input). Formally, the definition of the functionality should express the size of the input and therefore make this clear. However, in reality, this detail is often overlooked in papers.

In short, this is a real issue and if you want to use MPC you need to understand the ramification of "maliciously chosen inputs".


Do test vectors ensure a cipher is free of backdoors? If a cipher implementation passes unit tests using test vectors from some trusted source (these for AES, for example), then can we say that it is fully conforming to the specification, and must have been implemented correctly?

Is it possible to backdoor a cipher (or hash function, I suppose) in such a way that it still appears to be correct and is compatible with different implementations of the same cipher?

This question was motivated by the advice given by figlesquidge in his answer to the question AES column mixing and S-Box confusion, where he says:

  Standard AES disclaimer: Given the questions you've asked, you should
  not implement AES yourself in a real-world system because there are
  lots of security considerations when implementing ciphers.

can we say that it is fully conforming to the specification, and must have been implemented correctly?

No.

  Is it possible to backdoor a cipher (or hash function, I suppose) in such a way that it still appears to be correct and is compatible with different implementations of the same cipher?

Certainly.

Say I have an function AES(k,m)=c where variables k and m are the key and the message respectively and c is the resulting ciphertext.

Now I could write my own AES as follows:

def mikeazo_AES(k,m):
    if k==0x12abed347816981812abed3478169818:
        return m
    else:
        return AES(k,m)

Thus, given a specific key, it will simply return the plaintext. Since that key is not part of the test vectors, they will all pass.

This will be compatible with all other implementations unless that key is hit. Since they are randomly generated, the probability of that happening is slim. This may not seem super useful at first glance, but as an attacker you could add in some sort of trigger mechanism to force keys to be the special key. You can presumably do this as you have already got your software on their system.

There are better back doors that could be inserted. See example in comments from CodesInChaos.


Distribution based integer factorization The past week I've been looking into - and playing with - algorithms for factoring RSA moduli.

From what I understand, it's important that the primes p and q are of the same magnitude as the square root of N, but they shouldn’t be too close. To find out how close p and q are to sqrt(N) in the real world, I've used OpenSSL to generate a bunch of numbers.

The following image shows a graph. The x-axis shows N, the modulus. The y-axis shows how far p is from the square root of N, in percentage. This graph shows values for 5000 128-bit RSA moduli.

What I find interesting about this graph is that if a 128-bit modulus starts with "20...", I know that p can not be further than 2 percent from the square root of N.

Do algorithms exist that make use of such distributions? What would be the best attack if I know in what range p is located?

Update

If anyone wants to replicate the graph or check for errors in my code, here is the code used for generating OpenSSL N,p,q pairs:

from os import system
import re

def tardReplace(reg,data):
    n = reg.findall(data)[0]
    n = n.replace("\n","").replace("\r","").replace(":","").replace(" ","").replace("\t","")
    return int(n,16)

modDict = {}
genBits = 128
genAmount = 5000

fileName = "generated/" + str(genBits) + "bitRSA" + str(genAmount)
outf = open(fileName + ".txt", "w")

for i in range(genAmount):
    system("openssl genrsa -out foo.key " + str(genBits) + "; openssl rsa -text -in foo.key > values.txt")
    with open('values.txt','r') as f:
        data = f.read()

    if genBits <= 64:
        modReg = re.compile("modulus: ([0-9]+) ")
        mod = modReg.findall(data)[0]
    else:
        modReg = re.compile("modulus:([ \n\r\t0-9a-f:]+)publicExponent")
        mod = tardReplace(modReg, data)

    if genBits <= 128:
        prime1Reg = re.compile("prime1: ([0-9]+) ")
        prime1 = prime1Reg.findall(data)[0]
        prime2Reg = re.compile("prime2: ([0-9]+) ")
        prime2 = prime2Reg.findall(data)[0]
    else:
        prime1Reg = re.compile("prime1:([ \n\r\t0-9a-f:]+)prime2")
        prime1 = tardReplace(prime1Reg, data)

        prime2Reg = re.compile("prime2:([ \n\r\t0-9a-f:]+)exponent1")
        prime2 = tardReplace(prime2Reg, data)

    outf.write(str(mod) + "," + str(prime1) + "," + str(prime2) + "\n")

outf.close()

system("sort " + fileName + ".txt > " + fileName + ".sorted.txt")

And here is the code for making the graph:

import matplotlib.pyplot as plt

with open('../../rsaGen/generated/128bitRSA5000.sorted.txt','r') as f:
    data = f.read().split('\n')

x = []; y = []

for line in data:
    if line == '':  continue
    n,p,q = line.split(',')
    n = int(n);     p = int(p);     q = int(q)
    p = min(p,q)

    sqrtn = n ** 0.5
    diff = sqrtn - p
    percent = (diff/sqrtn)*100

    x.append(n)
    y.append(percent)

plt.scatter(x, y)
plt.show()

The archetypal algorithms that could take advantage of $p$ being close to the square root of $N=pq$ is Fermat's factorization method; and some improvements thereof.

The basic Fermat factoring method makes about $(p+q)/2-\sqrt N$ steps. Applied to $N\approx 2^{127}$ and $p/\sqrt N\approx 0.98$ (as in the question) this is over $2^{51}$ steps. We have heuristic algorithms to factor any 128-bit RSA moduli much faster than that, and nearly as simple (e.g. Pollard's Rho), thus the method is worthless in practice even at the 128-bit level; that only gets worse when we increase the modulus to practical sizes, and compare to more powerful factorization algorithms.

There are improvements of the Fermat factoring method that still benefit from $p$ being close to the square root of $N$. They reduce the number of steps, by skipping most candidates, and performing table lookups rather than squareness tests. The gain is large, but severely bounded by available memory, and is not enough to become competitive at least for $N>2^{1023}$ and $|p-q|>2^{\lceil\log_2N\rceil/2-100}$ (the criteria in FIPS 186-4, with origin in ANSI X9.31:1988, that has plenty of headroom), which has overwhelming odds to be verified for random $p$ and $q$.


PGP-key-based authentication system Consider we implement remote service, which will be accessible via API(i.e. restful http or grpc). All users are authenticated via pgp keys and each user has pgp keypair.

How to implement authentication for such a service?

I see multiple approaches and I'm unsure which one to choose:

Convert keypair to X509 certificate, use TLS certificate authentication (1, 2) to authenticate users. Requires some fiddling on client side, also unclear how to convert.
Require users to sign timestamp on each request. Check that timestamp is close to current server time. Unclear if this approach is secure.
Give users expirable tokens, which are either stored in DB or have MAC, require users to attach token signatures.
Some better approach I cant think of

Sign a self-signed X.509 certificate using PGP signature generation.

Let the web user create a self-signed X.509 certificate and store the certificate and private key in a PKCS#12 key store. Then create a PGP signed container with this certificate included. Let the web server put it in a trust store after verifying & stripping the PGP signature. The client needs to configure the PKCS#12 soft token with the browser used (or the Windows store, if IE / Edge / another SChannel based browser is used).

You would need to provide guidance to the users on how to create the self signed certificate and how to put the self signed certificate and private key store in the local key store of the browser. You could also create an application to do this for the users.


Rationale of the SHA-256 sigma function definitions When the sigma functions are defined in equations (4.4) and (4.5) in FIPS PUB 180-4, the defined functions show the traditional sigma summation symbol, with limits 0 to {256} and 1 to {256}. The definitions, however, are in terms of circular right shift and XOR operations. Why is a summation symbol used here?

It is the naming of functions and the functions are already defined - rotations (ROTR) and x-ors ($\oplus$). There are two $\Sigma$ and $\sigma$ functions for SHA-256 and SHA-512 series. And, in Greek, the $\Sigma$ is capital of $\sigma$.

The upper index represents the SHA family as 256 and 512. The sub-index, selects the function. $\Sigma_{0}^{\{256\}}$ means the first $\Sigma$ function of SHA-256 series. Note the curly braces.

Note: the functions are started to appear with SHA-2 series. It is not listed with SHA-1, the document can be seen from archive.org


SHA-3 padding clarifications I am implementing the SHA-3 algorithm in AVX2 assembly. The part where I am getting confused is that the padding with 10*1. Now my understanding is that the
data message M first needs to be padded with a '01'bit sequence. So, N= M || '01'.

Next, for the moment, please assume that the implementation is for KECCAK[1024] which is sponge(KECCAK-p[1600,24],pad 10*1,576](n,d). This implies, all the packets P_{i} have to be 576 bits long (1600-1024).

Now, my confusion is when the incoming message M itself is of 573 bits length. Then, N=M || '01' becomes 575 bits length. Then, do I just pad a single bit '1'? This is not then 10*1. How does one handle this specific length message, please?

Any advice is welcome. Remain grateful.

10*1 padding does not mean pad with a "10", it means pad with a single bit, then as many 0 bits as is required to fill the rate, then set the last bit of the rate to 1. 10*1 padding needs at least 2 bits of padding, such as the case of 574 bits with a rate of 576, in that case you only have a single 0, which is then set to a 1 since it is the last bit.

If the message is 573 bits, you need 3 more bits, so you add your single bit, two 0s, then set the final bit to 1, which leaves you with a literal "101" padding.

You may also want to deal with the ambiguity of the digest size. Your specific parametrization specifically calls out a rate of 576, but KECCAK1024 strongly implies a 1024-bit digest size, but in this case it is your capacity. If you are using the capacity, you want it bracketed, like  KECCAK[1024]


Paillier's scheme generalisation Paillier's scheme assume has message and ciphertext space equal to $\mathbb{Z}_N$ with $N=pq$, that is $N$ is the product of two different primes.

Is there a way to generalise this for $N$ that is the product of many ($>2$) different primes?

Yes, Pailler encryption can be generalized to the product of more than two (distinct) primes, much like in multi-prime-rsa. We just have $N=\prod p_i$ with $i\ne j\implies p_i\ne p_j$. Each $p_i$ must be secret and uniformly random in some large interval. It we want to use $g=N+1$ as the generator (which is common) without an explicit check of its order, it remains enough to ensure that $2\min(p_i)>\max(p_i)$. For $n$ primes, choosing $p_i$ as a random prime in $(2^{1024-1/n},2^{1024})$ ensures that, and that $N$ is exactly $1024\,n$ bits, and may simplify code using the last section's speedup by making all the primes standard-sized. For a working random prime generator and reasonable $n$, odds of hitting two equal factors or enabling a Fermat factorization remain negligible.

For the other steps of key generation, and for decryption, it is enough to compute $\varphi(N)$ or/and $\lambda(N)$ correctly:

$\varphi(N)$ is the product off all the $(p_i-1)$
$\lambda(N)$ is the Least Common Multiple off all the $(p_i-1)$

There's noting special to do for encryption; in fact there is no way to recognize from the public key if $N$ is the product of two or of more large primes.

If we want a speedup at decryption, we have the option to compute $c^{\lambda(N)}\bmod N^2$ (which is where most of the computation effort is spent) by computing $c^{\lambda(N)}\bmod{p_i}^2$ separately for each $p_i$, and using the Chinese remainder theorem to obtain the final result. That works like there, except

for the moduli $r_i$ there, we use ${p_i}^2$
for their reduced exponents $d_i$, we use $\lambda(N)\bmod\lambda({p_i}^2)$, that is $\begin{align}
d_i&=\lambda(N)\bmod(p_i(p_i-1))\\
&=\left(\frac{\lambda(N)}{p_i-1}\bmod p_i\right)(p_i-1)
\end{align}$.

The speedup obtained by using the CRT is by a factor about $n^2/2$ (with classical mulmod algorithms of cost proportional to the square of the number of bits); that's about half the speedup in multiprime RSA, because in Pailler the exponent $\lambda(N)$ has about half as many bits as the modulus $N^2$, whereas in RSA the exponent $d$ has about as many bits as the modulus $N$.


Difference between special honest verifier zero-knowledge and zero-knowledge property Special honest verifier zero-knowledge and zero-knowledge property is defined as follows:

Special honest verifier zero-knowledge(SHVZK):There exists a polynomial-time simulator M, which on input x and a random t, outputs an accepting conversation of the form $(m_1,t,m_2)$, with the same probability distribution as conversations between the honest $(P,V)$ on input $x$

Zero-knowledge property(ZK): Let $(P,V)$ be an interactive proof system for some language L . We say that (P,V) is computational zero-knowledge if for every probabilistic polynomial-time interactive machine $V^*$, there exists a probabilistic polynomial-time algorithm $M^*$ such that the output of the interactive machine $V^*$ after it interacts with the interactive machine P on common input x is computationally indistinguishable from the output of machine $M^*$ on input x.

Assume, there exists a interactive-protocol $\pi$ for language $L$ which  is three move protocol that satisfies zero-knowledge property

Considering $\pi$, the difference between SHVZK AND ZK is Simulator is constructed for only honest verifier in SVZK, whereas in ZK simulator must constructed for even cheating verifier.

Can we say $\pi$ satifies SHVZK?. My doubt is
In SHVZK, simulator produces accepting transcript where as in ZK property there is no condition about acceptance of transcript generated by simulator.

"Can we say $\pi$ satisfies SHVZK?"

Yes you can. As any proof system which satisfies ZK property, also achieves SHVZK.

Regard to "My doubt is In SHVZK, simulator produces accepting transcript where as in ZK property there is no condition about acceptance of transcript generated by simulator."

Note that in the definition of ZK, it is mentioned that "Let $(P,V)$ be an interactive proof system". A proof system should be complete, meaning that a honest prover always convinces honest verifier, which implies that the proof should be acceptable. So, even if in the definition of ZK, clearly is not mentioned that the proof should be acceptable, but similar to the SHVZK proof, a simulated ZK proof should be acceptable by verifier.


What are the possible security issues when exporting a plaintext database to a file like this? Say I have plaintext database with key-value pairs of usernames and passwords. Then I iterate through the database, encrypt the passwords, and write the username and encrypted password pairs to file with a specific format: I would be storing the salt, IV, and an encrypted hash checksum (for authentication to file) in the headers. The rest of the file would be the username-encrypted password pairs. There are indicators that specify how many bytes the username and passwords are. What would be some of the security issues with this file format?

I'll start with the usual reminder: Please don't roll your own crypto, chances are you're getting it wrong.

For password databases, KDBX (KeePass' format) usually is a good example which you strongly should consider using. For an analysis of some format, also see "On The Security of Password Manager Database Formats" by Gasti and Rasmussen (PDF).

For understandability I'll quickly re-iterate your format more formally:

Header: $IV || \text{Salt} || E_{K,IV}(R||H(R)||0^{128})$
Data pairs: $\text{UsernameLength}||\text{Username}|| \text{PasswordLength} || E_{K,IV}(\text{password})$

where $E_{K,IV}$ denotes PKCS#7 padded AES-128-CBC encryption using the key $K$ and the IV $IV$ where $K$ is derived from $\text{MasterPassword}$ and $\text{Salt}$ as $K=H(\text{Salt}||r||\text{MasterPassword})$. The password is considered valid if the last header entry yields a consistent decryption. $R$ denotes a 256-bit random string and $r$ an 8-bit random string.

I'll start the answer with security issues of the format as stated and will conclude with potential security issues based on the information not given. The complete analysis is based on the recap I gave above, which is based on the comments given on InformationSecurity.SE, on the information from the question and the information given in the comments of this answer.

The first and potentially most devestating point: IV re-use. The scheme is re-using the IV for all encryptions which allows an attacker to detect the shared prefix between passwords. The mitigation is simple: Either use a well-established storage format, use a random IV for each encryption or encrypt the whole bulk data (including lengths and user names) in one go.

The second most interesting issue is that the lack of integrity protection. There is no authentication of the data, if an attacker changes any part of the ciphertext and the padding remains intact, the user won't notice that anything changed. This allows an attacker to run a denial-of-service attack on the user by cleverly introducing malicious changes into the plaintext, resulting in complains (caused by frustration of not being able to log-in) that your storage format is garbage, because the data won't be keepen and it could be leveraged to a scenario where the attacker can learn the password, by causing the user to reset his on a specific account and if the attacker broke the e-mail account he would know the new password without the user even suspecting an attacker sniffed the password. The mitigation is relatively simple: Use a well-established standard or use authenticated encryption (such as AES-GCM) paired with a proper alarming error message upon decryption failure like "this data has been maliciously corrupted".

The third security issue is the explicit length leaking. This scheme leaks the length of every single password, allowing an attacker to choose which to brute-force first and thereby easing up the attackers work significantly. The mitigation is again simple: Either use a well-established standard or do the encryption in one go over the entire data, so an attacker can't identify the exact lengths and where passwords start and end.

The last issue I could identify is that the username is leaked. This allows an attacker to potentially identify where the user is registered and run spear phishing attacks and / or brute-force attacks on the user. Additionally it may help an attacker to identify the user in leaked password dumps and use the file to recover possible password re-uses of this password (just try all sites you could identify with the otherwise leaked password and the given username). The mitigation is the same as for the previous point: Use a well-established standard or run the encryption over the entire data.

The scheme uses AES-CBC, which is completely unauthenticated which allows for many advanced attacks as detailed above, so the recommendation is to use authenticated encryption modes like AES-GCM, AES-OCB, AES-EAX or AES-CCM, which will take care of the authentication for you and use strong ciphers (e.g. AES).

The scheme uses very weak password based key-derivation, which requires up to 257 hashes and 4 AES encryptions to verify a password guess. This is extremely weak and allows for fast brute-force attacks on the master password, which is bad as many users will chose a weak password which requires few tries which will require a short amount of time, as 257 hashes and 4 AES encryptions are basically "nothing" to slow down a sophisticated attacker. The mitigation is clear as usual: Use a well-established format or use a strong PBDKF like Argon2, bcrypt or scrypt.

The header you're specifying lacks a mean to store parameters for password based key derivation. This implies that the scheme is vulnerable to simple progress of technology. To demonstrate the issue, simply look at TrueCrypt. It uses 1000 or 2000 iterations of a hash function for password based key derivation, which was fine a decade ago. The file format specification didn't allow for variable iterations and thus TrueCrypt is still using this low iteration count, resulting in minimal defense against password brute-force attacks. The mitigation is clear: Use a well-established scheme or store the parameters in your header.


Key Exchange & key Distribution in symmetric key cryptography I want to know whether there is a difference between key exchange & key distribution in private key cryptography as well as public key cryptography?
or is it the same term?

I think the difference between key exchange and key distribution can be very subtle, but it probably comes down to the former being an active way of "dealing" keys, while the latter is something that can be more passive.

I think a few examples may make this more clear.

Key exchange

Alice and Bob want to communicate over a private channel. They both know each other's public keys ($PK_A$ and $PK_B$), and Alice sends Bob a message, a content encryption key, which she encrypted using Bob's public key.

Bob recovers this key by decrypting it using his private key, tied to $PK_B$.

Alice and Bob now have a common content encryption key, which they exchanged.

Key agreement

Not really covered by your question, but mentioned by @SEJPM to be relevant, key agreement is very much like key exchange, except that the key as such never crossed the channel.

This for example happens in Diffie-Hellman key agreement, where both parties have (publically) agreed to use a generator $g$ and a modulus $p$. Alice and Bob respectively choose secret integers $a$ and $b$, and they exchange values $A = g^a \mod p$ and $B=g^b \mod p$. Both Alice and Bob can then calculate the same common key (they agreed upon a key) $K \equiv A^b \mod p \equiv B^a \mod p = g^{ab} \mod p$, which they can use (after using a key derivation function) for a symmetric cipher.

N.b., the difference between key agreement and key exchange might be vague, up to the point that the terms are used interchangeably.

Key distribution

Key distribution deals with the problem that if $N$ parties want to securely communicate with each other, without any other party eavesdropping on the conversation, $\frac{N\cdot(N-1)}{2}$ keys are to be distributed.

This is, for example, a problem in the key distribution in wireless sensor networks, or the Web of Trust in PGP.

For example in PGP, all participants have a public key, which they can use in a fitting key agreement/key exchange protocol to establish a private channel with another participant.

In wireless sensor networks, depending on the expected number of nodes, it is sometimes opted to pre-distribute (hence key-distribution) a list of symmetric keys.

Key distribution is thus more of solving a many-to-many problem, while key agreement and key exchange both cover the one-to-one problem.


Understanding $\varepsilon$-advantage in cryptographically secure deterministic RNG In Efficient and Secure Pseudo-Random Number Generation by Vazirani & Vazirani, it is stated that every pseudorandom number generator which satisfies the XOR Condition can securely output $\log n$ bits (where $\ n = |N|$). Such a condition is satisfied by the Blum-Blum-Shub (whose trapdoor is based on the quadratic residuosity assumption), thus up to $\log \log N $ bits at each step can be extracted.

My question is of information theoretic interest: what exactly do they mean when they state that the boolean predicates (the output bits) $b_1,\ldots,b_k$ are inversion secure if there exists a Las Vegas algorithm T that runs in probabilistic polytime, i.e $T^{O_{b_{i},N}}[i, E_{N}(x)] = x$ (with $E_{N}(x)$ the one-way function), where $O_{b_{i},N}$ is a $\frac{1}{2} + \frac{1}{poly(n)}$ advantage oracle for $b_i$ with respect to N?
Why the probability beyond 1/2 plus that $\varepsilon$-advantage, which, I assume, bounds the overall probability? So, if the XOR of each non-empty subset of these predicates is inversion secure,
boolean predicates satisfy the XOR Condition.

I think it's pretty close with what Rabin function says:

  If for a $\frac{1}{logN}$ fraction of the quadratic residues $q\pmod N$ one could find a square root of $q$, then one could factor $N$ in random polynomial time.

Still, where does $1/(\log N)$ come from?

Took a while to grasp it, but with the help of a friend we came to a conclusion (and it turns out it was rather easy).

Recall that a function $f_n : \{0,1\}^{n} \mapsto \{0,1\}^{m(n)}$ is said to be one-way if for a positive polynomial $poly(\cdot)$, every randomized algorithm running in probabilistic polynomial time inverts $f_n$ with a negligible probability, i.e.  $\Pr[A\:inverting\: f_n] < \frac{1}{poly(n)}$, with $n$ size of the input. This polynomial comes from the fact that for every possible computational path, the algorithm will follow it with a probability $2^{-n}$, which is bounded by $\mathcal O(\frac{1}{n^c})$ for every constant $c$. Clearly, we want the adversary's advantage to be as asymptotically small as possible.


What are the random variables in Universal Hash Function? Universal hash function is defined as follow:

$f_{(k_0,k_1)}(x) = (k_0\cdot x + k_1) \mod p$, where $p$ is prime

In Wikipedia, it is mentioned that the above function is pairwise independent. Pairwise independence is defined here

I wonder what are the random variables in $f$ and what pairwise independence means here.

The random variables are $k_0$ and $k_1$, typically taken to be uniformly distributed in $\mathbb Z/p\mathbb Z$ in this context.

(Sometimes we take $k_0$ to be uniform in $(\mathbb Z/p\mathbb Z)^\times$ instead, i.e. exclude $k_0 = 0$, but as long as $p \gg 2^{100}$ this is not important.)


Ring oscillator based PUF I am unable to understand why - using a counter comparison based ring oscillator PUF - the output bit is either 0 or 1.

Since the output is one bit I don't see how multi bit responses are obtained. Using this information how can I calculate intra- and inter-Hamming distance? Can you provide some provide example to explain it?

Using ring oscillator based PUF proposed by Devadas and Suh it compares counter values and then produces 1 bit of output. So from this one bit of output, how is it possible to get a multiple bit response to calculate intra- or inner-Hamming distance?

.

If I apply input of 1001010 it is input to two sets of ring oscillator each having 128 ring oscillator out of two set one from each a ring oscillator is  selected and feed to counter and comparator produces output 0 or 1.

So a single bit response is obtained But in the paper of Devadas and Suh : https://people.csail.mit.edu/devadas/pubs/puf-dac07.pdf in figure 4 for challenge  1001010 the response is 010101. How is this possible?

note: I am unsure that you can get an answer for your question as there's not enough technical information in the paper to reproduce (for me anyway) the results.  However, you could work through it in the following method for any ring oscillator.

A ring oscillator is comprised of a ring built of an odd number of inverters. The simplest model of this oscillator can be represented with a single inverting transfer function $f(\cdot)$, a delay of $\tau$ and a feedback loop that meet the Barkhausen criteria. The $f(\cdot)$ function can be approximated with a hyperbolic tangent. However, an electrical model must involve additional lumped components (low pass filter) namely the input capacitance $C$ and the output resistance R that represent inverter's active region behavior.  The $RC$ is particularly pertinent due to the FPGA architecture in this case.  The noise processes of the circuit are represented in the model by $N(t)$.

The purpose of the "PUF" in this case is to have unique delay, which is the $N(t)$.  The momentary $N(t)$) value results from the sum of Gaussian noise and two-way shot noise sources (it's not thermal noise, which is actually shot noise in a semiconductor and every textbook that says otherwise is incorrect.  You can derive it from 1st principles) with a zero mean value and ${\sigma^2_N}$ variance.

The ring oscillator manifests oscillations due to the propagation delay $\tau$ in delay in the feedback loop.  In the image, $\Sigma$ is the contributions of $N(t)$  You then look at this behavior as non-linear delay such that

$$ \widetilde{\dot{\mathbf{U}}}_i = \frac{f(\widetilde{U},t-\tau)-\widetilde{{\mathbf{U}}}_i+N(t)}{RC},$$

where $f(\cdot)$ is the transfer function.  The transfer function in this case is the PUF behavior, which the authors did not model.  Also, it would be dependent on not only the semiconductor fab mismatch, but the router.  The question is "does the RC of the routing contribute more than the PUF circuit variance".  There's no way to know.

What they should have done is the following:
Let's assume that randomness is a function of the nondeterministic contribution of N(t) and a derivative of the random variable $\widetilde{{\mathbf{U}}}_i$.  The behavior of the circuit can be explained when the random part in the above equation is omitted and a we can linearize it with a small signal model.  In this case, the linearized $f(\cdot)$ function brings an amplification coefficient g, therefore, the circuit can be described with a linear differential equation as

$$\frac{d u_i}{dt} = \frac{-g u_i(t-\tau)-u_i}{RC} $$

You can then take the above and put it through a Laplace transform and find the zeros resulting in

$$ s+ \frac{1+g e^{-\tau s}}{RC}=0$$

The solution can then represented as a Fourier series with periodic responses from the time domain.  You can then use these modeled for each oscillator in the chain to understand the contribution of each oscillator.   For this reason, I do not believe that their analysis is adequate enough to make assumptions about the hamming distance in any method that is qualitative.  It is a quantitate measurement, and I am not convinced by that paper that the authors know how their system works.

I have no idea why this paper is so highly cited.  I would not pass muster in a circuits journal, and honestly, it just complicates things.  You can already consider an inverter to have a unique transfer function due to surface roughness and manufacturing defects.  I do not know either of the original authors, but I would love to know why this was thought to be a good idea.


Sub exponentially hard OWF , PRF and iO I'm currently reading the work "Obfuscation of probabilistic circuits and Applications' by Canetti Lin Tessaro and Vaikuntanathan 2015. It says sub exponentially hard OWF implies
sub exponentially hard PRF ( puncturable PRF) and later again proves that sub exponentially hard PRF ( puncturable PRF) + sub exponentially hard iO $\implies$ pIO(probabilistic circuits).

I'm really confused with what the author means by the term "subexponentially hard" and is it a weather or a stronger assumption when it comes to the OWF or iO.

Thanks in advance

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

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

Similar definitions apply for the other primitives too.

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


How hard is it to generate a simultaneous MD5 and SHA1 collision? I was recently reading that MD5 is "broken" because it's pretty easy to generate collisions (like 2^(L/2)). And the SHA1 (theoretically) fares no better. The solution seems to be hash algorithms that are very slow in comparison.

I am wondering why can't people combine these fast algorithms to get the best of both security and speed? What would be the time complexity to generate a simultaneous MD5 and SHA1 collision? And if it's hard enough, would these make a viable candidate for collision resistant hash applications?

(By simultaneous collision I mean generating a string with same MD5 and SHA1)

Surprisingly enough, it would appear that generating a simultaneous collision wouldn't be that much more expensive than generating a single collision for SHA-1.

The basic idea is to form a $2^{64}$ wide multicollision on SHA-1; that is, $2^{64}$ distinct messages that all SHA-1 hash to the same value.  We can do this by using Joux's idea of forming finding 64 different colliding blocks $B_{i, 0}, B_{i, i}$ such that all sequences $B_{0, a}, B_{1, b}, B_{2, c}, ..., B_{63, z}$ all share the same SHA-1 hash; this can be done by finding 64 successive SHA-1 collisions.  The best estimate on finding a single SHA-1 collision is $2^{61}$ SHA-1 compression function calls (Stevens); hence the effort to find 64 such collisions is $2^{67}$ compression function calls.

Once we have such a $2^{64}$ wide multicollision, we just do an MD5 hash of each, and look for an MD5 collision; this takes $2^{65}$ MD5 compression function calls, and yields a collision with good probability.

This yields a simultaneous SHA-1 and MD5 collision with an expected $2^{67}$ computational effort.


Understanding the Definition of Most Significant Bits in the Hidden Number Problem Boneh's and Venkatesan's "Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes" defines the Hidden Number Problem (HNP). The HNP shows that computing the most significant bits of a Diffie-Hellman shared secret is as hard as computing the entire secret.

The paper defines the function $MSB_{k}(x)$ which I originally interpreted to be the $k$ of $x$ most significant bits (e.g. $MSB_{2}(13)$ should be  $11_{2}$). However, the paper uses the following definitions:

  Given a prime $p$, we define $MSB_{k}(x)$ as the integer $t$ such that $\left(t - 1\right) \cdot \frac{p}{2^{k}} \leq x \lt t \cdot \frac{p}{2^k}$.

  For convenience we will sometimes assume that $MSB_{k}(x)$ is an integer $z$ satisfying $|x - z| \lt \frac{p}{2^{k+1}}$.

I'm struggling with these definitions for a few reasons:

These inequalities can have a set of possible solutions but the $k$ most significant bits of $x$ should just be a single $k$ bit solution.
These definitions rely on a prime $p$ but $x$'s most significant bits are independent of $p$.

From my research it sounds like these definitions are a bit more "flexible" then the definition that I have in mind but I don't intuitively grasp how the flexible definitions relate to the definition have in mind.

Imagine you are working modulo the prime $p = 2^{255}+95$. Knowing the most significant bit, in the usual sense, of values modulo $p$ gives you almost no useful information—it's virtually always $0$. Knowing the $k$ most significant bits, in the usual sense, gives you roughly $k-1$ bits of information.

For the results to make sense over arbitrary prime fields, one thus needs a definition of most significant bits that is not affected by such quirks, and that's there the weirder definition of $\mathrm{MSB}_k$ comes in, which might be better understood as "suppose you know $k$ bits of information about $x$".


NIST STS incorrect results for sample files So I wanted to check the outcome of a hardware TRNG and see if its entropy is good enough. I downloaded the source files for statistical test suit from nist.gov website, compiled them on my macOS machine with clang and tried some sample data files as inputs to check that everything works correct before proceeding to the next step. However, when I used data/data.pi file as an input for STS, the very first result P-value was incorrect!

For a Frequency test it was 0.534146 while the paper from NIST corresponding to that suit stated that the Frequency P-value for pi should be 0.578211 ("Appendix B Empirical Results for Sample Data", page 107). Other results were also incorrect, no surprise. I double-checked the selected options, but they are the same: 10 streams for 100,000 bits and a total of 1,000,000 bits. I also checked configuration parameters in defs.h file, they all match the corresponding ones in the paper.

My first concern was that during compilation process there were some warnings from the compiler. It was mainly unhappy with some uses of 'fabs(x)' for integer-types variables instead of 'abs(x)' in some files. I changed the code but the resulting P-values were still the same.

Any idea what might be the source of the problem? Results for other sample files do not match too.

Thanks!

Don't worry about it :-)

The documentation is "Revised:April2010".  The latest code implementation is (officially) dated July 9, 2014 and commented as "This update has a few minor corrections to the source code. The first change corrects the non-overlapping template test to make it correctly skip bits when a sequence matches.  The second change is to correct the $\pi$ values in the overlapping template test."

The NIST programmers aren't the best, and there might be other later tweaks to the source code.  I don't know how many "few" is, and they don't say.  I haven't gone through all of the individual source files.  Revisioning comments are effectively non existent. Your compiler errors can be ignored, they're only warnings and my (and others) experience of the code is that it works if your samples are large enough. 1 million bits is a good starting size.

A P of 0.534146 is a good result, and shows $\pi$ passing your randomness tests pretty well. The other test files ($\sqrt{2}$ et al) should also give you almost perfect scores but might differ slightly from those documented.

It's just a minor bug fix.


Should I use NaCl or libsodium for my application? While looking for end-to-end encryption for my app users, I stumbled upon NaCl and libsodium. I am unsure from a security perspective which of these implementations I should use for my cross-platform app.

Are there big differences in the level of security they offer?

(I don't have an opinion on NaCl as I've never used it. My understanding is that Libsodium uses NaCl in parts, and/ or re-implements it in others.)

As far as security goes, they should both be as equally secure. As far as I know they are both opinionated in that they don't provide you with an option to use less-secure techniques. In virtually every cryptographic primitive you seek, you will only find one or two more recent and more secure (ie. best-practice). This link elaborates on some of the design decisions:

https://libsodium.gitbook.io/doc/internals#security-first

Here is a good resource on Libsodium from Paragon - if you're using PHP you'll no doubt wind up here as the standard doco is a whole bunch of 'todo':

https://paragonie.com/book/pecl-libsodium

You don't specify a language, however, I have used Libsodium successfully across numerous Linux kernels, in PHP, Python (pysodium), Javascript, Windows 8.1+, and Android 7+ (via Termux). I have also interchanged certain primitives from pysodium with another Python library called cryptography.io (which relies upon OpenSSL).

One thing I like is the way the library provides two interfaces in many circumstances: a 'generically named' function, and an explicitly named one. For example, you can call crypto_aead_xchacha20poly1305_ietf_encrypt which explicitly defines the cipher in use, or, you can call crypto_secretbox and allow your cryptography to be 'upgraded' in the future if a newer version emerges that modifies default behaviour.

One shortcoming I have discovered so far, at least for pysodium's use of this library, is that the api exposure for Argon2id doesn't support associated data, whereas the actual algorithm code-base in the library does:

https://github.com/jedisct1/libsodium/blob/927dfe8e2eaa86160d3ba12a7e3258fbc322909c/src/libsodium/crypto_pwhash/argon2/pwhash_argon2id.c#L136
https://github.com/jedisct1/libsodium/blob/a97ab7085fcda73f4fc7dead1a499025ceda9ecc/src/libsodium/crypto_pwhash/argon2/argon2-core.c#L470

In practice, this wasn't an issue, as I just hashed the associated data with the password - however, this might be a problem in some implementations, especially if you're producing a PBKDF in parallel with another library's so you can exchange data (in an end-to-end protocol for example). If you're using Python, you can use the argon2-cffi implementation in most circumstances.

The lack of AES-ECB and AES-CBC ciphers has prevented me from using Libsodium exclusively on one MySQL-integration project, however, it was no drama to use cryptography.io as a bridge in that circumstance. That is how I started looking at compatibility between Libsodium and OpenSSL (via pysodium and cryptography.io).


Use exported certificate with private key to logon using Kerberos First I just would like to mention, that my knowledge in windows authentification methods are very limited. So my question:

Is it possible to use custom credential provider in windows to log on, that accepts certificate, which I export from certificate store with private key.

As far as I know, Kerberos accepts username/password format and although certificate from smart card.

So my question is, how can I feed my exported certificate into Kerberos?

Note: The below holds assuming Microsoft did things properly and following. But Microsoft being Microsoft they didn't. Smart-Card (certificate-based) logon is only supported when using Kerberos thanks to the custom Microsoft extension to Kerberos.

  So my question is, how can I feed my exported certificate into Kerberos?

Short Answer: You can't.
Long Answer: Technically, you can.

To understand this, we need to take two detours: Namely the answer to your first question and to Kerberos. Let's do Kerberos first.

So, Kerberos is a (complex) protocol that allows a client to authenticate with a (sequence of) central server(s) such that at the end the client's actual intended communication partner can be sure of the client's identity and has a shared key with them. All of this while only the client has to establish connections with the central server(s) and while the only pre-shared keys are between each party and the central server(s). Now, Kerberos relies entirely on symmetric cryptography, so from a protocol point of view authentication via asymmetric cryptography isn't (directly) an option. I'm rather confident that Windows also doesn't support this natively (short answer).

However, the answer to your question

  Is it possible to use custom credential provider in windows to log on, that accepts certificate, which I export from certificate store with private key.

is yes. There is software that allows you to log-in to local Windows installations using a smart card and it's a built-in ability if the authentication is handled by a domain controller. Note though that using an encrypted exported private key isn't a sensible authentication method on its own, as you would be back to username (identifiying the relevant keyfile) and password (decrypting it) and would have gained nothing.

If you have a smart card and use this smart card to decrypt a windows password, then you can use this decrypted password for Kerberos authentication. Doing the first part is possible, as demonstrated by the software which feeds the password to the standard Windows login facilities after decryption for local logon. Doing the latter shouldn't be too hard. Please note that implementing this is likely a lot of effort and only potentially worth it in an environment where you cannot possibly switch away from using Kerberos to use "normal" domain-controller-based public-key authentication. This is why the longer answer is "you can".


What are implementations of PRNGs based on ChaCha20? I thought I'd find an implementation in NaCl, but /dev/urandom is what I find.  Search engines samples revealed most implementations are broken.

What libraries are there currently?  (I'm only interested in the PRNG based on ChaCha20.)

Beyond what specific primitive your system will be based on, there are important things to consider while building a CSPRNG.

Bernstein's Fast-key-erasure random-number generators article is a good starting point, as well as how randomness generation is done in Amazon S2N.

Buffer output, but erase data as it's being read, frequently rotate the key, mix multiple entropy sources if possible.

Libsodium provides a Salsa20-based CSPRNG implementation. It is not used by default, as for most applications, reading /dev/urandom is perfectly fine.

ChaCha20 can be a drop-in replacement for Salsa20 here.


Can a MAC be used as a HMAC? I am reading through an information security book right now, and a confusing question poses itself to me:

"Could you use a MAC as a HMAC? That is, does a MAC satisfy the same properties that a HMAC satisfies?"

The book then goes on to give a hint about how MACs are computed by CBC mode of a given symmetric block cipher that involves K the key, and to consider when K is known to an attacker for both HMAC and MAC.

Here's the confusing part: Isn't a MAC just a code created from a MAC algorithm, while a HMAC is a type of MAC algorithm? I do not see how any of these hints could be applicable to the question when a MAC and a HMAC are so clearly similar (to a novice).

Am I right in this thinking?

HMAC is a type of MAC. The output of a MAC is called a "tag". Not all MAC (algorithms) are HMAC.

MACs are not required to be one-way or collision resistant for someone who knows the key. HMAC, however, inherits the one-way-ness and collision resistance of the underlying hash function.

A CBC-based MAC is mentioned as a hint because it is almost trivial to find preimage values for any given tag value. That also makes collision attacks trivial.


Mitigating private key loss for the average non-technical user I'm developing software that will use public key encryption as part of its user identification, verification and data ownership processes. Assume that I have the user experience side of things worked out and that what I propose will work well within the design of my application; the question I have here is purely about the security side of things.

Private key loss is an awful thing to bear, if it means total loss of access to your data. You can print it out and store it somewhere safely, or put in a USB key and put that in a safe, or whatever, but the average user is not going to do these things. They don't understand security, and they won't usually make the effort to cover their bases. Even if they do, they may forget where they saved or stored their key, or they may lose it for other reasons.

My question is as follows:

Assume there is a network of people who know each other closely enough that they can pick up the phone (or Skype, etc.) and have a voice conversation. Am I missing any glaring security problems with the following?

On my local machine, my private key is divided into 3 parts. The key ABCDEFGHIJKL... becomes ADGJ..., BEHK..., and CFIL....
I select 3 people in my network (preferably each selected from a distinct social group that doesn't really overlap with the others), and encrypt one of the pieces of my private key with their public key.
I send each respective encrypted piece of my private key to the person whose public key I used to encrypt it, and it is stored in their local data store.

Catastrophe strikes! My private key is gone!

I generate a new temporary key pair.
I ask each of my 3 friends to decrypt their piece of my old private key and re-encrypt it using my temporary public key, then send the newly-encrypted version back to me.
I decrypt each of the three pieces and rebuild my private key.

I now have access to my data.

The solution sounds convoluted, sure, but as I said earlier, I have a way to handle the UX for this in a reasonably frictionless way.

The only issue I can think of is that a friend may lose access to their own data and then I'll be out of luck, but to mitigate that as an issue, I'll hedge my bets and perform the same process with different groups of 3 people.

Other things:

"3" is not set in stone, and can be adapted depending on the user's network size.
A user could leverage a service that uses 2-factor authentication as a stand-in for one of their friends. e.g. I could store one of the pieces unencrypted (but obviously useless in isolation) in my 2-factor-secured GMail account.

Can you see any issues with my approach, and if so, what could I do to achieve the same result in a more cryptographically-secure way?

Splitting your key by just splitting into partial strings (doesn't matter if it's every 3. symbol or consecutive symbols) is a terrible idea, because you hand out actual information about your key - to them and to everyone who compromises their system.

For RSA this is actually a real problem, because partial knowledge of the private key makes Coppersmith's attack possible. In the original attack the known bits had to be either the least or most significant bits, but the attack has been refined quite a bit. For example, Reconstructing RSA Private Keys from Random Key Bits by Heninger and Schacham (2009) just need a fraction of $0.27$ random bits of the private key and a small exponent. In that paper the related work section gives a good overview over previous works.

As a refinement for the splitting:
I suggest looking into secret sharing schemes (e.g. Shamir's secret sharing), so that at least no one with less than 3 shares can't recover any information about the key. But still, the security of your key becomes dependent of the other parties keeping your key secure and not be malicious. And of course you need a stragety to change your key and update their shares. Reasons for this might be that you want to change the list of trusted persons, one of them lost all the date on their computer, etc.

In general, the dependency on their security is a practical issue: If you use proper implementaions of current state-of-the-art encryption schemes, it is much more likely that key management and storage contains a security weakness than the actual encryption.

Regarding the last part: If you worry about one friend loosing his data at the same time as you (roughly the same time, before you could redo the splitting process), secret sharing schemes can be set up so that you need $k$ out of $n$ shares to recover the key. And it doesn't matter which $k$ of those $n$ shares you use.


Apply a permutation cipher by hand I did the following problem from the book "Cryptography Theory and Practice" as
I am doing some self-study.

Problem:

a) Suppose that $\pi$ is the following permutations of the set $\lbrace 1,\dots,8 \rbrace$:
$$ \pi=\begin{pmatrix}
1 &2& 3& 4& 5& 6& 7& 8\\
4& 1& 6& 2& 7& 3& 8& 5
\end{pmatrix}$$
Compute the permutation $\pi^{-1}$.

b) Decrypt the following cipher text, for a permutation Cipher with
$m = 8$, which was encrypted using the key $\pi$:

${\bf TGEEMNLENNTDROEOAAHDOETCSHAEITLM.}$

Answer:

a)$$ \pi^{-1}=\begin{pmatrix}
1 &2& 3& 4& 5& 6& 7& 8\\
2& 4& 6& 1& 8& 3& 5& 7
\end{pmatrix}$$

b) To decrypt, I partition the text into groups of 8 giving.

${\bf TGEEMNLE\ \ NNTDROEOA\ \ AHDOETCS\ \ HAEITLM.}$

${\bf TGEEMNLE}$ decrpyts to ${\bf ETNGLEEM.}$

I am fairly sure that this is wrong. However, I do not know what I did wrong.
Please help.

Bob

Apply the $\pi^{-1}$ to all the blocks. Then put them under each other so we get colums of length 4 in this case. Then read out left to right, up to down instead (zig-zag).


Independent Pseudo Random Generators Is it sufficient to seed a pseudo-random number generator (PRNG) with two different values to be able to claim that we now have two independent PRNGs? Or is it that we have to use two functionally different generators for that?

If you are using a cryptographicly secure PRNG with a sufficiently large seed. Then it is expected to be infeasible to detect a relationship between the random stream output.
If you find two carefully crafted seeds where the output streams then have some clear relationship it would be considered a (mild) weakness in the PRNG, and much more so with random seeds.


What is the meaning of Maximum Expected Differential/Linear Probability (MEDP/MELP)? I was reading this paper which has a lot of references to the terms MEDP and MELP. Even though i think i got the general meaning, I could not verify that it is indeed correct.

For the MEDP, I would say that it is the maximum bias that can be achieved over k rounds of encryption.

For the MELP, respectively, I would say that is the maximum probability of an equation that holds over k rounds of encryption.

And both are used in order to evaluate the resistance of an encryption scheme against differential and linear cryptanalysis, for example by setting the upper bounds on those metrics.
Is that right?

Also, I have noticed that those quantities are referred for 2 rounds of encryption in a lot of cases. (is various AES MEDP,MELP papers)
Is there a particular reason why they choose only 2 rounds, or it's just matter of computational complexity?

The paper you link to gives precise definitions for the MEDP and MELP.  I will attempt to explain the definitions more expansively & clearly.

First, the differential probability (DP) function with respect to a given block cipher takes an input difference $\Delta x$, an output difference $\Delta y$, and a key $k$ as inputs and generates a probability as the output.  This probability can be understood to mean: “the number of pairs of plaintexts $(P_a, P_b)$ such that $P_a \oplus P_b =  \Delta x$ and $E_k(P_a) \oplus E_k(P_b) = \Delta y$ (where $E_k(\cdot)$ is the encryption function of the given blockcipher under the key $k$) divided by the total number of possible pairs of plaintexts where $P_a \oplus P_b =  \Delta x$ (which is just $2^B$ where $B$ is the block-size in bits of the blockcipher).”

The Expected Differential Probability (EDP) is a function that takes an input difference and output difference and finds the simple average DP of that input-output difference pattern (averaged over all possible keys).  Expectation in this case reduces to the simple average because as the paper states we are assuming all keys are equiprobable.  So in plain English, add up the DP of that difference pattern for every key and then divide the resulting sum by the size of the keyspace (e.g. $2^{128}$ for AES-128).

The MEDP is simply the maximum such EDP over all possible pairs of input difference and output difference, excluding the all-zero input/output difference (which if not excluded would trivially be the maximum, but which is not useful for cryptanalysis).  In (hopefully) plainer English, this asks what pattern of input and output differences gives the attacker the best chance (averaged over all keys) of finding a pair of plaintexts that match that pattern, and how much of a chance is that best chance?

The MEDP is used to evaluate how resilient a block cipher is to differential cryptanalysis.  If you can prove that a cipher has a very low MEDP then the cipher is provably secure against that type of attack (“very low” meaning something only slightly higher than the MEDP of a random permutation, i.e. $\dfrac{1}{2^B}$).

Switching to the linear probability (LP), with respect to a given block cipher this is a function that takes an input mask $a$ (a string of bits $B$ long), an output mask $b$, and a key $k$ and returns a probability.  In terms of how these masks are used, $a \bullet X$ means taking the $B$-bit string $a$ and ANDing it with the $B$-bit string $X$, and then xoring together all $B$ bits of the resulting string to get a checksum bit.  As section 5 of the paper describes, the probability generated by the LP function is: $2 \cdot$ “number of plaintext-ciphertext pairs $(P_i, E_k(P_i))$ for which $a \bullet P_i = b \bullet E_k(P_i)$ divided by the total number of possible plaintexts (i.e. $2^B$)” $-1$ all squared.  For example, if the expression $a \bullet P_i = b \bullet E_k(P_i)$ is true for exactly half of the possible plaintexts $P_i$ then the LP would be $(2 \cdot \frac{1}{2} -1)^2 = 0^2 = 0$.  If the number of plaintexts for which the expression is true deviates from 50% (either higher or lower than 50%) then the LP will be higher than 0, and the more the deviation the closer the LP will get to 1.

The ELP is very similar to the EDP in that for a particular pair of input and output masks the ELP gives the average LP (averaged over all possible equiprobable keys).  Like the MEDP, the MELP is simply the maximum ELP over all possible input-output mask pairs (excluding the all zero masks).  Similar to the MEDP, the MELP is used to evaluate how resilient a block cipher is to linear cryptanalysis (a provably very low MELP is a proof that the cipher is secure against that type of attack).

For the last part of your question, the reason why the paper focuses so much on finding the exact MEDP and MELP for 2 rounds of AES is that one can prove that the MEDP and MELP for 4 (or more) rounds of AES is upper bounded by the 2-round MEDP (respectively MELP) raised to the power 4.  So if they find the 2-round MEDP/MELP they immediately can give an upper bound on the MEDP/MELP of the entire cipher.


How to simplify a the signing process in an elliptic curve signature scheme that involves a quadratic verification equation? I am looking at a proprietary signature scheme used in production. It involves a short Weierstrass curve $E_{\mathcal{W}}:y^2=x^3+ax+b$ in the prime field $\mathbb{F}_p$. The parameters are set up such that $E_{\mathcal{W}}$ is always expressible as a Montgomery curve $E_{\mathcal{M}}:y^2=x^3+x$ (i.e. $a_{\mathcal{W}}=1$, $b_{\mathcal{W}}=0$, $A_{\mathcal{M}}=0$, and $B_{\mathcal{M}}=1$). As far as I know, the Montgomery form is never used for verification. The curve has highly composite order $n$, with a base point $B$ having prime order $\ell$.
The verification process given a hash function $H$, a keyed hash function built from $H$ with (namely $H$ in HMAC mode, $H_k$), a message $M$, a public key $K$ and a signature consisting of a scalar $s$ and a hash $h$ is performed as follows:

$h_1=H_{c_1}(M||h)$.
$R=s\cdot(sB+h_1K)$
$h_2=H_{c_2}(M || R_x || R_y)$, where $R_x$ is the $x$ coordinate of $R$ and accordingly $R_y$ is the $y$ coordinate of $R$
If $h_2=h$, the signature is valid; else, it is invalid.

$c_1$ and $c_2$ are static HMAC keys known both to the signer and the verifier. My conjecture is that they act as domain separation strings.

I am trying to determine if there is an efficient way of creating a signature that does not involve taking a square root in $\mathbb{F}_p$. Square roots are not trivially found in $p$ because $p$ it may be that $p\equiv1\pmod{4}$ and $p\equiv1\pmod{8}$.
Currently, I reach the following signing process:

Choose a nonce $r$ such that $0<r<\ell$.
$R=rB$
$h_2=H_{c_2}(M||R_x||R_y)$
$h_1=H_{c_1}(M||h_2)$
$s=\frac{-Hk\pm\sqrt{(h_1k)^2+4r}}{2}\pmod{\ell}$, where $k$ is the secret key corresponding to $K$ in the verification process
If $\sqrt{(h_1k)^2+4r}$ has no solution in $\mathbb{F}_p$, restart from the beginning.
Output signature $(s, h_2)$.

Is there a way to create a signature passing the above verification process that does not involve a square root in $\mathbb{F}_p$?

Is there a way to create a signature passing the above verification process that does not involve a square root in $\mathbb{F}_p$?

Well, one obvious thing to try is setting $R=0$ (the point at infinity); assuming the code doesn't have any protection against that (and the pseudocode doesn't), you compute $h = H_{c_2}(M || R_x || R_y )$ (where $R_x, R_y$ is whatever representation the point-at-infinity has), set $s=0$, and you're done...


What are the practical implications of ciphertext distinguishability? Commonly there are four ways to "break" a secrecy-focused cryptosystem:

Recover the secret key
Recover the message
Distinguish an encryption from random noise
Distinguish the encryption of two different messages

The practical implications of the first two breaks are obious: They allow arbitrary message recovery (more or less) fast.

However I'm unclear about the practical implications of the the last two breaks.

So let's assume an encryption algorithm or a public key cryptosystem which fails to provide indistinguishability but also doesn't allow key or message recovery. As an example assume the scheme from the "Present an attack for the combination of OTP and textbook RSA" question under a chosen plaintext attack.

So:
What are the practical implications if a distinguishable cryptosystem would be used in practice?

This isn't really a "hard" answer, but an attempt to give some intuition or motivation.

One can interpret indistinguishability as an overapproximation of the most common notions of security: Any system that is broken in a more practical way will also fail to meet indistinguishability, that is, all practically important security requirements are in fact subsumed by indistinguishability. It is therefore a sensible and defensive approach to require indistinguishability. This proceeding also agrees with the expectations one usually poses to a "good" system: It should be as close as realistically possible to Shannon's definition of perfect secrecy.

On the other hand, a system may well be distinguishable but do not admit any relevant attacks — however, in practice, distinguishing attacks are often the first sign that a system may be about to break in more severe ways. A potential reason for this could be the fact that the structure of a system needs to be well-understood by researchers to find such attacks, and then other weaknesses can become visible as well. I suppose the most prominent example is the RC4 cipher, which continued to accumulate more and more known biases (breaking indistinguishability) over time until it had to be considered insecure for practical purposes.


Brute force a ciphered message? I wrote my own cipher to encrypt messages. I would like to test a sample ciphered message to see how strong it is. Are there any tools for such task either in Windows or Linux ?

There's no way to verify the strength of a cipher in any automated way, especially given only the ciphertext. Attacking the construction of a cipher is an inherantly intellectual process, which does not fit well to the qualities of computer analysis.

For example, I could write a cipher such that $f(m) = rand(0,n)$ where $n$ is the largest integer representable in $sizeof(m)*8$ bits, and any automated analysis would say "this is an awesome cipher", but a human would immediately realise that it's totally useless.

If you're writing your own ciphers for real usage, I have only one piece of advice: don't.

Creating your own ciphers is fun, and it can give you a learning experience if you're actually doing it based on constructions you understand, but the resulting cipher should never ever go anywhere near a production system. Experts put their ciphers through years (decades, even) of peer review before they're adopted by anyone. If your goal is to learn, do so by breaking ciphers.


Lagrange Coefficients & Polynomial in KP-ABE My question is how these concepts relate in ABE.

I am assuming that the attributes are used to share the master secret key and only a user with the right attributes for a particular access tree is able to reconstruct the master secret key.

Could someone help with some details on how this work.

Short refresher on KP-ABE:

The Master Secret Key (MSK) and the Public Parameters (PP) are created during Setup and both enable the attribute authority to create Secret Keys (SK) for users using the Keygen algorithm.

Some user who possesses PP can Encrypt some data with a set of attributes $\gamma$. The encryption works by generating a new random secret $s$ and using that secret on all attributes in set $\gamma$.

$${E_i=T_i^s}_\gamma$$

The Keygen algorithm takes a policy (access tree) and MSK to create SK. The $y$ element from MSK is shared by using the policy into shares that represent the leaves of the access tree $q_x(0)$. This is very similar to Shamir's Secret Sharing. Those shares are used as

$$D_x=g^{\frac{q_x(0)}{t_i}}$$

where $q_x(0)$ and $t_i$ are both not easy to calculate due to the difficulty of discrete logarithm. Since the Lagrange interpolation is done in the exponent, as the polynomial interpolation on page 9 shows, it cannot reveal $y$. In the end we get $e(g,g)^{ys}$ where $y$ is still not easily computable due to discrete logarithm.

  I am assuming that the attributes are used to share the master secret key and only a user with the right attributes for a particular access tree is able to reconstruct the master secret key.

If the user would be able to reconstruct MSK from its own SK and the received CT, then it could create SKs for any attribute set and decrypt any CT with any policy. Of course, this is not the point of ABE. The MSK is the master secret key, because you can create any SK from it, so it must be kept secret at all cost by the attribute authority. This is also the main problem of ABE, because this is basically a key escrow service that, if broken into, undermines the complete security of the system.


Can we estimate the loss of entropy when applying a N-bit hash function to and N-bit random input? Someone pointed out recently to me that a cryptographic hash function " is not designed as a bijective mapping from N bit input to N bit output".

So if I feed an N-bit cryptographic hash function with N bits of random input, there's a loss of entropy between the input and output of the hash function.

Considering the md5 hash function, is there a way to estimate that loss of entropy? And is this loss cumulative so I could say, if I apply the hash function enough times, I end up with a 50% loss of entropy?

Actually, no. If it is a good Hash, you should roughly have $N-k$ bits of output entropy for some $k$ of much lower order than $N$.

The problem arises when the input is much longer than $N$ bits.

One way to estimate the entropy loss of such a Hash applied to $N$ bit inputs is to model it as a randomly chosen function on $N$ bits.
This was first done by Odlyzko and Flajolet. There is a nice review with updated results here

Let $\tau_m$ be the image size of the $m$th iterate of the function. The entropy can be related to its behaviour.

If the function is a permutation, $\tau_m=2^N$ for all $m\geq 1$ and there is no entropy loss.

Edit: See the comment and link by @fgrieu which is an estimate of what I called $\tau_1.$ He is saying that
$$
\tau_1\approx 2^{128-0.8272\cdots  }
$$
for $N=128.$


Prime Numbers in Discrete Log I am implementing a security protocol based on discrete log. I came across the equation $p = kq + 1$. Understand that based on number theories that both $p$ and $q$ should be large enough to be "safe". However, how does it justifies safe? Say I chose $p = 7$, $k = 2$ and $q = 3$, will my implementation be screwed up?

There already exist standard primes that might be used for Finite Field Discrete Logarithm based schemes. One set is found in RFC 3526. Another set is currently in the process of being standardized as part of TLS and can be found in the current Negotiated FF DHE draft (this link will expire no later than June 15 2015).

The smallest prime in the former set is 1536 bits, which means that it is greater than $2^{1535}$. It is recommended to be used with a 180 bit exponent, which corresponds to an integer greater than $2^{179}$.

The smallest prime in the latter set (TLS) is currently fixed at 2048 bits, although an even greater number was originally proposed.

By comparison, 7 is only 3 bits and 3 is only 2 bits, so, yes, your implementation would be kind of inadequate, should you try to use these primes.


Zero-knowledge problem of Pinocchio (verifiable computation) This is a similar (and further) question of
Verification of Pinocchio (verifiable computation)

In Section 2.1, it said

  the outsourced computation is a function, $F(u,w)$, of two inputs: the client’s input $u$ and an auxiliary input $w$ from the worker. A VC scheme is zeroknowledge if the client learns nothing about the worker’s input

But in section 3.1, Protocol 2, the verification function requires all the elements $c_k$, which I think contain the value of all the input wires (including $w$). So how can it hide $w$ from the client?  The Zero Knowledge section said that the GGPR’s rerandomization technique could be used, but the rerandomization is only added to $v(x),w(x),r(x)$, and I guess the client still have to know all the $c_k$?

I've been confused on this for days. Can anyone please help me to understand how the ZK is done?

It is true that the verification procedure needs the values of the input wires, but "input wires" refers only to the wires of $u$, the value provided by the client.  The wires for $w$ are considered "middle wires", and are included in the computation of $v_{mid}$, $w_{mid}$, and $y_{mid}$ (i.e., their indices are included in $I_{mid}$).

On a higher level, the protocol does this:

The client sends (to the worker) values for some (not necessarily all, and possibly even zero) wires.  The wires for which a value is provided by the client are called the "input wires".

The worker sends (to the client) two things:

Values for some wires of the circuit whose values have not been provided by the client.  The wires for which a value is provided by the worker are called "output wires".  All wires that are not input or output wires are called "middle wires".
A proof of the following statement: It is possible to assign values to all the middle wires of the circuit so that "everything works", meaning that the input and output wires for every gate of the circuit are correct for the operation that the gate is supposed to perform, and moreover, the worker knows some such values.  This proof can be zero-knowledge; in that case it reveals nothing about the values of the middle wires.

The case where "input wires" (resp. "output wires") in the above sense correspond to the input and output wires of the circuit in the usual sense is actually just a special case, which corresponds to the "non-ZK" case discussed in the paper.  In the ZK case discussed in the paper, the "input wires" in the above sense correspond to only some of the input wires of the circuit: the wires for $u$. The wires for $w$ are "middle wires", so that the worker proves, in zero-knowlege, that it knows appropriate values for those wires.


What's the name of this cipher? And how can it be broken? Assuming that:

SHA-256 and SHA-512 are random and irreversible
the output appended to some random and long enough secret is just as random as any other data and will produce values that are just as hard to guess

Then one can conclude that a cipher can be constructed using those hash functions in the following manner:

let state and key both be 32 or 64 byte values
initialize state with a random IV and key with a random key
make v equal the hash of state + key, xor block of plaintext withv
update state with the cipher produced
repeat until all plaintext is processed
to decrypt do the same, but update the state with the cipher text

Now the question is, does such a cipher exist? Is it possible to discover the plaintext given a ciphertext without brute-forcing the key? If so, what techniques could be used for that?

This would appear to be CFB mode, only using a hash function (with a secret key as part of the input), rather than a block cipher.

As such, assuming that the hash function with the partially secret input acts as a random Oracle, this provides privacy.  However, it doesn't provide integrity (that is, the attacker can modify the ciphertext, and the resulting ciphertext will decrypt, and in fact produce semipredictable changes to the plaintext), and will probably end up being slower than a more conventional encryption method.


Why do we need Euler's totient function $\varphi(N)$ in RSA? After we calculated $N = p * q$, we calculate $\varphi(N)$ and use it later to determine $e$ (PR) and $d$ (PU). But why?
For decryption and encryption, we only use $N$ and don't need $\varphi(N)$. So why can't we find $e$ and $d$ without Euler's totient function?
I know that $\varphi(N)$ is giving me how many integers are coprime to $N$, and if $N$ is a prime then it would be $\varphi(N) = N - 1$. But why is this useful? Or rather why is it a must for determining $e$ and $d$ in RSA?
Edit:
And why does $e$ need to be smaller than $\varphi(N)$?

What we really need is a number $\lambda$ satisfying $x^{\lambda+1} \equiv x \pmod n$ for all integers $x$ (which, by induction, then implies that $x^{k\lambda+1} \equiv x \pmod n$ for any $k$).

Given such a $\lambda$, and an arbitrary encryption exponent $e$ which is coprime to it, we can then find the multiplicative inverse of $e$ modulo $\lambda$, i.e. a number $d$ such that $ed \equiv 1 \pmod \lambda$, or in other words, $ed = k\lambda + 1$ for some integer $k$.  Such $e$ and $d$ then satisfy $$(x^e)^d = x^{ed} = x^{k\lambda+1} \equiv x \pmod n,$$ meaning that, if we encrypt a number by raising it to the $e$-th power modulo $n$, we can recover the original number by raising the result to the $d$-th power and again reducing it modulo $n$.  This is what we need for RSA encryption and decryption to work correctly.

The smallest such number $\lambda$ is given by the Carmichael totient function, which, for a product $n = pq$ of two primes, is $$\lambda(pq) = \operatorname{lcm}(p-1, q-1)$$ where $\operatorname{lcm}(p-1,q-1)$ denotes the least common multiple of $p-1$ and $q-1$.  However, since we don't necessarily need the smallest such number, it's also possible to use the Euler totient function $$\varphi(pq) = (p-1)(q-1)$$ which is, by definition, always a multiple of $\lambda$.

I'm not aware of any particular reason for preferring $\varphi$ over $\lambda$, except that it's slightly easier to compute $\varphi$ and to explain why it has the necessary property $x^{\varphi+1} \equiv x \pmod n$, which may be why introductory texts tend to prefer it.  I do believe, however, that actual practical RSA implementations (insofar as they explicitly compute the decryption exponent at all, rather than e.g. using the Chinese remainder theorem) generally use $\lambda$ rather than $\varphi$, since doing so yields the smallest possible decryption exponent $d$.

Addendum: The reason why $\lambda$ (and $\varphi$) satisfies $x^{\lambda+1} \equiv x \pmod n$ is basically Fermat's little theorem, which says that, for any prime $p$ and any integer $x$, $$x^p \equiv x \pmod p.$$

This can be easily generalized to show that, for any multiple $k\lambda(p)$ of $\lambda(p) = p-1$, $$x^{k\lambda(p)+1} \equiv x^{\lambda(p)+1} = x^p \equiv x \pmod p.$$

In particular, since $\lambda(pq) = \operatorname{lcm}(p-1,q-1)$ is, by definition, a multiple (and in fact, the smallest common multiple) of both $\lambda(p) = p-1$ and $\lambda(q) = q-1$, it follows that $x^{\lambda(pq)+1} \equiv x$ modulo both $p$ and $q$, and therefore, also modulo $pq = n$.

Of course, since $\varphi(pq) = (p-1)(q-1)$ is also a multiple of both $p-1$ and $q-1$, it also has the same property, as does any other common multiple of those numbers.

The fact that $\varphi(n)$ also happens to be the order of the multiplicative group modulo $n = pq$ is basically a red herring; there's nothing special about $\varphi(n)$ among all the other multiples of $\lambda(n)$ as far as RSA is concerned.  What's more relevant is that $\lambda(n)$ is the exponent of this group, which is essentially another way of stating the crucial property that $x^{\lambda(n)+1} \equiv x \pmod n$ for all $x$.


One doubt on an NP hard problem It seems that Shortest Vector Problem in a lattice  is NP hard. Then how Ajtai-Kumar-Sivakumar (AKS) algorithm solves it? I mean, what is the witness?

First of all, SVP is not known to be NP-complete. There are some hardness results for SVP, but just considering very specific scenarios (for instance, SVP is NP-Hard in the $\ell_{\infty}$ norm) or under other types of reductions (such as randomized or non-uniform reductions).

Even so, the AKS algorithm runs in exponential time, so, it doesn't give us any information about the hardness of SVP.

When we say that a problem is NP-hard, we expected that there is no polynomial-time algorithm to solve the problem, but there is nothing strange with the fact that we know exponential-time algorithms for the problem (and we usually know trivial exponential-time algorithms to solve hard problems...).


Standardized parameters for elliptic curve cryptography When an elliptic curve-based cryptosystem is deployed, a single set of public parameters (consisting of a particular elliptic curve over a finite field as well as a generator of a prime order subgroup of its group of points) is typically shared across all users.

Some of these public parameters are standardized in some form. The best known ones are NIST-approved curve parameters, described as part of the FIPS 186-{2,3} standard, but there are others. For example, a French agency recently released a set of parameters recommended for local security applications (possibly over concerns re the security of curves over the very special base fields used by NIST?—they didn't say).

Is a list of such curve parameters compiled somewhere? Do you know any aside from the previous ones?

There are a few more standards, with (sometimes) overlapping sets of parameters:

ANSI X9.62
SECG
Brainpool