Correcting Improperly Formatted EC Private Keys We are currently generating a secp521r1 key as follows using cryptography for Python:

private_key = ec.generate_private_key(ec.SECP521R1(), default_backend())
serialized_private = private_key.private_bytes(
    encoding=DER,
    format=TraditionalOpenSSL,
    encryption_algorithm=NoEncryption()
)

This turns up the following DER file:

3081DB02 01010441 1343B3C8 94ABD7D3 B2CD80C9 872667BB 45406FC4 E342CDAC
543C99AE 51382765 990DF5EF 1A0436BD 771E8F45 9B8DAE82 EBC101A7 DA084666
F1E718D2 F3F5722F A1A00706 052B8104 0023A181 89038186 000401B9 CB8E7F9F
C698CCAF 5E37A0A3 FF418566 6ABD9F9B ACF2B7F5 5F8785AD C3EA9848 FE29FD33
BC1DB969 158BC3AA 0F684AED BF542D19 B3BCB040 7EAAAD04 2ECA9B50 0109AC9E
F94383C3 CE2CCAFB 1F85289C C2C3153F 76018012 EC7B0E0E 8F29A375 01A3557B
EF5E77E0 24CC2A64 31506CAB E215A833 2E437348 64380564 98A8444A C5B6

From this, we get the following ASN.1 tree:

SEQUENCE (4 elem)
    INTEGER 1
    OCTET STRING (65 byte) 13 43 B3 C8 94 AB D7 D3… (PRIVATE KEY)
    [0] (1 elem)
        OBJECT IDENTIFIER 1.3.132.0.35
    [1] (1 elem)
        BIT STRING (1064 bit) 00 04 01 B9 CB 8E 7F 9F... (PUBLIC KEY)

The problem begins when I extract these two octet strings and present them to the Security APIs on OS X and iOS. These APIs expect the raw octet strings as a concatenation of the public, then the private key, with no extraneous markers. However, it seems like these public and private keys I'm getting from what I assume is OpenSSL under the hood  are slightly malformed; the public key is prefixed with an extraneous 0x00, while the private key is missing a byte (every one I've generated so far that has the missing byte has that byte set to 0x01, but I can only guess what this value should be when the byte is missing… See (page 12 of SEC2)[http://www.secg.org/sec2-v2.pdf] for why I (probably incorrectly) assume the leading digit might be a 0x01).

From my (very limited) understanding of how SEC1 private keys are expected to be encoded, I would imagine that the private key must be 66 bytes long for 521-bit keys (521 bits == 65.125 bytes), while the public key must be 133 bytes long for 521-bit keys (same 66 bytes for x and y, plus a leading 0x04).

Assuming these keys are properly generated, is it safe to assume the leading 0x00 on the public key can be stripped, and the private key padded with a leading 0x01?

Ps. Maybe this is related? https://www.mail-archive.com/openssl-dev@openssl.org/msg37790.html

Yes, it seems related: the private key just misses a 00 value (not a 01 value) in front. The problem that the I2OS primitive seems to round down instead of up if the value is smaller than 520 bits (65 bytes).

Fortunately the public key seems to be OK. The next byte boundary from 521 is 528 (512 + 16 bits). 2 x 528 = 1056 bits. However, the first 8 bits of the bit string indicate the number of bits that are not used out of the next bits. They are always present, and always set to 00 whenever the bit string is used to represent bytes. So they always need to be skipped (check the bits themselves on the site you link to - you'll see they start with 00000100 which is 04 not 00!).

So basically you get to the following simple scheme: get the private key and add as many 00 bytes to the left until you get 528 bits (66 bytes). For the public key just use it straight away, starting at the 04 (uncompressed point). If it doesn't work then maybe iOS expects the X and Y coordinates directly so strip the 04 away.


Alternative for RFC 6238/4226 - one time password via SMS (single-factor authentication) Currently we have implemented One Time Passwords (OTP) as second  authentication which works well. We use TOTP - RFC 6238

Some clients would like to have a "sms only" login, so it's single factor authentication. In the some cases (dependent of the data) that is fine. We will send the token via SMS and it won't have to be OTP-app compatible (e.g. Google Authenticator)

To our opinion the RFC 6238 (TOTP) is too weak for single factor authentication as the time component gives issues:

If the password is 30 seconds long, two login attempts in the the 30 seconds period will give the same password
If we change the time to 1 sec, we have to check multiple "frames"
Also, alphanumeric characters in the password isn't compatible with the RFC?

We are also aware there is a counter based algorithm (HOTP - RFC 4226), but their could be security issues if we won't sync the counter correctly (between servers).

So we are looking for a RFC to generate one time passwords with the following requirements:

Generate passwords, time based, no counter
Generate passwords with alphanumeric and numeric characters

The flow will be:

Generate OTP
Store the password in (server-side) session (including expiration)
Check the token and clear the session.

We could use the following code to create a OTP

Generate random (secure) bytes
Convert to text

But that isn't compliant to a RFC, and RFC-compliance is preferred.

My questions:

Is there another RFC we could use that satisfies the requirements?
Are we RFC 6238 compliant if we: generate the TOTP with a short time (e.g. 1 sec), and store the result in session.

From a security standpoint it is not necessary to reduce the time interval to one second. Your implementation has to assure, that there will be no second login attempt in this time interval.
I recommend to save the latest timestamp and during authentication verify, if enough time has passed, and only then create a new TOTP value and send this via SMS.
This is also, what the TOTP RFC recommends.

Also, the RFC says, that you should use 30 or 60 seconds time intervals.
You should ask yourself: how often will the users try to login?

alphanumeric

The original OTP algorithm by Lamport creates alphanumeric values.
But the problem is, that the use case for the lamport algorithm was a bit different. In my opinion the orignial intend was not to introduce a second factor but to disallow replay attackes.

It is a challenge response algorithm. I.e. you have to make a challenge all the time, you could calculate the response and save the response in the session and send it via SMS. But you also need to assure, that you really create different challenges.

TOTP alphanumeric

The thing with the HOTP and TOTP algorithm is that they were defined by hardware vendors to provide a second (possession) factor. This is probably why the output is ment to be digits and not alphanumerics. digit LCDs are cheaper and digits are easier to display than alphanumerics.

But you could however change the truncation algorithm to generate hex strings or some kind of alphanumeric values.
The 6 digits or 8 digits is just a transformation from a sha1 output. You can also convert the sha1 ouput to lets say to 10 alphanumeric characters.
See https://tools.ietf.org/html/rfc4226#section-5.3

OCRA Algorithm
If you want to be absolutely RFC complient you can take a look at the OCRA Algorithm, which is the third member of the three musketeers HOTP, TOTP, OCRA. This RFC officially allows you to define the truncation function and even skip the truncation completely:
https://tools.ietf.org/html/rfc6287#section-5.2

But honestly running the OCRA add some layer of complexity. I probably would go with HOTP and a modified truncation method.


Can private data be encrypted and stored safely in public? Given that AES-256 is reasonably strong encryption, can private data (for example Bitcoin private keys) be sufficiently encrypted and stored safely in public places (for example a public github repository)?

The short answer is: if and only if the key is never compromised and the algorithm is never severely broken.

To inject some realism into this question, one real-life event that's worth knowing is how Wikileaks' encrypted file of USA diplomatic cables got compromised.  Bruce Schneier had a good summary at the time (it's not a primary source, but he links such sources).  But the basic idea is:

Wikileaks encrypts a file with lots of sensitive information, using password-based encryption.
Wikileaks shares the file and password with a journalist.
Wikileaks posts the encrypted file into Bittorrent as a backup/survival measure.
The journalist, who is not technically savvy at all, writes a book and uses the password as a chapter title.
Observers manage to put two and two together, download the torrent, and decrypt it with the password from the book.

How does this address your question?  Well, if the file had not been uploaded to a public system like Bittorrent, the damage from the exposure of the password would have been much smaller.  So publicizing a ciphertext widely certainly carries additional risks.

That's not a yes/no answer to your scenario, because there isn't one.  Restricting the circulation of the ciphertext is always safer, but this is really a risk vs. convenience tradeoff where you might reasonably opt for convenience, depending on the application.


signature with Bleichenbacher’s attack I understood Bleichenbacher & ROBOTO attack, however I have some trouble understanding Section 3.5 of ROBOT attack which discusses retrieving private keys.
https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-bock.pdf

  In order to create a signature with the server’s private key, the
  attacker first uses a proper hash function and encoding to process the
  message. For example, when creating a PKCS #1 v1.5 signature for
  message M, the encoded result will have the following format [29]:

  EM = 0x0001 || 0xFF...FF || 0x00 || ASN.1(hash(M))

  hash() denotes a cryptographic hash function.

What message M is the author talking about? Is this TLS session establishment?
Can someone shed more light on this section 3.5

What message M is the author talking about? Is this TLS session establishment? Can someone shed more light on this section 3.5

First of all, you need to understand what the Bleichenbacher attack is (by the description in your answer, you don't).

What it is is a way of, given a value $EM$, computing $EM^d \bmod N$, given an Oracle that will, given a value $EM'$, telling you whether $EM'^d \bmod N$ has value PKCS #1.5 encryption padding (which is different from the signature padding).  The attacker can often find an Oracle by using a protocol where he sends an encrypted value to the system under attack, and observing how the system reacts (whether he acts as if the decryption failed, or whether he acts like he got some valid value).

When the attack was first published 20 years ago, it would require a huge number (circa a million) different $EM'$ values to actually work; later refinements significantly reduced that number, to circa 10,000 messages IIRC.

Now, on to TLS and your actual question, and while the paper does look at protocols beyond TLS, I'll focus on TLS.

When the TLS server establishes a connection, it sends both its certificate (showing that it owns a public key), and something signed with that public key.  If the signature doesn't verify, the client rejects the connection.

So, in order to masquerade as the server, you'd need to do the same thing; you need to send a certificate (which this attack reuses the valid server's certificate), and then the signature of something; that something is the message M.

Now, if you look into the TLS protocol, this $M$ is the transcript of the TLS negotiation up to that point; the details aren't actually relevant to the attack, except that they aren't known until the negotiation actually happens (as it includes unpredictable values chosen by the client).

So, what the paper proposes we do is masquerade as the server up until the point where it actually has to generate the signature.  It knows $M$, and so we able to compute $EM$.  Then, by quickly performing the Bleichenbacher attack against the real server, it recovers $EM^d \bmod N$ before the client times out.  This $EM^d \bmod N$ value is the correct signature for $M$, and so the attacker can present that to the client, and the attack succeeds.


Learning cryptography using a FPGA I have a FPGA and am curious what cryptographic applications I can use with it.  I'm just a hobbyist / security researcher and not a professional cryptographer.

Since I'm creating my own curriculum, what cryptographic goals should I have with regards to the FPGA device?  (note I'm not looking for FPGA programming advice, that's a goal all in of itself)

I'm also interested in learning what won't work with a FPGA... in other words, what algorithms are or aren't suited for a FPGA?

As for goals, there are typically two that you would look to when implementing something on an FPGA: first, minimizing latency; second, maximizing throughput.

To minimize latency, you would use the FPGA to perform a computation much faster than you could do on a CPU. An example here would be the DES cipher. DES is well suited for hardware and you can get significant reductions in latency using an FPGA.

The second goal to potentially look at is maximizing throughput. The idea here is that you could potentially use hardware to encrypt 100s of streams in parallel.

As to which algorithms are not suited for FPGA, Thomas pointed out scrypt. I'm guessing other KDFs are similar in that they try to make it extremely hard for an attacker to gain any advantage by using an FPGA. Of related interest might be this question on bcrypt using GPUs.


Can j-invariants be used to decide which elliptic curves are suiteable for cryptography? The j-invariants classify the elliptic curves up to isomorphisms (if we suppose to work in the algebraic closure). Is this classification used in some way to decide whether or not an elliptic curve can be used in cryptography?

If j-invariants can not be used for classification, is there an other classification which responds to my question?
If j-invariants can be used for classification, what does the j-invariants tell us about the curve so that we know it is save to use it for cryptography?

For example: can a certain j-invariant correspond to a curve where we are sure that it has full-torsion so that it is a possible choice for Weil pairing?

Giving the j-invariant is basically equivalent to giving a curve equation (up to quadratic twist) (over $\mathbb F_p$ for $p > 3$) : to each j-invariant you can attach a pair of curves $(E, \widetilde E)$. You can easily compute the curve equations of $E$ and $\widetilde E$ from $j$:

$$E: y^2 = x^3 + a x + 2a, \qquad a = -\frac{27j}{j-1728}$$

Now the $j$-invariant is "suitable for crypto" if both curves above are suitable, which you can check using the usual algorithms (SEA, etc.).
Since it is easy to go from “curve equation” to “j-invariant” and back, it is also easy to conclude that the j-invariant does not contain anything particularly useful for cryptography.


Random semantic security and bijective PRGs I'm working through Boneh and Shoup's "Graduate Course in Applied Cryptography", and have just finished reading the chapter on stream ciphers and PRGs.

The first exercise for this chapter introduces the notion of semantic security of a cipher for random plaintext messages. Formally, for a cipher $\mathcal{E}=(E, D)$ defined over $(\mathcal{K}, \mathcal{M}, \mathcal{C})$, we define an attack game where the challenger (instead of the adversary $\mathcal{A}$) chooses two messages $(m_0, m_1) \xleftarrow{R} \mathcal{M}$ uniformly at random from the message space, and encrypts $m_b$ in Experiment $b \in \{0, 1\}$, sending the adversary the resulting ciphertext $c$. $\mathcal{A}$ then sends back a single bit $\hat{b} \in \{0, 1\}$ to end the game. $\mathcal{A}$'s advantage in this game is then defined as

$$
SSRadv[\mathcal{A}, \mathcal{E}] = \left|Pr[\hat{b}=1|b=0] - Pr[\hat{b}=1|b=1]\right|
$$

and $\mathcal{E}$ is said to be semantically secure for random plaintexts if $SSRadv[\mathcal{A}, \mathcal{E}]$ is negligible for any efficient adversary $\mathcal{A}$.

The main body of the question asks about how one would build a cipher $\mathcal{E}'=(E', D')$ defined over $(\mathcal{K}', \mathcal{M}', \mathcal{C}')$ that is semantically secure in the "normal sense" (i.e. in an attack game where the adversary chooses $m_0$ and $m_1$), using an SSR-secure (as defined above) cipher $\mathcal{E}$ as a starting point. For complete context, the problem also states that $\mathcal{K}=\mathcal{K}', \mathcal{M}=\mathcal{M}'$.

Given the topic of the preceding chapter, it feels like a natural solution here is to use a secure PRG $G$. Specifically, let $G$ be a secure PRG defined over $(\mathcal{M}, \mathcal{M})$, and then for a given key $k \in \mathcal{K}$ and message $m \in \mathcal{M}$, define $E'(k, m) = E(k, G(m))$. Intuitively, G transforms any chosen plaintext $m$ into an essentially random element of $\mathcal{M}$, and then the random semantic security of $\mathcal{E}$ implies the semantic security of $\mathcal{E}'$. For brevity, I won't try to spell out the actual security proof here.

My main concern here arises when trying to define what the decryption algorithm $D'$ would look like here. In order to undo the application of $G$, we'd need $G$ to have an inverse, and since $G$ is defined over $(\mathcal{M}, \mathcal{M})$, this implies that $G$ is a bijection. This seems like it would contradict the assumed security of $G$; if we can readily define an inverse for $G$, then we could retrieve any seed from its corresponding image in $G$.

Is it possible to have a secure PRG $G$ that is also a bijection, and if so are there restrictions on $\mathcal{M}$ (e.g. $\mathcal{M}$ is super-poly in the security parameter, etc.)?
Is there a different approach to building $\mathcal{E}'$ that gets around this potential security flaw?

There are a few fundamental problems with your approach:

When you use the construction $m \mapsto E(k,G(m))$ in the context of the standard CPA game, you are feeding adversarially chosen values into the PRG $G$. PRG security does not guarantee anything about PRG outputs in this setting. PRG security can only be applied when the PRG input is uniformly chosen, and used nowhere else in the system (in particular, it can't be known to / chosen by the adversary).
As you mention, decryption requires $G$ to have an efficiently computable inverse, which is incompatible with PRG security. The alternative is that $G$ has no stretch, which basically defeats the purpose of a PRG. If you relax the stretch requirement of a PRG, then even the identity function is a secure PRG in the sense of its outputs looking random. Clearly when you use the identity function in your construction, you haven't actually done anything to $\mathcal{E}$.

  Is there a different approach to building $\mathcal E′$ that gets around this potential security flaw?

Yes, but I don't know how to give a reasonable hint without trivializing the problem. You don't need to introduce any additional crypto primitives beyond the original scheme $\mathcal{E}$.


Hash to prime numbers? Is there some provably secure hash function to prime numbers?
Say, a function $H: \{0, 1\}^* \rightarrow \{e: e \in \{0, 1\}^\lambda \land e$ is prime$\}$

I'm asking because there are some constructions to be used only on prime numbers (for example CL02 Strong-RSA Dynamic Accumulators).

You could use the hash value as seed for a deterministic CSPRNG and then use a prime number generator also used for RSA key pair generation. Note that the size of the prime number must be relatively high (1536 bits for 128 bits of security, e.g. for an RSA key of 3072 bits).

The usual caveats of deterministic RSA key pair generation apply. For instance, the algorithms must remain the same, otherwise a different prime value is calculated for the same hash value.

Generally the method of generating the prime value is available separately in math or crypto libraries that come with the runtime. For instance, Java has the BigInteger(int bitLength, int certainty, Random rnd) constructor.

Beware that the time it takes to find a prime is unknown in advance. The generation may take a long time (and in the case of Java may also take a ridiculous number of bytes from the DRBG - just tested this).


Having access to multiple servers, would additional usage of “Secret Sharing” for password storage enhance security? I am currently learning about secret sharing and I’ve started wondering why larger companies that have access to whole server networks (like – for example – Google, Facebook, etc.) don't use “Secret Sharing” for password storage in addition to hashing and salting.

I know that such companies tend to use many different stages for storing passwords (hashing, salting and encryption in various combinations), but wouldn't more security be achieved by using “Secret Sharing” and storing the resulting shares on independent servers?

The advantage I see is that an adversary would have to have access to at least the threshold number of servers in order to retrieve the hashed passwords. Or am I missing something?

How would such a scheme work?  You'd have to:

Split the password database (or is it individual entries?) into multiple shares;
Distribute those shares across many servers;
Have a system for those servers to peer together to reconstruct the password entries;
Support live additions and modifications of user password entries.  When a user changes their password, this is now a distributed transaction that must succeed or fail atomically (otherwise the user can't log in afterwards!).
Make sure that the reconstructed password entries are never written out to disk, or at least not in the clear.
Make sure that multiple database shares never get aggregated into the same backups.
Other problems I'm probably not considering.

It sounds like a very complex solution.  Lots of moving parts and lots of things that could go wrong.  Not just in terms of security, but also basic functionality.

And what are we supposed to gain from all this complexity?  The idea is that if an attacker steals one share (or fewer than the threshold), they can't mount a brute force attack on the database.  But I think that gain is put at risk by the fact that this would be a system of homogeneous, cooperative, automated peers:

If an attacker finds a software vulnerability that allows them to steal password shares from one server, there's a high probability that the same vulnerability can be used to steal shares from other servers, because of the system's homogeneity.
If an attacker can impersonate a peer, can't they just ask the true peers for the password shares needed to reconstruct the hashes?  After all, the peers freely cooperate with each other to hand over their shares.

Maybe there's a way to mitigate the latter by designating, for each password entry, one peer that "owns" it, so that peer will never share its share with any other.  But now the idea is getting pretty complex, more so when you throw availability requirements—when a peer goes down, can users whose entries are "owned" by that peer log in anymore?  If each entry has a "primary" owner and a "standby" to take over if the primary fails, can we fool the standby into thinking that the primary failed, and does that allow us to bypass the measures?

As a contrast, many applications of secret sharing involve humans who:

Are adversaries who are trying to prevent at least some of the others from learning the secret.
Store their shares in heterogeneous environments that the others don't control.
Store their shares in offline environments where extraordinary measures are required to retrieve them.
Come together to reconstruct the secret manually in a carefully regulated ceremony designed to prevent any participants or other parties from learning the secret.

See, for example:

The DNSSEC root signing ceremony
HashiCorp's Vault tool's initialization process has a PGP integration designed to encrypt the newly generated master key's shares in memory with the recipients' public keys, so that no person ever sees the plaintext of the master key shares.

Dropbox recently wrote a blog post detailing their password storage strategy.  They articulate a strategy that encrypts every hash with a global AES key, which looks much simpler than what you propose and arguably no less secure in practice.  I'll let the quotes speak for themselves:

  Finally, the resulting bcrypt hash is encrypted with AES256 using a secret key (common to all hashes) that we refer to as a pepper. The pepper is a defense in depth measure. The pepper value is stored separately in a manner that makes it difficult to discover by an attacker (i.e. not in a database table). As a result, if only the password storage is compromised, the password hashes are encrypted and of no use to an attacker.

  [...]

  Why is the global pepper used for encryption instead of hashing?

  Recall that the global pepper is a defense in depth measure and we store it separately. But storing it separately also means that we have to include the possibility of the pepper (and not the password hashes) being compromised. If we use the global pepper for hashing, we can’t easily rotate it. Instead, using it for encryption gives us similar security but with the added ability to rotate. The input to this encryption function is randomized, but we also include a random initialization vector (IV).

  Going forward, we’re considering storing the global pepper in a hardware security module (HSM). At our scale, this is an undertaking with considerable complexity, but would significantly reduce the chances of a pepper compromise.


Security of encrypting many short values with AES in GCM mode We intend to encrypt certain values in a database which holds personal information such as addresses so as to prevent data leakage should the database be compromised.

The intention is that each field is individually encrypted with AES GCM with a 128-bit key and 128-bit randomly generated nonce. Fields will generally be quite short in length so there will be many short values encrypted with the same key.

AES GCM was chosen on the basis that it provides authentication in addition to encryption.

There will be approximately 50 million data items with 30 fields each. The intention is to use different keys for subsets of the fields, so likely 5-10 keys initially.

Would AES GCM be suitable for use in this scenario?

The only limitation that you really have to consider is that of nonce collisions. With 128-bit random nonces, you would expect collisions after about $2^{64}$ nonces due to the birthday bound.

Even if you stored all 30 fields of all 50 million rows thousands of times (you need a new nonce if a field is rewritten), you would still have a chance smaller than $2^{-32}$ of a collision. With your plan of using different keys for some fields you should be fine.

There are other limits on how much you can authenticate with GCM, but as long as you use the full-length authentication tag those limits are larger than the one above with short messages like you have. See section 7 of The Galois/Counter Mode of Operation (GCM) (pdf).

NIST SP 800-38D (pdf) says to only use a key for $2^{32}$ messages at most (Section 8.3) unless you are creating deterministic 96-bit nonces. It also gives even smaller limits if you wish to truncate the authentication tag (Appendix C).


"128-bit security" or "128 bits of security"? Maybe a silly question but I am wondering what the correct way to specify a security level is:

128-bit security
128 bits of security
Something else entirely

The term used in the Security level article in Wikipedia is n-bit
 security or for example: 128-bit security level

  In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed in "bits", where n-bit security means that the attacker would have to perform $2^n$ operations to break it, but other methods have been proposed that more closely model the costs for an attacker. This allows for convenient comparison between algorithms and is useful when combining multiple primitives in a hybrid cryptosystem, so there is no clear weakest link. For example, AES-128 (key size 128 bits) is designed to offer a 128-bit security level, which is considered roughly equivalent to 3072-bit RSA.

This NIST spec uses the same term of n-bit security

  SHA-1 does provide the 112 bits of preimage resistance that is needed
  to achieve the 112-bit security strength for HMAC


How used nonce in CTR Mode of AES-EAX Encryption? I want to encrypt a message with AES-EAX manually. Then, i confused how ctr mode in AES-EAX processing the nonce which came from omac process. How the counter be concatenate with the nonce in their primitive ctr mode if the nonce already 128-bit length because padding in omac before. My initial nonce length is 96-bit. Should i discard the auth nonce until 96-bit again and concatenate it with 32-bit of counter?

I tried to search that answer in google and didn't find that answer. I also compared my ciphertext calculation with ciphertext from application but it have different result. So, i hope i can find the answer in here. Please help me to know.
I really appreciate your answer.

I already figured it out myself. Lol
So, in paper "The EAX Mode of Operation" by M. Bellare, P. Rogaway, and D. Wagner explained that in CTR algorithm and i wasn't aware. The 128-bit auth nonce will be encrypt in ctr mode and concatenate with encrypted nonce+1 until encrypted nonce+m-1, which m is amount of block plaintext. And at last xor it with plaintext.


Is there a way to make RC4 (ARCFOUR) secure, or is it completely broken? I need a method to authenticate a process with another in order to establish interprocess communication between them, to prevent malicious processes from trying to hook onto the system. Currently I just send a password in plaintext between the two processes and the host process just performs a string comparison with its copy of the password, and will disconnect the connecting process if they don't match. It was fine when I was limited to connecting each process on localhost, but obviously this is not secure if someone just happens to have access to a network between each process and could sniff the packets. Do note that I only care about encryption for the password exchange and I don't really need it to secure the communication.

So basically I need a encryption algorithm that doesn't need to protect its contents well but does need to protect its key, and needs to be as fast as possible with minimal RAM usage and I/O overhead. Yes, data exchange is more CPU-bound than I/O bound since the two processes will be doing loads of calculations and they most likely will be connecting through localhost. Now, I came across RC4, which has a throughput of over twice that of AES-128, but it is evident that it has some weaknesses and I have a lot of questions about how to implement it in a secure way.

Well first question - it's in the title. Is RC4 completely broken and should be avoided? I hear a lot of "it is secure if properly used" and then a lot of "use of RC4 is discouraged."

I was planning to keep the plaintext password on both processes and have them SHA-224 hashed, and concatenate the hash with a 32-bit IV as a 256-bit key for RC4. Are there any security risks with this approach? Perhaps I could then hash the concatenated IV and hashed password with SHA-256? I'm well aware that WEP was cracked because it used a 24-bit IV, but a 32-bit IV has over four billion more unique values. Should I avoid incrementing the IV after each packet like WEP?

And when it comes to RC4-drop[n], what is a reasonable value for n? 256, 512, 768 bytes? How would you implement drop n on a library whose only public operation is encrypting a byte array - pass a byte array of length n after the engine is initialized with the key? Would that mean you would have to basically process n empty bytes after every time you change the IV (which happens after every packet)?

Sources: http://www.rsa.com/rsalabs/node.asp?id=2009

EDIT: after reading all these excellent responses, I realized how ignorant I sounded about the whole subject. I had no experience with cryptography before this day, and I only was able to read about RC4's risks from the limited Google results that I could barely follow. thank you to everyone who has been patient with me!

Correct me if I'm wrong, but I believe a better solution is to either use AES (which is not slower because re-keying RC4 after each packet is expensive) or an universal message authentication code. I can easily work with AES, but my understanding of MAC is a bit shaky. An IV is only secure if the update sequence is randomized and unpredictable, meaning I would have to send a 128 bit IV for every message that is sent, which can add a 400% overhead to the short, 4 byte packets that are commonly sent by my application. HMAC can add more than twice that amount if SHA-256 is used. I am going to have to investigate this matter further.

A few observations:

RC4 suffers from related key attacks. This means your idea of concatenating a 224 bit key and a 32 bit IV is not a good idea. You should rather use $\operatorname{SHA-256}(Key\mathbin\|IV)$
Remember that a (Key, IV) pair must not be reused, ever.
A 32 bit IV can work if it's a counter, but IMO such a scheme is unnecessarily fragile. I'd rather generate a new, random 128 bit value for each encryption.
Even with dropping, RC4 is still a bit biased. This can allow password recovery if an attacker can observe a few billion communications.
You don't protect data integrity. For example an attacker might keep the encrypted password intact, but change the rest of the message. I don't understand your problem well enough to know if that's a problem.
There might be replay attacks, where an attacker repeats an earlier message fully or in part.
Your assumption that RC4 is faster than other ciphers isn't necessarily true. On many modern systems AES is really fast. There are also other modern stream ciphers, such as Salsa20 which are fast and much stronger than RC4.
RC4 has costly initialization. So its only fast if you need to initialize it rarely. In particular if you reinitialize for each packet, its performance will certainly drop below AES.
Do you really need a cipher in the first place? You might be better off with a MAC. It seems like you're interested in authentication, not confidentiality. Universal MACs can be really fast.
User Passwords often have low entropy, so you need to strengthen them before using them as a key. Strengthening them is computationally expensive, and is done using KDFs, like scrypt or PBKDF2.
Consider using a high entropy key instead of a password.
If you use a constant key hardcoded into an executable, those executables may never run on untrusted machines. Else an attacker could simply extract the key out of the executable.

In short:

The weaknesses in your protocol are likely much more severe than the weaknesses in RC4.
There is little reason to use RC4 in a new protocol. There are fast and strong alternatives.


How to represent a 32-byte SHA2 hash in the shortest possible string? I'm calculating a SHA2 hash of a certain sensitive key value. I need to store files on disk using this hash a directory path prefix. So lets say I hash the key value 150023, I get a 32-byte value which in hex is 64-characters long - quite a long filename.

What's the shortest string I can get of this 32-byte hash, that would have some degree of uniqueness? I could use Base64 but that would be about 40 chars. Should I simply truncate the 32-byte hash value? Would it have frequent collisions if I used similar key values?

There are 94 printable ascii characters. Not all of which are valid for file names, however. There should be $64=2^6$ that are valid for file names, so read $6$ bits at a time and map those to one of the $64$ characters that are valid for file names. That would give you $256/6\approx 43$ characters. It will be hard to get much smaller than that.

That process is pretty much base64 anyways, so I'd stick with base64.

Truncation could work depending on your adversary model. What kind of collisions are you worried about? If you are only worried about random collisions, truncation would be fine. If you truncate to $128$ bit outputs, you would expect to see a collision after about $2^{64}$ files. If you are worried about malicious collisions, best to stick with the $\approx 43$ characters of base64.


Order and cofactor of the base point? What is the order and cofactor of a base point?
Is it possible to deduct the order and cofactor, given just the basepoint.
What about the other way around from order and cofactor to basepoint?

What is the order and cofactor of a base point?

Put simply, the order of the basepoint is the number of points the basepoint generates under repeated addition. If you have point $G$ and you repeatedly add $G$ to itself, you will eventually get the identity element $O$ (where $O + G = G$). The order of $G$ is the smallest $n$ where $nG = O$.

The cofactor is the order of the entire group (number of points on the curve) divided by the order of the subgroup generated by your basepoint. Because of Lagrange's theorm, we know that the number of elements of every subgroup divides the order of the group.

  Is it possible to deduct the order and cofactor, given just the basepoint. What about the other way around from order and cofactor to basepoint?

Not easily unless you know the order of the group.

There are algorithms for efficiently computing the order of an elliptic curve. After you know the order of the curve, you can factor it to find the size of its subgroups. Using the factors, you can test each one and find the order of any point.


How is Shamir's Secret Sharing better than this simple 2-password technique? I'm looking for a solution to protect a message, such that both password1 (usually given to trusted person #1) and password2 (given to trusted person #2) are required to decrypt the message.

Thus, person #1 alone or person #2 alone can't decrypt the message.

A solution seems to be given by Shamir's Secret Sharing (using finite field arithmetic).

Question: how is the following simple solution weaker than Shamir's solution, and which are the benefits of Shamir's solution over this:

ciphertext = encrypt(encrypt(plaintext, password1), password2)

(where encrypt is any traditional symmetric encryption solution)?

Example use-case (off-topic but just as an example): plaintext is your digital "will" (containing helpful passwords that you would like to transmit to your loved ones after your death), password1 is kept by your attorney/notary, password2 is given to your life partner.

PS: this simple and obvious technique is discussed here and here.

You've described an $n$-of-$n$ threshold encryption scheme by nesting: there are $n$ shares of a secret key, and it takes all $n$ of them (in the right order, so I hope you labeled them) to recover the plaintext.  Similarly, there's a simple $1$-of-$n$ threshold encryption scheme by concatenation, which is what, e.g., OpenPGP uses for multiple-recipient messages.

What neither of these handles is $k$-of-$n$ for $1 < k < n$; e.g., $2$-of-$3$, where you want to ensure that either

you and your solicitor, or
you and your mistress, or
your mistress and your solicitor,

can collaborate to recover the secret, but none of them individually can (and definitely not your husband).

Obviously, it is possible to compose nesting and concatenation to have the same effect—do $1$-of-$3$ where each share is a $2$-of-$2$ threshold system itself, for instance, like the list above—but there is a bit of a combinatorial explosion of overhead this way especially when $k \approx n/2$ so that the overhead grows as the central binomial coefficients.

In contrast, Shamir's secret-sharing scheme costs only $\log_2 n + b$ bits per share of a $b$-bit secret no matter what the threshold $k$ is, for a total of $n \log_2 n + n b$ bits of overhead, or $k \log_2 n + k b$ bits of storage to recover the secret.

Note that secret-sharing schemes are almost never what you want in practice (except, perhaps, for revealing deathbed secrets).

For example, if you jointly control a bank account, and you want to ensure any transfers out of the bank account are authorized by two of three signatories, it is a bad system to use a single signing key split up with a secret-sharing scheme—if you do that, then every time you sign a check, you necessarily reconstitute the single signing key, and whoever owns the computer on which you reconstituted it now has unilateral power to sign checks.

It is generally better to use threshold signatures, the simplest system of which is just the concatenation of signatures by distinct authorized parties.


Need for salt with IV I have mainly referred to this question. Definitely in case of using a salt, IV has a use of adding randomisation to each and every key. But isn't it redundant in case of using an IV to use a salt? (Like in case of referring to PBE with AES in CBC mode.)

(This is because in my understanding using the salt will make it not feasible to use rainbow tables or likes for brute force for each and every possible salt, and IV will further add randomisation to each and every message... But in case of using IV there will be randomisation in each and every message, so rainbow tables will not be feasible then also without using a salt.)

It sounds like you're using a password-based key derivation function that accepts an optional salt input to convert a passphrase into an encryption key, which you then use to encrypt messages with a block cipher mode (or possibly some other type of stream cipher) that takes an IV or a nonce, and you want to know whether it's necessary to provide a salt to the KDF, given that you're encrypting every message with a unique IV.

In general, the answer is "possibly, but at least using both won't hurt."

An IV and a salt really have two completely different security goals.  An IV is used as part of the encryption process, and its main purpose is to allow the same key to be securely used to encrypt multiple messages.*  If the same key and IV are used to encrypt more than one message, inspecting the ciphertexts can leak some information about the plaintexts.

(The exact information leaked depends on the cipher mode: for CBC and CFB modes, it includes the length of any common prefix shared by the messages, and possibly some information about the first cipher block that differs; for CTR and OFB modes, reusing the IV leaks the bitwise XOR of the full messages!)

A salt, on the other hand, is used in the key derivation process,** and its main purpose is to slow down certain kinds of brute-force password cracking attacks by, on one hand, ensuring that two users with the same passphrase won't end up with identical keys, and on the other hand, preventing attackers from precomputing passphrase/key combinations in advance.

(Some KDFs may also use the salt to allow multiple quasi-independent keys to be derived from the same passphrase, while other KDFs have a separate parameter for that.  Similarly, some cipher modes may also have additional requirements on the IV; for example, CBC mode needs an IV that is not only unique but also unpredictable to resist certain chosen-plaintext attacks.)

In particular, a password-based key derivation function should implement key stretching, i.e. it should be deliberately resource-intensive to compute in order to slow down brute force attacks.  Including a unique salt in this process is important, because it prevents an attacker from gaining a significant advantage by targeting multiple users in parallel.

Without a salt, an attacker could just run the slow key-derivation process once for each password, and then quickly test the resulting key against every captured message.  Salting the KDF forces the attacker to instead repeat the slow key derivation process for each user / message separately.  An IV will not help here, since it's applied only during the encryption step, after the slow key derivation process is over.

IVs don't really have any effect on brute-force password guessing attacks like this; the kind of attacks prevented by proper IV usage are plaintext-recovery (not key-recovery) attacks based on reusing the same key and IV to encrypt multiple message, which can leak information about the plaintexts for those messages.

Note that, if you're only encrypting a single message with each key produced by your KDF, then you may be able to safely use a fixed IV.  But in that case, you definitely need to use a per-message salt in your KDF, to guarantee that the keys will really be unique.  In any case, even if not strictly necessary in this case, using a random unique IV is still the safe default choice.

Ps. In any case, you really should be using an authenticated encryption mode instead of plain CBC to protect against active tampering attacks.  Among such modes, I'd like to particularly mention SIV mode (RFC 5297), which is designed to offer extra resistance against accidental IV reuse.

*) At least, that's true of the kind of IVs we're talking about here.  More generally, the term "IV" really just means "initialization vector", and is used for all sorts of algorithms, like hash functions, that involve iteratively processing blocks or "vectors" of data.  Alas, the terminology is probably too entrenched to change at this point.

**) Salts are also used for password hashing in password-based authentication schemes.  Actually, password hashing and key derivation are very similar tasks, and so the algorithms and terminology are mostly the same.

Related links:

What is the main difference between a key, an IV and a nonce?
Can you help me understand what a cryptographic "salt" is?
Why should I use an Initialization Vector (IV) when I have unique keys?


How to impelement mapping point Curve25519 to weierstrass point? I am implementing a ECDH using Curve25519 to communicate two system. One system have library that use for weierstrass curve only, it can define with domain parameter like p, a, b, G_x, G_y. I have read and find that Curve25519 can converse to weierstrass, I can find that converse domain paramerter for Curve25519 here (https://tools.ietf.org/id/draft-ietf-lwig-curve-representations-02.html). After that, I need converse point from Curve25519 to weierstrass, I find the mapping is (u,v) -> (x, y) = (u + A/3, v) but I do not understand that. Example with base point of Curve25519, (u, v) = (0x9, 0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9), after converse in weierstrass, base point is (0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaad245a, 0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9), with A = 486662, B = 1. That seem not correct with mapping, so is that operator devision is not normal division. What exactly I need to converse point in form Curve25519 to weierstrass curve, thank you.

I'm not sure what is your question, I'm assuming you are not understanding why the mapping gives that particular result...

In ECC, all computations are carried out in a finite field. For Curve25519, all computations are done modulo $p = 2^{255}-19$.

To compute $u + A/3$, the division by three is actually $A$ multiplied by the inverse of $3$ modulo $p$. This inverse is the value that, when multiplied by 3, given 1 modulo $p$. This inverse is 0x5555555555555555555555555555555555555555555555555555555555555549; you can check that if you multiply this by $3$ and compute the remainder of the division by $p$ it will give $1$. Carring out the rest of the computation (always reducing modulo $p$) will give the expected result 0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad245a.

The modular inverse can be computed using the extended Euclidean algorithm or using Euler's theorem (which is computing the exponentiation by $p-2$).


What are the security implications of multiple hashing? There are plenty of questions on this site about hashing passwords. However, none of them quite cover this topic. One of those links covers using multiple different hash algorithms; one covers general hashing, and the other covers how passwords should be transferred. However, I want to know what the security implications of using one hash function multiple times.

I came across an article a while ago saying that this is not a good idea. However, I want some definitive answers. So, what are the security implications, good or bad, of using a hash system like this:

hash(hash(hash(password) + salt) + pepper)

In other words, hashing the password, then hashing the hash of the password with the salt, then hashing this hash with the pepper.

Multiple hashing, in itself, is not a bad idea.  What's bad is trying to design your own non-standard password hashing scheme, without understanding what features such a scheme needs in order to be secure.

In fact, hashing the password many times can be a very good idea, as long as you do it sufficiently many times.  This is one way to slow down the hashing process, and so make it more resistant to brute force cracking attempts, a technique known as key stretching.  This is something any good modern password hashing scheme should do, and the way many such schemes, like PBKDF2, do it is, in effect, by hashing the password many times.

As for your example of hash(hash(hash(password) + salt) + pepper), this will not, in general, be any weaker than just hash(password + salt + pepper), but it's also not significantly stronger.  To achieve any kind of useful key stretching, you need to iterate the hash at least 1,000 times, and preferably closer to 1,000,000 times (or however many iterations the user is willing to wait for).

Ps. For anyone thinking of designing their own password hashing scheme, or evaluating the security of an existing scheme, here's a quick checklist of the properties such a scheme should, at a minimum, have:

It should not be possible to reconstruct any information about the password directly from the hash.  (This is a very basic requirement.  Even a single application of any cryptographic hash function, like the SHA-2 functions, is enough to ensure this.)
The hash should accept arbitrarily long passphrases, and should depend on every bit of the passphrase.  (Again, this requirement should be obvious, but some very old and/or very badly designed hashing schemes like DES-crypt may fail it.)  If, for the sake of usability, some features of the passphrase (like surrounding whitespace or letter case) are deliberately ignored, the user should be clearly informed of this before they select their passphrase.
The hash should be salted, so that two users having the same password will not get the same hash.  Ideally, the salt should be globally unique and unpredictable; it should certainly not be just the username.  A sufficiently long random string (e.g. 10 or more base64 chars) is OK, but ideally the salt should also comprise other hopefully unique elements (like, say, an SHA hash of the username, server ID and a timestamp) to ensure uniqueness even if the random number generator fails.
In addition to the salt, the hashing scheme may depend on a secret key (sometimes called "pepper").  However, its security should never depend solely on this key remaining secret.
The hashing scheme should be resistant to brute force attacks, meaning that the hash should be slow to compute.  This can be achieved by iterated hashing, as described above, or by other constructions designed for the purpose (as in scrypt).  The slowness should be controlled by an adjustable parameter (and, ideally, should adjust itself to available hardware).  In particular, there should not be any "shortcuts" for checking the validity of a password significantly faster than by the standard method your code uses.  If possible, the hashing scheme should also be designed to be unsuitable for massively parallel implementation (e.g. on a GPU; scrypt is designed like this, PBKDF2 is not).  Also, if possible, in client–server applications, most of the hashing effort should be offloaded to the client (but the server-side part of the hashing scheme should still be secure by itself, even if the client misbehaves).
The users should be encouraged to choose long, randomly generated but easily memorizable passphrases (such as those generated by diceware).  To that end, the user interface may automatically generate and suggest such passphrases to the user.  (If so, care should be taken to ensure that the random number generator used is of high quality, and that the passphrases cannot be captured by an attacker.)  The user should not be forced to comply with inefficient and artificial requirements like "password must contain at least one number", although passwords using a diverse set of characters (including non-ASCII Unicode characters) should certainly not be forbidden (or, worse yet, stripped of such characters).


Question on the remote coin flipping problem I decided to ask the question here, because although the problem is mathematical, I'm interested in its application here. In the version i read in wikipedia, they suggested the following method for Alice and Bob to agree on a coin flip result from afar:

1)Alice gives Bob a commitment(a box), which contains her 'call', but Bob dosent know what it is.

2)Bob performs the flip and reports the result to Alice.

3)Alice tells the 'key' to Bob who now learns her 'call'. If the call matches the report, Alice wins, else Bob does.

First of all, I want to know how this 'box' is actually implemented, in a relevant crypto system. Based on how the 'box' is actually defined, Alice can always win as follows:
(We assume a 'box' to be a secure file, whose contents are absolutely unknown to Bob. Name this file F)

1)Alice gives Bob the 'box' which contains both possible calls 'tail' and 'heads' of the coin flip(but obviously Bob dosent know anything about the contents by the definition used above).

2)Bob performs the flip and reports the result to Alice(let it be heads).

3)Alice supplies the corresponding key $k_h$ to Bob, such that:
 $k_h(F) = 'heads'$, and alice inevitably wins.(if Bob reported tails, she would supply $k_t$ such that $k_t(F) = 'tails'$)

Basically the file here is a 2-key container, which returns a different result based on the key used. Is the definition of 'box' i gave wrong? What is the correct definition?

Is the definition of 'box' i gave wrong? What is the correct definition?

It is incorrect.

The analogous description of a commitment scheme would be that it is a box that contains only one choice (for example, "heads" or "tails"), Alice can place either, and Bob can't tell (by looking at the box) which is in it.

Later, Alice can open the box; Bob can then tell what's in it and (here's the key point) Alice can't change her mind what's in the box.

With this definition, this is a secure coin flip protocol (except that when Alice learns Bob's choice, she can walk away without opening the box; that needs to be handled somehow).

The easiest way to implement a commitment scheme is with a cryptographical hash function; Alice picks the secret value she's putting into the commitment and a long random nonce, she hashes them both together:

$$Commitment = Hash( Secret || Nonce )$$

She then sends the hash to Bob.  Bob, by looking at the hash, can't recover the commitment (because of the random nonce).  Then, Alice opens the commitment by revealing the secret and the nonce; Bob verifies the secret by hashing the revealed secret and nonce together to recompute the original commitment.  If the Hash used is collision resistant (that is, we can't find two distinct values that hash to the same value), then Alice can't have a single commitment that can open to two different value (because that would imply two different $Secret || Nonce$ values that hash to the same thing, and we assume Alice can't find such a pair).


Does this equation hold in a bilinear map? I would like to verify whether or not the following equation holds:

$e(a,c)^{c1\cdot c2\cdot c3}e(b,c)^{c1\cdot c2\cdot c4}==e(a,c)^{c2\cdot c3}e(b,c)^{c1^2\cdot c2\cdot c4}$ for appropriately defined bilinear map $e$ with different input groups $G_1$ and $G_2$ for $a,b\in G_1$ and $c\in G_2$

No it does not. To see it, take $b=1$:

$e(a,c)^{c1\cdot c2\cdot c3}e(b,c)^{c1\cdot c2\cdot c4}= e(a,c)^{c1\cdot c2\cdot c3}e(1,c)^{c1\cdot c2\cdot c4} = e(a,c)^{c1\cdot c2\cdot c3}1^{c1\cdot c2\cdot c4} = e(a,c)^{c1\cdot c2\cdot c3}$

similarly,

$e(a,c)^{c2\cdot c3}e(b,c)^{c1^2\cdot c2\cdot c4} = e(a,c)^{c2\cdot c3}$

So you would get

$e(a,c)^{c1\cdot c2\cdot c3} = e(a,c)^{c2\cdot c3}$

which is clearly not true in general (unless $c_1 = 1$ or $c_1 = 0$ or $e(a,c) = 1$).


Is it possible to truncate AES output and keep uniqueness (no decryption needed)? I would like to hash numbers less than 1000000000, so generally they could be stored on 30 bits. The aim is to obtain numbers that are not reversible, so my initial plan was to use SHA256 (with some salt). However, I would like to keep the output as short as possible, but I want to be sure that there are no collisions. Hash functions do not guarantee me that-- especially when I truncate their output. Probably I could check if there are collisions for my numbers, but maybe there is some better way?

Is it possible to reduce the size of the output of AES and keep uniqueness-- assuming that I don't need to decrypt and it is even desired to not be able to do so? Maybe divide each output into four parts and XOR all of them to get a 32-bit output?

For the parameters you gave, the birthday paradox will kick in and you will get collisions, since the set of integers you want to process is much larger than $\sqrt{2^{30}}$.

A very simple countermeasure would be for input $x_k$ to use bits $(y_{k,1}\ldots,y_{k,30})$ of the AES output
$$
(y_{k,1}\ldots,y_{k,128}):=AES_K(x_k)
$$
(for a fixed randomly chosen secret key $K$, you can use some fixed padding on $x$ if you wish).

Say you you have processed $x_1,x_2,\ldots,x_m$ with no collision and placed the outputs
$$
(y_{1,1}\ldots,y_{1,30}),\ldots, (y_{m,1}\ldots,y_{m,30}),
$$
in a sorted list. Say $(y_{m+1,1}\ldots,y_{m+1,30})$
collides with a previously chosen output vector. Then keep checking
$$
(y_{m+1,j},\ldots,y_{m+1,j+29}),\quad j\geq 2,
$$
until you get a 30 bit pattern that doesn't collide with that vector. Due to the good randomness properties of AES this will succeed in a few iterations after each collision, with high probability.

You can then store the cordinate index  $j_x$  used to generate this vector together  with $x_{m+1}$ if reproducibility is required.


How is a PRNG used in the PGP? I'm currently reading up on the components of PGP and I am wondering what exactly the PRNG is used for. PGP uses ANSI X9.17 and entropy from a users keystrokes to generate a temporary key.

So, is this temporary key used for the public key encryption? Is it one of the keys in the key pairs? And how does PGP actually generate it's key pairs?

(Open)PGP is a hybrid encryption system, it uses both public/private and symmetric key encryption. Public/private key encryption is very inefficient for any kind of data but very small one, so when encrypting for some private key, usually you're only encrypting some block cipher which is then used to actually encrypt the data.

For generating this key, a random number generator is used.


What are some good references for the implementation weaknesses in RSA I'm pretty sure I understand textbook RSA.

Choose p and q, large primes, and compute n=pq.
Choose e such that $gcd(\phi(n),e)=1.$
Publish n and e.
Compute d such that $de=1$ (mod $\phi(n)$).
To encrypt a message M, compute E=M^e (mod n).
To decrypt, compute D=E^d (mod n), which will equal M.

There are obvious things we need to do to make this not obviously insecure, such as choose p and q large enough, but not too close together.  It also helps if the ratio between p and q is not a simple rational like 2/3 or 4/7.  We also need the private exponent d to be similarly large.

But there are less obvious precautions needed.  A simple example is that we need to pad M, but there are others.

What is a good reference to understand the other attacks on (implementations of) RSA, and how RSA can be hardened against them?

Thanks.

It depends on what you are using RSA for and how deep of an understanding you would like.

A sort of general overview of RSA and potential attacks against textbook RSA is presented in the Handbook of Applied Cryptography, specifically chapter 8. (Note that the entire text is free online.) Chapters 11 and 12 also are useful to read, as they focus on specific instances of RSA. This will give you a good, brief understanding of the generics of RSA, but I wouldn't go implementing the algorithm straight out of the HAC.

Instead, if you'd like to know a good standard for implementing RSA in specific instances, I'd recommend one of the many standards on the subject (PKCS, FIPS, ISO, ...). On Wikipedia, you can find this List of PKCS. You might be interested in PKCS#1. Note that the actual RSA Labs maintains a PKCS list of its own, where you can find PDFs of the various PKCS (usually: that or .ps files). I find PDFs infinitely more pleasing to read than RFCs, so that might pique your interest.

Further, the NIST maintains a Current FIPS list. So, for example, if you were interested in using RSA for signatures, you might look at FIPS 186-3.

PKCS and FIPS aren't big on theory, however, so if you are looking for a good theoretical understanding, the HAC is probably your best bet. You might also want to look up actual published attacks in the literature. For example, searching rsa padding returns many useful results, e.g. Why textbook ElGamal and RSA are insecure by Boneh, Joux, and Nguyen. That isn't so much a reference for secure implementation, but it certainly highlights the possible attacks on the textbook implementation.

Also, you probably want to look at other known-good implementations like GPG and OpenSSL.


How common are SEED certificates outside of Korea? When is support required? I'm looking at the SEED algorithm and would like to know if this is still in common usage.

Can anyone tell me when I would need to implement this standard, either as a client or a server?

I believe the Wikipedia article about the SEED block cipher sums it up nicely.

SEED is pretty much ubiquitous in Korea, and unused outside of the country. I'm not sure if this article is still accurate, but it does give an idea of the history of SEED in Korea: "the cost of monoculture".

If you work with Korean clients, and they demand that you support it, you should certainly implement it. Otherwise, I don't see any reason to do so.


Why is prime number size important for RSA security? RSA modulus is $N = pq$ where $p$ and $q$ are prime numbers. I read from somewhere that the time it takes to decrypt the RSA encryption increases exponentially as key length increases, which depends on the value of $N$, which in turn, depends on $p$ and $q$. Are there any mathematical proof to explain this phenomenon?

In RSA with modulus $n$, the legitimate user's cost to encrypt a message is $(\log_2 n) (\log_2 \log_2 n)^{1 + o(1)}$ bit operations, with the best public exponent $e = 3$; and to decrypt a message (if you know the secret exponent) is $(\log_2 n) (\log_2 \log_2 n)^{2 + o(1)}$ bit operations.  This is most assuredly not exponential in $n$ or even in the size $\log_2 n$ of $n$, and it is quite fast in concrete terms—to measure how fast it is, you can run openssl speed rsa4096 in the privacy of your own living room!  You can also consult the SUPERCOP benchmarks for measurements on a wide variety of computers to see the concrete speeds.

What about the attacker's cost to decrypt in RSA without knowing the private key?

If $n = pq$ for $p < q$, the cost of the elliptic curve method of factorization (ECM) is $L^{\sqrt{2} + o(1)}$ where $L = e^{(\log p)^{1/2} (\log \log p)^{1/2}}$.  This is the best-known classical method of factoring that depends on the size of a factor, so the factors must be chosen large enough to put this out of reach.  This is neither a polynomial function, nor an exponential function, but somewhere in the middle: $e^{(\log p)^\alpha (\log \log p)^{1 - \alpha}}$ is polynomial in $\log p$ when $\alpha = 0$ and exponential in $\log p$ when $\alpha = 1$, but here $\alpha = 1/2$.  But, of course, what is really interesting is not the asymptotic growth curves of attack costs, but the concrete attack costs for specific parameter sizes.  Based on experimental evidence of ECM performance[1], to make sure that the cost is near $2^{128}$ we can set $p \approx 2^{1024}$ for a ‘128-bit security level’.

There are other methods of factoring:

The number field sieve (NFS) costs about $L^{1.704\dots + o(1)}$ per key in a large batch attack[2], where $L = e^{(\log n)^{1/3} (\log \log n)^{2/3}}$.  Note that this cost depends on the size of $n$ rather than on the size of its factor $p$.  For a 128-bit security level, we need to set $n \approx 3584$.

If we had a large quantum computer:

Shor's algorithm costs about $(\log_2 n)^{2 + o(1)}$ qubit operations.  If large quantum computers ever became feasible, then for a >100-bit security level, we would need $n \approx 2^{2^{43}}$, i.e. a terabyte modulus[3].
Grover-optimized ECM costs about $L^{1 + o(1)}$ where $L = e^{(\log p)^{1/2} (\log \log p)^{1/2}}$, which requires us to use somewhat larger primes.  If large quantum computers ever became feasible, then for a >100-bit security level, we would need $p \approx 2^{2048}$, though cryptographers recommend $p \approx 2^{4096}$ until quantum computing is better understood[3].

(Combining the attack costs of Shor and Grover-ECM, it is cheapest for the legitimate user if we use multi-prime RSA with $n = p_1 p_2 \cdots p_\ell$ where $p_i \approx 2^{4096}$ and $\ell \approx 2^{32}$, i.e. four billion factors.)


Optimized Garbled Circuit Algorithmic Description The Garbled Circuit (GC) is now over thirty years old, and many optimization methodologies have been proposed, including point-and-permute, row-reduction, free-XOR, fixed-key blockcipher, half-and.

But, after Googling papers and forums, I can't find any concrete algorithmic descriptions which includes all of these optimizations. Does anyone know the exact descriptions of optimized GCs?

I ask because I need to implement the algorithm for personal use.

Not all optimizations of garbled circuits are compatible with each other. Are you interested in implementing all of the different combinations? If not, the Half Gates paper already gives a formal description of the scheme, which includes point-permute, fixed-key block cipher, free-XOR. This should represent the state-of-the-art combination of GC optimizations. There is a good implementation of half-gates in the Ivory project.


Security for IV in AES-GCM mode I'd like to use AES-GCM instead of HMAC for authentication and privacy in a token used in a web application, but I'm unsure how to securely tag each token with an IV. Is it safe for me to prepend the IV in front of the AES-GCM data, or do I need to protect it somehow?

It is indeed safe to send it along with the ciphertext; the attacker can't learn anything from it (other than possibly how many packets has been generated so far, if you use a counter to generate the IVs), and if the attacker modifies the IV, the resulting message will fail to decrypt (with high probability).

Existing protocols that can use GCM (TLS, IPSec) do exactly that: prepend the IV in front of the AES-GCM data.


How can create a proof that we have a sequence of binary digits? Given a sequence of bits (either a 0 or 1), for example:

0110100110110001

How can one create a proof that we have this bit sequence, without actually revealing the bit sequence?

I know that there are several examples of proof mediums, such as polynomials for zk-SNARKs, however, how would one go about defining a proof medium for the above question?

EDIT: This bit sequence is derived from some input x which passes through some arithmetic circuit C in which a set of environmental conditions (i.e. delay) determine the propagation through paths, such that (for example) the first path to the goal will be associated with a 1, else 0, which ultimately make up a sequence of bits.

If I understand correctly, you're asking to prove that you have the result of running a secret input through a public process without revealing anything about this result.

For this proof to be an interesting one, you would have to output some value and then prove how it relates to the values you're hiding. If you don't do that, then you're simply proving that you ran any value through a public process. Since anybody can run values through a public process, this wouldn't be interesting. Does that make sense?

In other words, it's important that you figure out what is interesting about your proof. i.e. is there some fixed secret information you would need to have to prove what you're trying to prove?

If you reveal, say, the encryption $c$ of the bit string under a public key $pk$. Then proving that $c$ is the encryption under $pk$ of some bitstring $y$ seems like it could be interesting. You would probably also have to prove that $pk$ was generated honestly. Assuming unique decryption, this combination of proofs will fix the witness $(x,sk)$ which leads to the output $(c,pk)$.

This proof can be framed as an NP language where the value $(c,pk)$ has witness $(x,sk)$. You can then use standard zero-knowledge.


Check if $a<b$ in a trustless scenario Let's say Alice has access only to a value $a$ and Bob has access to both $a$ and $b$. I need Alice to be able to check whether $a<b$ holds, like a relaxed version of the Yao's Millionaire Problem, given that one of them knows both values. The challenge is that the comparison result cannot be trusted if done by Bob, as he may be biased.

Therefore, I thought of two approaches for this problem:

Check whether Bob was honest in his evaluation of $a<b$, maybe by
using ZK-proof; or
Somehow enable Alice to do the comparison
herself without exposing $b$, so that:
$$a < enc_{pk}(b) \iff a<b $$

Which one do you think it would be better to tackle and how?

EDIT: You can assume that both $a$ and $b$ are well defined by a commitment scheme before the evaluation is done.

This is a common misunderstanding of zero knowledge. In order to prove something in zero knowledge (in fact, in order to prove anything in a way that is non-trivial), there must a well defined statement. See https://crypto.stackexchange.com/a/60633/25354 for an explanation of this.

Note that in your context, it is always true that there exists some $b$ such that $a<b$ (over the integers). Thus, without having some commitment or encryption of $b$ before the proof starts, this is trivially always true.


Breaking a XOR cipher of known key length? For a challenge, I need to find the key that enciphered a text.

I know that the key is of length N (invariable). There is no assurance that the key is only alphabetical or alphanumeric, but it could be a reasonable assumption.

I know that the original text is alphabetical only, no number, but there is no assurance that the text is lowercase or uppercase only. It would be a reasonable assumption that the text has lowercase and uppercase characters.

The actual encryption is similar to the one of a Vigenere cipher, in that it uses a rolling key to XOR the input, character by character going like (pseudo code, don't try to run this in any language) :

ciphertext = ""
n = 0 ; //key iterator
for character in input:
    ciphertext += key[n] XOR character;
    n++;
    if(c >= N) { // reset key iterator when reaching the known length of the key
        c = 0;
    }
return ciphertext

The output is not directly usable as text and the input has both uppercase and lowercase characters.

How should I go about breaking the encrypted text ?

What I thought about:

Extract from the encrypted text the characters encrypted by the same letter of the key, for example, isolate all characters encrypted with key[0], and run statistical analysis on it.
My problem is that the presence of uppercase and lowercase letters makes statistical analysis difficult, being unable to differentiate the same letters in uppercase or lowercase. We now have 52 possible letters instead of 26, on a text that is too short to use this method. (around 450 characters, for a 8char long key, it means only 56char by set)

Go the known plaintext way, trying to find commonly used words. The problem is that he text is most likely either in french, or english, and the longer the word, the most likely it is that it's not present in the text. I think this is a last resort solution.

Simply bruteforce the text. Assuming a key length of 8char, with a charset of 0-9a-zA-Z, we've got 62^8 (several hundreds thousands of billions) possible permutations, which is impossible to cover.

What could I do to resolve this, or reduce the time it would take to solve ?
I was wondering is there was a way to know if the input text is either in lowercase or uppercase from the encrypted text, or if there is a way to manipulate the encrypted text to put it all in uppercase ... That would help with the statistical analysis a bit, even if I won't most likely have not enough data for a quality analysis.

After more time on this challenge, here is what I've done to solve it.

Divide the text by N columns, where N is the length of your key.

Run frequency analysis on each column. Given enough data, you will most likely get a character that is present far more often than the others. Since my text was in french, it was the letter e.

For each column, find one instance of the value that is supposed to be an 'e' and XOR that data with the letter 'e' to find the Nth letter of the key.

Given enough data, you will find an 'e' for every column, giving you all the letters of the key.
Try decrypting the text with the key, and voilà, you get the original text.

Once I've made up this way of solving the puzzle, I found out that it was a really common way to solve a XOR encryption, and that tools existed that could do it for you far faster than manually.

For example, xortool : https://github.com/hellman/xortool

xortool -l 8 input.bin -c65

-l is the length of the key, -c is the hexadecimal value of the most frequent letter in the language you think the text is in.

That command is near instantaneous.


Is it possible to get better randomness by using multiple PRNGs? I don't know if this question even makes sense, but:

Is there be any benefit or impact to some sort of hierarchical (e.g. a PRNG drives the decision for which PRN to pull from a set of PRNGs) or state-based model (e.g. a PRNG determines the next PRNG to pull from, which in turn determines the next, etc.) or combination thereof. Or might this somehow lead to a less-random output.

If there is some benefit to the aforementioned, then what about the difference between using multiple PRNGs with same implementation using different seeds, versus using multiple different PRNG implementations.

There are many ways to combine random number generators:

XOR the outputs. Very simple and fast. If they are independent and at least one is strong, the output is strong as well. However, if those assumptions are not true, this can be very broken.
Hash the outputs. With a strong hash you combine the entropy of both. Good if the RNGs have some entropy, but their output is not uniform. Can be significantly slower, if your RNGs are fast.
Seed one using the other. Mostly used for seeding a CSPRNG with a true RNG. If the former is weak or the latter doesn't have enough entropy, the whole is weak as well.
Entropy pool, with multiple inputs combined into a large state, which is iterated to produce the next state and hashed to produce output. Can include pseudo-random inputs, but a normal PRNG is not a good input.

In practice, if you have a CSPRNG, seeding with a random number (3.) is the only one you should be concerned with. If you have poor, non-cryptographic PRNGs, no games you play with the outputs will get you anything better than (or usually even as good as) simply moving to a CSPRNG.

An entropy pool is usually already available in the OS (/dev/urandom or CryptGenRandom), so there are few situations where you should go there yourself. Number 2. is often used in TRNGs for whitening, but that too is not something you should usually need to be doing in software. Maybe, if paranoid about the design, you could be seeding two completely different CSPRNGs with true entropy, then XORing the outputs, but then you are trusting on them to really be independent.


Is this cumbersome strategy to produce a ridiculously strong password valid? I'm writing something where somebody wants to have a ridiculously strong password for a file and yet be sure that he will always be able to reconstruct it. The way I have thought of this might be a little cumbersome, but as long as it works and makes sense, I'm happy with it. First I'll explain how my character derives his password, and then the issues I'm having.
Password derivation
My character will start from a sentence describing something only he knows. Then he will transform it so that it wouldn't look like a sentence to anybody (remove spaces, replace letters with numbers or symbols at random places, replace syllables with similar-sounding ones, random capitalisation, etc.) leading to what we'll call the base password.
Not happy with this level of security, he wants to generate a much higher-entropy password by running the base password through an encryption algorithm a certain number of times. There are very subtle hints that will remind him what algorithm and key he needs to use, and how many times the base password needs to be run through it. The final result is the file password. (He doesn't need to open the file often so it's alright to have to go through the hassle when he does need to open it.)
I did a test using Twofish and running a base password through it a few times. I got this stuff:

rvXRimTU7jhLxCZCe+9hCafIj/5nwZ4eK4pDJOxi5+8yulVzG6h61bZBIK5E2fCcHiG65HaoybnhH9/2l2VnGjWiqH44Snr9iSGInq0vwApJUAalYMJRDwXNQh2yOr6yRtqA+CtWZrbCu86IGjLy6NB5C75ko3khsz342JW94Uj7GrZDZWKee3M2KB3O76QbXtVB8EiBhuvoHeeEOvskeJdw5qAfPw42j4aQdAdcfc6Qo1cHIh20piWy8xrnvywViXM1tpEFBezbPXHBFjCUp1vFJAFf/vDl9SMA7pD7B190jZxQHpltAJeQXJxwAoM64fvxGTNx/Cieo4s+WHnCTA==

Questions and issues

To me, the resulting file password looks high-entropy enough. Unless an attacker can guess the original sentence, how it was turned into the base password, and gets the hint revealing the algorithm used to scramble it, I doubt anyone could brute-force that file. Yes, they could hit the character with a wrench until he reveals how to get the file password and stuff like that, but we don't care about that. We only care whether the file password is high-entropy or not. Do you guys agree that it's high-entropy?

I used an online tool to do my test, and that's when I was reminded that encryption algorithms often use "salts" to make the result different each time even though you encrypt the same data with the same key. Clearly, this is a problem, because if salt is used then our character will never get the same password again. Is salt the only factor that adds randomness in Twofish, or is there other stuff I need to take into account? (I can simply assume he is using an implementation that excludes all randomness and always generates the same file password from the same base password, provided the correct key is used and the algorithm is iterated the correct number of times.)

I was rather disappointed to see that different online tools for text encryption are utterly incapable of correctly decrypting each other's output even with the same settings and the correct key. The result is invariably gibberish. This is going to be an extremely dumb question, but I guess this depends on the implementation, and that if we had two professional tools implementing Twofish, they should be able to decrypt each other's output given the correct key and the same settings? (If this wasn't the case, other people in the story would never be able to access the encrypted file.)

Is the method I outlined sensible, from a security standpoint?

This is a broadly sub-optimal strategy because it violates Kerckhoffs's principle: if the attacker knows as much about the steps you're describing as you do, and only lacks the core secret, then most of these steps become useless for increasing the security of the secret.
Put another way: the steps that you're describing aren't actually increasing the entropy by any significant amount.
It sounds like this use case depends on the "survival" of the secret holder - to be alive and conscious enough to be able to always produce the secret from memory? If so,  the optimal strategy is probably:

maximizing the "memorizable" entropy of the input - a randomly generated passphrase, memorized, in the style of XKCD 936, using a mnemonic narrative constructed around it after the fact to aid recall - but with more entropy (five or six words drawn from a dictionary of 20,000 words or more), in order to be bruteforce-resistant even if stored with a weak/fast hash

maximizing the cracking resistance of the output - a true KDF like high-work-factor bcrypt or well-tuned scrypt (which are well-covered elsewhere). These are better because they are cracking-resistant even when their algorithms are public knowledge.

But really, since you often don't have control over how the input is stored (hashes), it's the first step that really matters - because even a weak hash will protect a strong password.
And if you're constrained to using the KDF that's built into the file storage format, the second step wouldn't apply at all - because you wouldn't have access to the salt because it would be hidden inside the document's hash. So you'd have to store it somewhere, which would be fragile.
So for your use case, it's probably best to let the secret (as a random passphrase) do the work.


What are the values of $w$ such that the corresponding $\text{Keccak-}f[25w]$ function is invertible (bijective)? From this answer, I see that from a mathematical point of view, one could define the $\text{Keccak-}f[25w]$ permutation for an arbitrary value of $w$.

I am interested in the following question: disregarding all properties of the resulting function except the invertibility (because $\text{Keccak-}f[25w]$ is required to be a permutation), is it true that if the value of $w$ is a multiple of $8$ and not a multiple of $5$, the corresponding $\text{Keccak-}f[25w]$ function is invertible (and bijective)? If the answer is “No”, then how to determine whether a particular $w$ is suitable (assuming that $w$ is required to be a multiple of $8$)?

$\operatorname{Keccak-}\!f[25w]$ is defined, by the Keccak specification, only when $w = 2^\ell$ for some $\ell$, and in all such cases it is a permutation.  The choices 1, 2, and 4 for $w$ are not multiples of 8.  No multiple of 5 is a power of 2 and consequently $w$ is never a multiple of 5.


What attacks does future secrecy protect against? Consider messaging between 2 parties. A sequence of messages are exchanged between the parties using encryption. We consider an attacker that has at a minimum a log of all the (encrypted) messages sent between the two parties.

Forward Secrecy: encryption keys are constantly updated in a non-reversible way, this means that if the attacker gains key $K_i$ they can derive $K_{i+1}$, $K_{i+2}$ and so on and decrypt message $M_i, M_{i+1}, M_{i+2}$ but they cannot decrypt any previous messages.

Future Secrecy: Like the Axolotl double ratchet, both sides constantly generate new public/private key pairs and only the public parts are exchanged over the communication channel. This means that if the attacker gains private keys $AK_i$ and/or $BK_i$ they can decrypt a finite number of messages $M_i$ or maybe $M_i, M_{i+1}$ but they cannot decrypt any further messages. They also can't decrypt previous messages.

What I don't understand is the security value of future secrecy.

  What kind of attack situation would future secrecy protect against?

It seems like an attacker would have to have exploited one of the messaging devices and read those temporary private keys from its memory - but then couldn't it just read the decrypted messages from memory and not bother with a cryptographic attack?

It seems like an attacker would have to have exploited one of the messaging devices and read those temporary private keys from its memory - but then couldn't it just read the decrypted messages from memory and not bother with a cryptographic attack?

It is assumed that the messaging devices erase the decrypted messages (and expired private keys) from memory, hence there's nothing to read.


questions about modular reduction algorithm over $F_{2^m}$ So I'm trying to understand algorithm 2.40 (arbitrary reduction polynomials) from the Guide to Elliptic Curve Cryptography and have some questions.

The very first sentence of this section says this:

  Recall that $f(z) = z^m +r(z)$, where $r(z)$ is a binary polynomial of degree at most $m − 1$

So let's take sect113r1. $f(x)$ is $x^{113}+x^9+1$. It seems like $z^m$ would be $x^{113}$ and $r(z)$ would be $x^9+1$. Is that a correct assumption?
The algorithm uses $c$ and $C$ and I'm wondering if they're the same thing. Like it says this:

  INPUT: A binary polynomial $c(z)$ of degree at most $2m −2$.

...and it also says this:

  Add $u_k(z)$ to $C\{j\}$.

$C\{j\}$ is defined thusly:

  The following notation is used: if $C = (C[n], . . .,C[2],C[1],C[0])$ is an array, then $C\{j\}$ denotes the truncated array $(C[n], . . .,C[ j +1],C[ j ])$.

The thing is... $C$ is not defined prior to the "Add" line. So it seems to me that either $C$ and $c$ are supposed to be the same thing or $C$ is supposed to be pre-initialized to all 0's?
So for the "Add $u_k(z)$ to $C\{j\}$" step...  I assume that means to add by doing XOR? What if $u_k(z)$ and $C\{j\}$ are of different sizes? Do we pad both of them with 0's on the right or left side?
So let's say $W$ equals 8. That means that the largest value of $u_k(z)$ is going to be $z^7r(z)$, which, assuming my understanding in #1 was correct, would mean that, for sect113r1, that it'd be $x^{16}+x^7$. So we add that (perhaps simply by doing XOR, per question #3) to $C\{j\}$ (which I asked about in question #2). The concern I have is...  let's say $C\{j\}$ is 0. At that point the result would be $x^{16}+x^7$, which is bigger than $W$ and I'd kinda expect it to less than $W$. Otherwise it's not really clear to me what that algorithm is supposed to be returning. Like maybe each element could be a digit in a bigint with a limb size equal to $W$?
In the last step it says "Return$(C[t−1], . . .,C[1],C[0])$". What is $t$ supposed to be? It's not defined or referenced anywhere else. Maybe it's supposed to be the length of C?

So let's take sect113r1. $f(x)$ is $x^{113}+x^9+1$. It seems like $z^m$ would be $x^{113}$ and $r(z)$ would be $x^9+1$. Is that a correct assumption?

Correct, we have $m = 113$, hence $z^m = z^{113}$ and $r(z) = z^9 + 1$.

  The algorithm uses $c$ and $C$ and I'm wondering if they're the same thing.

They are very closely related, $c(z)$ is a univariate polynomial in $z$ (with coefficients in $GF(2)$), and $C$ is the representation of that polynomial using words of size $W$ (in bits). So if we have $c(z) = z^7 + z^3 + z + 1$ and $W = 8$, we would have $C = (C[0]) = (10001011)$. $C$ gives us an unambiguous way of representing $c(z)$.

  So for the "Add $u_k(z)$ to $C\{j\}$" step... I assume that means to add by doing XOR? What if $u_k(z)$ and $C\{j\}$ are of different sizes? Do we pad both of them with 0's on the right or left side?

I believe the addition algorithm is specified earlier in that section but yes, if you are representing univariate polynomials as described above then you can XOR the values to get the result of addition (since XOR is addition in $GF(2)$). If you follow the convention that the coefficient of the highest degree term in the polynomial is the MSB in the last word ($C[n]$), then you don't need to zero pad. If you have less words in one polynomial than the other, you can skip addition (since XOR by all 0 is the identity function) and just take those words as is. As an example, with $W = 4$

$$a(z) = z^7 + z^3 + z  + 1$$
$$b(z) = z^3 + z^2$$
$$c(z) = a(z) + b(z) = z^7 + 2z^3 + z^2 + z + 1 = z^7 + z^2 + z + 1$$
$$A = (1000, 1011)$$
$$B = (1100)$$
$$C = (1000 (\oplus 0000), 1011 \oplus 1100) = (1000, 0111)$$

  So let's say $W$ equals 8...The concern I have is... let's say $C\{j\}$ is 0. At that point the result would be $x^{16}+x7$, which is bigger than $W$ and I'd kinda expect it to less than W.

Why must the result be less than $W$ (bits)? If $W = 8$ then clearly we need more than one $W$ bit word to represent a polynomial with degree 113. There's no reason we can't have intermediate values that are also greater than one word. Again, see my answer above as to how represent a polynomial with multiple words.

  In the last step it says "Return($C[t−1],...,C[1],C[0]$)". What is $t$ supposed to be? It's not defined or referenced anywhere else. Maybe it's supposed to be the length of C?

Remember that $C$ represents a polynomial with degree up to 224. But we are reducing by $f(z)$ which is of degree 113, so we don't need all the words of $C$. In the introduction to Section 2.3 "Binary field arithmetic" it states "Let $t = \mathrm{ceiling}(\frac{m}{W})$", hence $t$ is the maximum number of words need to represent an element $\bmod{f(z)}$ where $m$ is the degree of $f(z)$.


Can I Modified AES for enhaced security of WPA-2? I have topic for my research paper is modified AES algorithm for enhaced security of WPA-2 , it posible ? what i should learn ?

thanks

No.

AES isn't a weak point of WPA2. Modifying it would almost certainly weaken it, outside trivial stuff like adding more rounds or other things consistent with the Rijndael cipher it standardizes. And even these mods can introduce insecurity if things like hardware acceleration can no longer be used and it ceases to be constant time.

More simply both AES and WPA2 are fixed, published standards. AES is used in WPA2, modified AES isn't. Once you modify AES it's no longer AES. Once you modify WPA2 it's no longer WPA2.


LED (AES like) algorithm Decryption-Mixcolumn I want to program decryption algorithm for the LED cipher.
The lightweight block cipher LED(Jian Guo, Thomas Peyrin, Axel Poschmann, Matt Robshaw:CHES 2011).
All the things is routine except the MixColumn component which is like the MixColumn of AES but with a different matrix.
 In fact we have 64 bit of plain text in structure of a state[4][4].
In the MixColumn component each column of the state multiplies with the matrix M  and the result will be replaced with the old column(in the encryption process)

I wanna to have decryption so I need ReverseMixcolumn function.For that i need the inverted matrix M which I have no idea about calculating it.
I know nothing about calculating matrix inverse in the field of operation.
Even I dont know what is the field of operation in algorithm hence it is not pronounced in paper(eprint.iacr.org/2012/600.pdf)

This is code of MixColumn component:

const unsigned char MixColMatrix[4][4] =
{
    { 4,  1, 2, 2 },
    { 8,  6, 5, 6 },
    { 11,14,10, 9 },
    { 2,  2,15,11 },
};
void MixColumn(unsigned char state[4][4])
{
    int i, j, k;
    unsigned char tmp[4];
    for (j = 0; j < 4; j++) //j=0 soton 0
    {
        for (i = 0; i < 4; i++)
        {
            unsigned char sum = 0;
            for (k = 0; k < 4; k++)
                sum ^= FieldMult(MixColMatrix[i][k], state[k][j]);
            tmp[i] = sum;
        }
        for (i = 0; i < 4; i++) //taaghir sotoon
            state[i][j] = tmp[i];
    }
}

The inverse of LED MDS matrix is :

$$\left[
\begin{array}{c c c c}
12 & 12 & 13 & 4 \\
3 & 8 & 4 & 5\\
7 & 6 & 2 & 14\\
13 & 9 & 9 & 13\\
\end{array}\right]$$

you can verify it.

this is sage code that generates the inverse MDS matrix.

f=x^4+x^1+1  # irrudiciable polynomial
L.<z>= GF(2^4,modulus=f)
R=PolynomialRing(L,'x')
N=16
m=[(4,  1, 2, 2),(8,  6, 5, 6),(11,14,10, 9),(2,  2,15,11)]
T= matrix(m)
#print S.inverse()
print m
print T
P=matrix(L,4,4)
P_1=matrix(L,4,4)
for i in range(0,4):
    for j in range(0,4):
        P[i,j]= (T[i][j]) + z^1*(T[i][j]>>1) + z^2*(T[i][j]>>2) + z^3*(T[i][j]>>3)

print P
P_1=P.inverse()
print P_1
# print the matrix with clear distance
for i in range(0,4):
    for j in range(0,4):
        print P_1[i,j]
    print ""


How is the generator used in Feldman's Verifiable Secret Sharing scheme determined? According to the Wikipedia description of Feldman's VSS scheme

  First, a cyclic group G of prime order p, along with a generator g of G, is chosen publicly as a system parameter. (Typically, one takes a subgroup of (Zq)*, where q is a prime such that p divides q-1.)

Why is it necessary to use a generator g in this process?
What is the procedure to be followed to implement a method which produces this generator for a given prime order group Zp?

The multiplicative group $\mathbf{Z}_p^*$ of non-zero integers modulo $p$ is cyclic of order $p-1$, so it has exactly one subgroup of order $k$ for each divisor $k$ of $p-1$.To obtain an element $g$ of $G$, take any element $a$ of $\mathbf{Z}_p^*$ and let $g = a^{(p-1)/q} \bmod p$. Then $g$ is an element of $G$ because
$$g^q = \left(a^{(p-1)/q}\right)^q = a^{p-1} = 1 \pmod p.$$

The order of $g$ is a divisor of the order of $G$, so it is a divisor of $q$, and since $q$ is prime, it equals either $1$ or $q$.


Is it a good practice to use plain text for derivation of Keys? I have a question regarding the derivation of keys in crypto.
Is it a good practice to use the plain text (in form of hashes) for derivation of keys ? these keys will be used for encryption of the same plain text later on.

What are possible drawbacks of the same if any ?

Thank You in advance.

Edit 1: For example

I have a plain text say X

The hash, H = Random Text + X;

Key, K1 = Initial Key XOR H;

Cipher C = Enc (K1, X)

So it is a good practice to use the plain text as shown in above manner for key generation and encryption ?
what are the drawbacks of the same.

Edit 2
The other party will receive

Cipher C along with C1 = Enc(K0, Hash)

So that in order to decipher, apply Dec(K0, C1) = Hash

K1 = Hash XOR K0

and then PT = Dec(K1, C)

Thank You.

The hash can only be calculated once you know the plaintext (and, in your case, the Random Text as well). If you already know the plaintext there is no need to know the key anymore.

So basically you have a scheme here that either offers no security at all, or a scheme that is impossible to decipher, even for the intended users (apart from guessing the plaintext).

In your update you show that you now wrap and unwrap the hash. That would make this scheme feasible, but it would still leak information. If you have identical plaintext then you will also have identical ciphertext, unles you change Random Text each time. You also haven't specified an IV.

If you have a random number generator already then it is much easier to calculate $K_d = KDF(K_{master}, Salt)$ and then $C = E(K_d, P)$. Or you could just use a random IV and (authenticated) encryption.

There is a strong feeling that you've deviced your own protocol because you are unfamiliar with common techniques. That's never a good idea.