Enabling Oblivious Access Control via Function Encryption Abstract

With Functional Encryption, would access control between two parties be possible without revealing the entirety of one party's policy to the other? E.g. such that a server would be incapable of discerning anything more about a client's policy (aside from weather the client's requested action is permissible via single Boolean output), and vice versa for the client when checking that the server is first allowed to receive the action request before transmitting it.

Problem Statement

A distributed set on nodes (subjects) within a computation graph communicate peer-to-peer (P2P), exchanging messages, services, etc (objects) via an common API. Subjects exchange identities to authenticate each other with some common source of trust, e.g. a Certificate Authority (CA), thereafter establishing a forward secured channel, e.g. via Transport Layer Security (TLS). Through this channel, the two participants should conduct a form of trust negotiation with respect to validating the other participant is authorized to receive or request a given object respectively.

Ideally, in the interest of preventing any information about the computation graph from being leaked, one may wish that policy definitions be obfuscated from the public. For a large dynamic P2P systems, it is perhaps best participants store only their own provisioned policy, as opposed to all policies for whom they are expected to interact with. To be fully decentralized as well, no connection to a third party broker at run time for access arbitration should be used.

Given these requirements, middle ware standards such as DDS Security from OMG fallow a familiar pattern above where participants exchange signed permission documents that prescribe the policy to enforce upon the owner. In essence, a participant's entire hand of cards is revealed to all recipients. To introspect the topology of the inner data bus and its resources, a malicious actor needs only to annex a single identity in order to connect and aggregate policy documents.

  I was thinking this relates to Oblivious Transfer (OT), but instead where the verifier gets exactly one policy decision result without without knowing anything about the rest of the policy that was not pertinent to the inquiry.

Related

What are the current limitations (and capabilities) of Functional Encryption used for access control?
What paradigm does ABE, KP-ABE and CP-ABE fall into
Certificate based Access Control for Pub Sub messaging

Side Note & Motivation

I'd like to create a Mandatory Access Control (MAC) plug in for robotic and Industrial IoT (IIoT) middle wares. I've written one before that leverages regular expressions in clear text extensions within a subject's identity certificate. OMG's DDS Security default plugin does this better by decoupling identity and permission documents for handshaking. However, I think we could do even better than its v1.0 plugin by not sharing entire participant policies. Of course one could just provision the permission document into multiple minimalistic documents for each use niche use case, but my thoughts were that perhaps functional encryption could help avoid such quantized bookkeeping.

Potential Solution?

Using Functional encryption, a trusted authority with a master secret key ($msk$) and public key ($pk$) would generate a "functional decryption" key ($sk$) from a participant's policy ($k$). Each participants would be provided the $pk$ and relative $sk$, where $sk$ is bound to the participant's public identity via a signed document.

For a client and server session between two participants, the client would first use $pk$ to encrypt its own intended API request ($x$) to generate the ciphertext ($c$). After securely connecting and receiving the server signed document, the client would verify the server's ownership of $sk$. Next the client would check the server is authorized to receive the API by using the server's $sk$ to calculate a policy function of the request $c$ encrypts. If the function returns True, then the server is authorized to receive the API request, otherwise False is returned. If True, the client then transmits $x$ and its own $sk$ document for the server to verify similarly, checking the client is authorized to send the API request before fulfillment.

Extension?

To prevent recipients of a participant's $sk$ from probing what additional API permissions where provisioned within, e.g. by brute force enumeration of API requests, perhaps either the encryption or decryption algorithms could altered require a third argument ($sk'$). While also generated from $k$, $sk'$ is instead kept secret to the owner, while additionally remaining a non-substitutable argument for (public) $sk$ and vice versa. The result being that a return of True could only occur if the policies in $sk$ and $sk'$ coincide such that the permissions for the intended client and server for the API request $x$ are all permissible, otherwise False is returned.

This would prevent a malicious actor from gaining any more knowledge about the permissions of other participant's, aside from what could already be inferred from authorized exchanges using the identity and $sk'$ from the participant it has already compromised. Perhaps a another approach could necessitate some sub key or token from the other participant that would authorize the policy "background" check upon the received $sk$ for only the permission relevant for the API in question. However this would require the client to divulge the API request to the server to receive such a token before even vetting the server, itself a circumvention of access control that would perhaps negate the advanage.

In lieu of three argument function encryption algorithms unfeasible, perhaps a similar effect could be achieved by necessitating a cascaded calculating of function upon $c$ and then $c'$ using $sk$ and $sk'$ once in either of the two stages? E.g.

$$
(pk,msk) \leftarrow Setup(1^{\lambda}) \\
sk \leftarrow Keygen(msk, k) \\
{sk}' \leftarrow Keygen(msk, {k}') \\
c \leftarrow Enc(pk,x) \\
{c}' \leftarrow Dec({sk}',c) \\
F(({k}',k),x) \leftarrow Dec({sk}',{c}')
$$


In storing passwords in a database should I use a per-application salt in addition to a per-secret salt? Assuming that the salts are sufficiently long (16 random chars) is there any advantage in using a per-application salt in addition to a per-secret salt when storing hashed passwords in a database?

The per-application salt would held in the code.  The per-secret salt would be held in plain text on the same database entry as the hashed password.

There is an advantage.

Cracking a password from its hash without knowing the salt is extremely difficult, as you're essentially increasing the password length by the length of the salt.

If you're storing the hash in such a way that it isn't obvious that it's been salted by the application, the attacker likely won't go looking for it. If the application itself isn't plain text (ie; compiled in some way), even if they do go searching for it, it is non-trivial to find.


How are secure hashing and encryption algorithms proven? Given that:

  You should always use proven secure hashing and encryption algorithms,
  rather than attempting to write your own.

What's the process for criteria for an algorithm being proven?

Is it necessarily a peer review process? Does an algorithm need to withstand exploit attempts for N amount of time by M many experts?

Or, is there a mathematical proving process that security experts can apply on their own to evaluate an algorithm?

From the consumer perspective, how can early algorithm adopters vet new potential algorithms? Or put another way: When should security-concerned folks start considering new algorithm X?

My personal opinion: "proven secure" is more of an advertising slogan than anything else. The one-time pad and certain multiparty protocols can be shown to have some kind of information-theoretic security; these are exceptions to the rule. "Don't roll your own crypto" is still sensible advice however.

For the rest of this discussion, I'll try and stick to facts.

In public-key cryptography, there are three kinds of number-theoretical primitives in common use (RSA groups, prime-order groups based on finite fields F_p, prime-order groups based on elliptic curves) for which the security properties and arguments are based on a combination of experience and heuristics. For example, RSA has been around for 35-odd years now without anyone finding a way to break it when used properly; a lot of effort has gone into factoring integers but the best number-field sieving algorithms available today are still nowhere close to factoring 4096-bit RSA moduli. Similar considerations apply to taking discrete logarithms in finite fields.

What "provable security" does is construct a layer of cryptographic components on top of these primitives and prove that a certain formal definition of breaking the components is at least as hard as breaking a certain formal notion of security on one of the primitives. For example, one can prove that if you obtain my ElGamal public key and you give me any two messages of the same length, and I give you an ElGamal encryption of one of them back, then you cannot do any better than guess at random which of your two messages I encrypted --- unless you can also solve one of cryptography's basic hard problems over the group I'm using to do my ElGamal encryption, which has been studied since around the 1980s. (This is formally called the IND-CPA to DDH reduction for ElGamal and is a staple of public-key cryptography 101 courses.)

Does this mean that ElGamal is secure for a particular application? It depends, and it says nothing about "out of band" attacks such as malware on your computer, biased randomness generators etc.

I see the role of security proofs primarily as a layer of security within the cryptographic research community. Proposals for new primitives are rare, and need a jot of justification to be accepted. However, let's say you have a particular application where you want, for example, an encryption scheme for messages where you want anyone to be able to tell just from looking at a ciphertext if the plaintext is all zeroes or not, but nothing else. A cryptographer might be able to design such a scheme for you based on existing primitives or schemes, and then prove that breaking the new scheme with the additional feature is in some way at least as hard as breaking one of the existing and well understood schemes. For example, one could adapt ElGamal and prove that if you can tell an encryption of 01 from an encryption of 10 or 11, then you can also break ElGamal directly.

Within this specific context --- proving a scheme to satisfy some formal notion under the assumption that the primitives already satisfy some formal notion --- the word "proof" in cryptography means the same as it does in mathematics. Cryptographic proofs typically do not address the following points:

Does the primitive in question really satisfy the property?
Is the formal notion of security sufficient for a particular real-world application?
Is the proof correct? The amount of proof-reading done before a paper gets into CRYPTO is much less than for most mathematical journals; mistakes do happen.

To give another example: block cipher modes of operation. The security proof for (say) Galois-Counter Mode (GCM) is that if you had a perfect block cipher B then B-GCM (with random initialisation vectors and a few other things) would give you  authenticated encryption. In contrast, ECB mode has no such security proof (and fairly obviously does NOT provide much security even with a perfect block cipher). AES is not a perfect block cipher, but a pretty good one judging by experience. But we can still say that AES-GCM is a much better choice than AES-ECB.

The original quote, in my opinion, would read better as:

"Cryptographers should not (usually) design new schemes for the sake of adding features without proving them to be at least as secure as existing ones. Everyone else should stick to standardised algorithms."


Where to store sensitive keys in a device? I am working on some security features that should be executed by the firmware of a consumer device whose communication to a server must be secure.

Any exchange of data is based on symmetric cryptography, with keys created by "Elliptic Curve Diffie Hellman Key Agreement".

For reasons of cost, a dedicated hardware security module (HSM) was omitted. Instead, all cryptographic algorithms are executed within the board firmware, additionally supported by powerful hardware accelerators directly on the MCU to handle AES and ECC.

All RAM and used flash memory is internal to the MCU.
JTAG interface is disabled.
No external memory is used.
Beside of executing directly within the firmware, all cryptographic algorithms are state of the art.

The open question is, where to store sensitive keys:

Is it acceptable from a security point of view, to keep private and symmetric keys in the MCU's flash memory, since there is no way to penetrate from outside, except perhaps the monitoring of power consumption as a side channel attack? To be more secure, all these keys are additionally encrypted by a unique device key, to be created upon factory startup. However, I feel, because this device key is also kept solely within internal flash that this gives only very little additional security.

What considerations should be considered to verify whether such an approach will fulfill standard security requirements or not? What would be the right way without using a dedicated HSM?

If it can be stored, it can be recovered.

Consider the unsettling fact that even if you were able to select a hard-to-discover location, since you are using a consumer device, at any point in the supply chain (HDL design, whoever makes your microcontrollers, etc) someone could have compromised the device long before you get to designing the firmware. You are wise to observe the likely-negligible extra security obtained.

As others have mentioned, reactivating JTAG or UART ports is not that big of a deal, and I can just crack open your device and dump out the flash memory anyway. Understanding firmware is easier than ever. You should assume your adversary has access to IDA Pro, understands firmware emulation, and is willing to drop some cash on an EEPROM or flash reader. (This is what I do, anyway.) Being clever may slow an adversary down but it can provide no guarantees.

Even HSMs are not necessarily secure. It's turtles all the way down.


How to choose between AES-CCM and AES-GCM for storage volume encryption We are using the encryption built into Solaris 11 ZFS, which offers the choice between CCM (CBC counter mode) and GCM (Galois counter mode). What are the pros and cons of choosing each of these cipher modes?

TL;DR if you're reading this in 2020, applications should be using GCM mode.

CCM (Counter with CBC-MAC)

Message authentication (via CBC-MAC) is done on the plaintext not the ciphertext.  (This is generally not a desireable feature.)

On the encrypt operation, the encryption and MAC could happen in parallel, but generally do not (typically because there is just one AES engine in a chip, just one AES thread at a time, etc.).  Similar statement is true for decrypt.

Performance costs essentially 2 x AES operations per block
Cannot be parallelized
CCM ciphers are available in OpenSSL as of TLS 1.3 (2018), but disabled by default.

GCM (Galois Counter Mode)

GCM ciphers are the most widely used block ciphers worldwide. Mandatory as of TLS 1.2 (2008) and used by default by most clients.
Message authentication (via GMAC/GHASH) is done on the ciphertext.  (This is desirable most of the time.)  Note that in most implementations, the auth check and decryption happen in parallel for performance reasons.
Performance costs 1 x AES operation and 1 x GHASH per block (GHASH generally faster than AES, so GCM is faster)
Encrypt/decrypt of multiple blocks can be parallelized nicely

GCM should be considered superior to CCM for most applications that require authenticated encryption.  Because of the authentication that happens, GCM is not susceptible to the bit flipping and other attacks that can be mounted against counter mode or other stream modes.

There are some nuances that should be noted before using GCM that involve maximum size of the encrypted message and the MAC size.  These are called out in the standard (NIST SP800-38D).


Why OpenSSH prefers ECDSA nistp256 keys over -384 and -521, and those over Ed25519, for host key verification? According to ssh_config(5), HostKeyAlgorithms “specifies the host key algorithms that the client wants to use in order of preference ... The default for this is:
ecdsa-sha2-nistp256-cert-v01@openssh.com,
ecdsa-sha2-nistp384-cert-v01@openssh.com,
ecdsa-sha2-nistp521-cert-v01@openssh.com,
ssh-ed25519-cert-v01@openssh.com,
rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,
ssh-rsa-cert-v01@openssh.com,
ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,
ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa

This lists ECDSA keys before Ed25519 key, and also prefers ECDSA keys with curves nistp256 over nistp384 and that over nistp521.
I was under impression that Ed25519 is generally superior to ECDSA keys, and that keys with higher n curves, at least of these three, are more secure.
So why OpenSSH lists the algorithms in this order?
Also, I'm developing an Android application that uses SSH as a transport. It also needs a list of preferred host key algorithms. Would it be a good idea to replicate OpenSSH's list in the app? Or should I prefer ed25519 over ecdsa with nistp521 over -384 over -256 over rsa keys?

If I remember correctly, it is simply an issue of performance. Remember, HostKeyAlgorithms determines the method used to authenticate the server to the client, it does not generate session keys.
The ECDSA algorithm is faster than RSA, and small key sizes are faster than large key sizes, when the default was changed in 5.7, the changelog specially referenced performance reasons, See the first feature item.
NIST keys are probably preferred over ED25519 for compatibility reasons, I have had to generate NIST keys after Curve25519 based keys after finding the server did not support them, so that makes total sense. Curve25519 based keys are probably more secure, unless you are asking NIST, then they say the are equally secure.
Since these are just default options, you are of course free to change them or force a specific algorithm, I have forced 3072-bit RSA for my default host key method. Remember, this is a selection option, if a key type on the list does not exist, it will not be used. If you only have RSA keys in your configuration, all the EC options will be skipped, you can delete them at will.
If you are using SSH for transport and you have control over the app and server, you can just generate the 1 host key you want and be done with it, and ignore the configuration options, since they will not matter.


Why is diffie-hellman-group1-sha1 used instead of diffie-hellman? For SSH why is Diffie-Hellman-group1-sha1 used instead of just Diffie-Hellman? In other words, why is the hash function used?

This has been specified by the standard, steps 4 and 5 of the protocol described in RFC 4253:

  S generates a random number y (0 < y < q) and computes
    f = g^y mod p.  S receives e.  It computes K = e^y mod p,
    H = hash(V_C || V_S || I_C || I_S || K_S || e || f || K)
    (these elements are encoded according to their types; see below),
    and signature s on H with its private host key.  S sends
    (K_S || f || s) to C.  The signing operation may involve a
    second hashing operation.
  C verifies that K_S really is the host key for S (e.g., using
    certificates or a local database).  C is also allowed to accept
    the key without verification; however, doing so will render the
    protocol insecure against active attacks (but may be desirable for
    practical reasons in the short term in many environments).  C then
    computes K = f^x mod p, H = hash(V_C || V_S || I_C || I_S || K_S
    || e || f || K), and verifies the signature s on H.

  This value (H) is called the exchange hash, and it is used to
  authenticate the key exchange.  The exchange hash SHOULD be kept
  secret.

  The signature algorithm MUST be applied over H, not the original
  data.  Most signature algorithms include hashing and additional
  padding (e.g., "ssh-dss" specifies SHA-1 hashing).  In that case, the
  data is first hashed with HASH to compute H, and H is then hashed
  with SHA-1 as part of the signing operation.

It then goes to define diffie-hellman-group1-sha1, just to show that SHA-1 is indeed the hash mentioned above:

  The "diffie-hellman-group1-sha1" method specifies the Diffie-Hellman
     key exchange with SHA-1 as HASH, and Oakley Group 2 [RFC2409] (1024-
     bit MODP Group).  This method MUST be supported for interoperability
     as all of the known implementations currently support it.  Note that
     this method is named using the phrase "group1", even though it
     specifies the use of Oakley Group 2.

So basically it is a hash over the parameters used for the key exchange. Without it the parameters may be changed by an attacker (the "active attacks" in the description) and the exchange would not be authenticated.


One Time Pad Alphabet Size I am building a simple one time pad system using a low-power microcontroller to XOR a stored key with an input string, and vice versa. Due to several internal factors, it's very preferable for the system to use only the 95 "printable ascii" chars instead of full 256-values bytes to represent pad keys. Since the input is restricted to simple plain-ascii as well, that should be enough coverage if I understand the OTP process correctly.

My pad-making question is about converting random 0-255 values to plain-ascii chars, representing 0-94 or so. Would it be more secure to convert each 0-255 value (x) using:

x % 95 (x mod 95) to get all the possible chars, but with the 65-94 values being 50% more likely than 0-64 values.
int(x / 3), to get a uniform distro of keys chars from 0-84 value, where each value has odds of 3/255 (~1/85) of being used.

While #1 has 10 more key possibilities, #2 has uniform distribution, and I can input from an 85 "letter" alphabet if needed (instead of 95).

Given a random 0-255 input, which down-conversion likely results in better security?

edit: fixed the unclear range "0-85" and "0-95" to reflect 85 and 95 possibilities.

Your input alphabet is 95 chars, within the 128 character 7-bit ASCII space. You need the ciphertext to specifically be within the 95 char input alphabet. I assume the microcontroller byte size is 8-bits, and I hope you have 32-bit registers.

The best solution would be to use a 6-bit output alphabet (64 entries) and use an intermediate conversion between the input and OTP to perform XOR. You will of course run into a space penalty as your input is not within the 6-bit encoded space, but it will make up for it with the performance of the algorithm, which is quite quick.

The OTP can be stored as 8-bit per char raw data to save space and read in 6-bit intervals (24 bits = 3 bytes or 4 6-bit chars), or stored as 6-bits per byte. If you stored the OTP as encoded ASCII, it will need to be converted back into a 6-bit stream representing the index of the characters in the alphabet. If you store as 8-bit, you do not have to perform the intermediate conversion before XOR on the OTP, which you will need to do if it is stored as 6-bit.

The plaintext will be converted into a 6-bit stream either from its byte data (8 bits of data, read 6 at a time) or from an encoded 7-bit representation of the first 128 ASCII chars (7 bits read 6 at a time). If the microcontroller has 32-bit registers, you can pack 4 7-bit characters or 5 6-bit characters. 16-bit registers get you 2 7-bit or 6-bit characters. Now you can XOR with the OTP, and you can use several performance-space tradeoffs. You can read the OTP into the full register space (32-bits OTP for 28 or 30 bits of plaintext, 16-bits OTP for 14 or 12 bits of plaintext) and truncate after XOR. Or you can read the exact amount of bits from the OTP as required, which requires additional shift operations but uses less pad data.

After XOR, pack the result 12 or 24 bits at a time, and encode to a 6-bit printable alphabet. I have a high performance alphabet that allows me to use integer operations to encode instead of table lookups like Base64, if your processor is slow at lookups the integer method can be several times faster.

Treating the 7-bit input alphabet as 8-bit entries before encoding is faster, but you loose 1 bit per character of OTP and output space, this may be useful if storage and bandwith is plentiful but you want lower computation or code size. Using 6-8 and 8-6 for input, output, and OTP data means less code, and more simple algorithms:

Input = 7-bit printable ASCII
Inter1 = 8-bit (0 || input char)
Inter2 = 24-bit packed integer (3 x Inter1)
OTP = 6 or 8-bit data
InterOTP = 24-bit packed integer (24 bits of OTP)

XOR integers, encode resultant 24-bits to 4 6-bit characters (65% efficient)

  24-bits of OTP, 32-bits of ciphertext used for 21 bits of plaintext

If you want better efficiency, the input is treated at 7 bits instead of 8. You can read full bytes of OTP if you do not need efficiency of pad storage:

Input = 7-bit printable ASCII
Inter2 = 28-bit packed integer (4 x input char)
OTP = 8-bit data
InterOTP = 28-bit packed integer (32 or 28 bits of OTP)

XOR integers, encode resultant 28-bits to 5 6-bit characters (70% efficient), or treat 3 28-bit blocks as 14 6-bit chars (maximum 75% efficient)

  28-bits of OTP, 40-bits of ciphertext used for 28 bits of plaintext or
  32-bits of OTP, 40-bits of ciphertext used for 28 bits of plaintext or
  84-bits of OTP, 112-bits of ciphertext used for 84 bits of plaintext or
  88-bits of OTP, 112-bits of ciphertext used for 84 bits of plaintext

There are more space efficient methods, but the computation cost is astronomically high, and unsuitable for a microcontroller. You can pack 9 characters of 95-char alphabet into a 64-bit MMX register using extended precision FP math, encrypt with 64-bits of pad, and encode back into 10 chars using some VERY ugly and cycle hungry math, but it works and is 90% efficient, well beyond the max 6-bit encoding efficiency of binary data (75%).


Product of Negligible and Non-Negligible Functions I know that the product of two negligible functions will always be negligible, but I'm wondering if it's possible for the product of two non-negligible functions to be a negligible function?

I'm wondering if it's possible for the product of two non-negligible functions to be a negligible function?

Yes, actually; here is an example:
Consider the two functions:
$$P(x) = 1 \text{ if x is an even integer}, 0 \text{ otherwise}$$
$$Q(x) = 1 \text{ if x is an odd integer}, 0 \text{ otherwise}$$
Both $P$ and $Q$ are nonnegligible functions.
However $P(x)Q(x) = 0$, which is (trivially) a negligible function.


Can we calculate the "previous hash value" in the SHA256 compression function with a known message block and final hash? Suppose we have a $512$-bit (or $512\times n$ bit) message that we'd like to hash using SHA-256. I've looked at the implementation, and from what I understand, after padding, there will be a total of $2$ (or $n+1$) message "blocks" that are fed into the function, with the last block being completely padding. The last message block in this scenario is completely known, it should begin with the "1" bit that marks the beginning of the padding, followed by a bunch of zeros, followed by the message size in bits.
So now, let's say we hash the message. If we follow the chain, the first "hash value" is known, it's the $H_0$ of SHA-256 which is the following (from wikipedia):
h0 = 0x6a09e667   h1 = 0xbb67ae85   h2 = 0x3c6ef372   h3 = 0xa54ff53a
h4 = 0x510e527f   h5 = 0x9b05688c   h6 = 0x1f83d9ab   h7 = 0x5be0cd19

But for every subsequent execution of the compression function, the values above will be changed. My question is, since we know the final message block, can we compute the intermediate hash right before the last hash $H_n$ using just the final message block (which is fully known), and the output final hash $H_{n+1}$?

Can we compute the intermediate hash $H_n$ using just the fully known final message block, and the final hash output $H_{n+1}$?

No, that's computationally infeasible. The only known way to find $H_n$ is when we know all (or enough of) the message, which allows to directly compute $H_n$ in the forward direction (or use brute force search of a small unknown fraction of the message, validating a guess by checking if the final $H_{n+1}$ matches).
The reason we can not compute $H_n$ is that the Davies-Meyer round function $(H_n,M_n)\mapsto H_{n+1}$ restricted to fixed known $M_n$ is computationally difficult to invert.
That follows from its construction as $H_{n+1}\gets E(\text{key}\gets M_n, \text{block}\gets H_n)\boxplus H_n$ where $E$ is a public block cipher and $\boxplus$ is a group operation¹ on $\{0,1\}^{256}$ (256-bit bitstrings).
If some fairy told us the output $X$ of $E(\text{key}\gets M_n, \text{block}\gets H_n)$, and since we know $M_n$ and $H_{n+1}$, we could find $H_n$ in two ways:

by using the decryption function $D$ matching $E$, with $H_n\gets D(\text{key}\gets M_n, \text{block}\gets X)$
by inverting $X\boxplus H_n\mapsto H_{n+1}$ to find $H_n$ from the known $H_{n+1}$ and the $X$ given by the fairy.

But we have no fairy, and there is no known way out of this chicken-and-egg problem. That's even provable under a model of $E$ as an ideal cipher. That's by design of the Davies-Meyer round function.
Also: it is likely that for a sizable fraction of the final hash $H_{n+1}$ and message size (equivalently, values of $M_n$ ), the known relation $H_{n+1}=E(\text{key}\gets M_n, \text{block}\gets H_n)\boxplus H_n$ leaves several possible values for $H_n$.

¹ $\boxplus$ happens to be addition of 256-bit bitstrings ignoring carry bit between blocks of 32 bits.


How does the order of Q affect the time it takes to solve ECDLP? I use Sagemath's built-in function discrete_log() to solve ECDLP and according to the documentation it uses Pohling-Hellman algorithm to solve an ECDLP.

This is the case for my EC:

P-order => 176648753626148987385153422443570230330
Q-order() => 2

The P-order has these prime factors: 2 * 3 * 5 * 5888291787538299579505114081452341011

Even though the highest prime factor is super-large, the ECDLP through discrete_log() is solved within a second.

I Read about the Pohling-hellman attack and it only mentions that P should have small prime-factors in order for the attack to be successful. It never mentions the order of Q.

How does the order of Q affect the time it takes for the attack to be successful?

Here is what I believe Sagemath is doing:

Given the problem of finding $x$ s.t. $xP = Q$, one step is computing $x' = x \bmod 5888291787538299579505114081452341011$; it does this by computing $P' = (2\cdot 3 \cdot 5)P$, and $Q' = (2 \cdot 3 \cdot 5)Q$, and trying to solve $x'P' = Q'$
As the order of $P'$ is circa $2^{122}$, we would normally expect this computation to take circa $2^{61}$ time (quite a while).  However, in this case, $Q'$ is the neutral element.  I suspect that Sagemath notices this, and so immediately concludes that $x' = 0$
Every other computation involved in Pohlig-Hellman is relatively quick, and so it reports the answer ($3 \cdot 5 \cdot 5888291787538299579505114081452341011$) quickly.

The summary is: if your implementation special cases this $Q' = 0$ case, then we can skip any prime that does not appear in the order of $Q$; the time taken by Polhig-Hellman is dominated by the largest prime that appears both in the order of $P$ and the order of $Q$.


Commutative homomorphic encryption for zero-knowledge transfers I am trying to design a scheme that would allow the following:

Alice has a number $a$ which she wants to keep secret
Bob has a number $b$ which he wants to keep secret
Alice can "transfer" a number to Bob such that whatever she transfers must be subtracted from her number (the sum of their numbers must remain the same)
Victor is an independent observer and must be able to validate that the sum of the numbers does not change without learning any of the numbers

For example, suppose Alice's number is $10$ and Bob's number is $5$. If Alice transfers $2$ to Bob, his number will become $7$ and her number will become $8$. Victor, observing the transfer, should be sure that the total sum didn't change but he shouldn't be able to learn any of the numbers involved. Alice shouldn't be able to learn Bob's starting or ending number, and Bob shouldn't be able to learn Alice's starting or ending number.

I am thinking this is possible to implement using a deterministic encryption that is both commutative and homomorphic (additive). For example:

Alice would use her public key to encrypt her number $a_1 = E(a, pub_a)$ and would share it with Victor
Bob would do the same $b_1 = E(b, pub_b)$
If Alice wanted to transfer $x$ to Bob, she would compute $a_2 = E(a-x, pub_a)$, $x_a = E(x, pub_a)$, $x_b = E(x, pub_b)$. She would then share $a_2$, $x_a$, and $x_b$ with Bob and Victor
Bob would decrypt $x = D(x_b, priv_b)$, and then use it to compute $b_2 = E(b + x, pub_b)$. He would then share $b_2$ with Victor

Using this info, Victor would be able to verify that Alice's number was updated properly, because $a_1 = a_2 * x_a$. He would also know that Bob's number was updated properly because $b_2 = b_1 * x_b$. And finally, he would know that $x_a$ and $x_b$ encode the same number because $E(x_a, pub_b) = E(x_b, pub_a)$.

Deterministic encryption should not compromise security because the numbers themselves can be randomly "padded". For example, the numbers could be 128-bit integers where lower 64 bits are randomized. So, essentially, instead of sending $2$, Alice could be sending something like $2.00034094035343043$.

It seems to me that El Gamal could work to implement something like this, but I'm not sure if there is anything better. Also, there are some concerns for El Gamal:

Homomorphism for regular El Gamal is multiplicative, not additive
Ciphertext and public key size may be quite big - and I'm trying to make them as small as possible

Your protocol won't work if the encryption scheme is randomized. In fact, the commutative property would be that $D(D(x,priv_a),priv_b)=D(D(x,priv_b),priv_a)$, which is different than $E(E(x,pub_a),pub_b)=E(E(x,pub_b),pub_a)$.

A deterministic encryption scheme cannot be semantically secure. So if a scheme could meet the requirements to be used in this protocol, it wouldn't have the security guarantees you would want from an encryption scheme.

This is not to mention that $*$ could also be non-deterministic.


What are the consequences of a MAC tag collision? I've seen some proofs of MAC security that are based on the extremely-unlikely event that two MAC tags collide (ie, they are equal for distinct messages).  Suppose that this extremely unlikely event occurs, then what?  Can we forge arbitrarily more messages with this same tag?  With ANY tag?  Or even better, do we get the MAC key?

Whether we get any information from a MAC collision rather depends on the details of the MAC.

HMAC is one extreme.  If you happen to find a collision (that is, two distinct messages that happen to MAC to the same value), well, that doesn't tell you very much.  We don't know how to use that to generate any more collisions, or to gain any information on the key.

MACs based on universal hashes (UMAC) are on the other extreme; in these MACs, the message is sent through a universal hash primitive (which takes a key, and has the property that any two distinct messages hash to the same value for only a small number of keys), and then that hash is protected with some cryptographical primitive.  These types of MACs typically take a nonce; two messages with two nonces that hash to the same value is generally harmless; however, if you MAC two messages with the same nonce and they evaluate to the same value, that usually means that the result of the universal hash happened to be the same, and that gives the attacker information about the key used in the universal hash; usually enough for the attacker to generate second preimages for other messages.  Also, with some MACs of this type, sometimes it is not necessary for the two messages to have the same MAC, the fact that the attacker knows the messages and MAC values based on the same nonce may be sufficient.

CMAC and XCBC are similar to the UMAC case (even though a universal hash is not involved); if you find two messages that have the same CMAC value, it is likely that a simple length-extension to the two messages will allow the attacker to create other pairs of messages with the same MAC.  However, this observation gives no information about the CMAC key; whether this is actually useful in practice depends on whether those length-extended messages happen to be something the attacker can use.


passive corruption ?= Byzantine corruption in the UC framework? Notations: We follow the convention in the UC framework. We use $\mathcal{A}$ to denote the adversary, $\mathcal{P}$ to denote a party in the model.

We focus on two types of corruption in the UC framework, which we rephrase now.

Byzantine corruption: $\mathcal{A}$ takes the full control of $\mathcal{P}$.
Passive corruption: $\mathcal{A}$ sees the internal state of $\mathcal{P}$.

My question is:

  Is passive corruption actually equivalent to Byzantine corruption?

Now I explain the reason behind my question.

In the UC framework, $\mathcal{A}$ controls the network, if $\mathcal{A}$ only has the ability to see the internal state of $\mathcal{P}$, $\mathcal{A}$ can do the following to approximate "controlling $\mathcal{P}$" in the real-world model:

$\mathcal{A}$ isolates $\mathcal{P}$ from the network.
$\mathcal{A}$ copies the internal state of $\mathcal{P}$ and launches a virtual machine $\widetilde{\mathcal{P}}$.
$\widetilde{\mathcal{P}}$ has the same internal state as $\mathcal{P}$ at the time of corruption. But, $\mathcal{A}$ takes the full control of $\widetilde{\mathcal{P}}$.
$\widetilde{\mathcal{P}}$ pretends to be $\mathcal{P}$ in the rest of the execution.

Some readers may suspect whether 4 is possible in the UC framework with authenticated channels. Now I explain my concerns.

In the UC framework, it is non-trivial to know who actually sends the message. We need to rely on "authenticated channels". We use $\mathcal{F}_\mathsf{auth}$ to denote the ideal functionality for such a communication channel.

Via $\mathcal{F}_\mathsf{auth}$, parties in the protocol can make sure who sends the message. If $\mathcal{P}$ is Byzantinely corrupted by $\mathcal{A}$, $\mathcal{A}$ can send messages in the name of $\mathcal{P}$.

But, what if $\mathcal{A}$ passively corrupt $\mathcal{P}$?

The definition of $\mathcal{F}_\mathsf{auth}$ allows $\mathcal{A}$ to change the messages sending out from $\mathcal{P}$ if $\mathcal{A}$ corrupts $\mathcal{P}$. It is not clear whether it differs in the case of  passive corruption.
Existing realizations of $\mathcal{F}_\mathsf{auth}$ rely on some secrets in $\mathcal{P}$, such as the signing key. If $\mathcal{A}$ just sees the internal state of $\mathcal{P}$, which includes such secrets, then $\mathcal{A}$ can pretend to be $\mathcal{P}$ in these realizations.

Or in other words, passive corruption does not reduce $\mathcal{A}$'s ability to impersonate $\mathcal{P}$.

Back to my question:

  Is passive corruption actually equivalent to Byzantine corruption?

And a followed-up question.

  How should I model something similar to passive corruption?

Thanks for your reading.

Let me add an example to assist explanation.

Consider that I can passively corrupt the webserver of CVS. I can steal their TLS/SSL certificate private keys in the CVS webserver's internal state.

Then, I make a man-in-the-middle attack to a specific client, and if I also control the network, I can mimic CVS website to this client and display wrong pharmacy records.

Reference:

Canetti's paper on the UC framework. "Universally Composable Security: A New Paradigm for Cryptographic Protocols".
https://eprint.iacr.org/2000/067.pdf
Canetti's paper on realizing $\mathcal{F}_\mathsf{auth}$ using $\mathcal{F}_\mathsf{sig}$. "Universally Composable Signature, Certification, and Authentication". https://eprint.iacr.org/2003/239.pdf
Canetti-Shahaf-Vald's paper on realizing $\mathcal{F}_\mathsf{auth}$ with a global PKI (a bulletin-board certificate authority) also using $\mathcal{F}_\mathsf{sig}$. "Universally Composable Authentication and Key-exchange with
Global PKI". https://eprint.iacr.org/2014/432.pdf
Backes-Pfitzmann-Waidner's paper on realizing $\mathcal{F}_\mathsf{sig}$ with a public-key signing scheme. "A Universally Composable Cryptographic Library". https://eprint.iacr.org/2003/015.pdf

Is passive corruption actually equivalent to Byzantine corruption?

The answer is clearly no, otherwise cryptographers wouldn't spend so much time on developing protocols for active security.

Let me add an example to assist explanation.
Consider that I can passively corrupt the webserver of CVS. I can steal their TLS/SSL certificate private keys in the CVS webserver's internal state.
Then, I make a man-in-the-middle attack to a specific client, and if I also control the network, I can mimic CVS website to this client and display wrong pharmacy records.

The man-in-the-middle attack you specify is an active attack. Yes, in real-life, an attacker that has the internal state of the webserver can get their TLS/SSL private key and then could cause all sort of trouble. But, the whole point of the passive model is that we assume that the attacker does not do this. The only thing they do is record plaintext messages/internal state of the parties they have corrupted.
Why do we make this assumption? To make our lives easier, of course. We have to start somewhere, so we start with a fairly simple adversary model. It does not assume a completely trusted third party, yet we can still develop secure protocols. That is a win. Whether that win translates into the real world is another question. There have been papers (I'm looking, I'll update when found) that use passively secure protocols and argue that this is okay since, because of the application, there are other mechanisms in place that will force parties to be honest.
So, if you are worried about active attackers you should use protocols that are secure against active attackers. Passively secure protocols will break royally if the adversary is actually active.


What is the time complexity of computing a cryptographic hash function/random oracle? I'm wondering what's the computational complexity of computing a hash function/random oracle when doing complexity analysis. For example, what's the computational complexity of computing $H(b\|r)$? where $b$ is a bit and $r$ is a random string of length of security parameter $\lambda$. If $b$ is a string (i.e., a string message), what's the computational complexity? In my opinion, we can just take it as taking $poly(\lambda)$ time, but can we take it as computing in constant time? say, $O(1)$?

Most hash functions are designed with an initialization stage (with a fixed performance overhead), a compression function and state update function that process the input in blocks (with a fixed per-block performance overhead), and a finalization stage (with a fixed performance overhead).

Typically that means you can consider initialization and finalization as a single constant when evaluating computational complexity of a hash function, and the per-block compression and state update can likewise be considered as a single constant.

You could approximate this as $\mathcal{O}(c+xn)$, where $n$ is the number of blocks required to fit the input (accounting for padding), $x$ is the constant for per-block overhead, and $c$ is the constant for initialization and finalization.

For longer messages of arbitrary length, it would typically be simplified as just $\mathcal{O}(n)$ where $n$ is the length.

In many cases, this complexity is insignificant compared to other elements of a larger algorithm involving hashes, and might therefore not even be counted in the complexity analysis.

Also, when input sizes are fixed you may simply assume a constant value, which essentially means rounding to $\mathcal{O}(1)$.

In the case of variable width outputs (technically not a hash, but still the same family of symmetric functions) like SHA3 SHAKE256, a XOF (extensible output function), the computational complexity is approximately equivalent to combining a hash with a stream cipher. In this case, you have $n_1$ for the input size and $n_2$ for the output size, and the complexity would approximately be $\mathcal{O}(c+x n_1+y n_2)$ where $x$ is the overhead per input block and $y$ is the overhead for the bit stream output per output block. This may be simplified as $\mathcal{O}(n_1+n_2)$.

Again, when both sizes are fixed (such as if you use the XOF for a fixed purpose in a protocol, like hashing a key to produce a bitmask for a digital signature function, like in some RSA implementations), it can be approximated as $\mathcal{O}(1)$.


Message types in GPG I am trying to check the part where messages are both encrypted and signed. But what is the difference between a message which looks like this

-----BEGIN PGP MESSAGE-----
Version: GnuPG v2

hQEMA40Tbs69jxZxAQf/QfWUH8waN2CFAbn4bWlORERoaL7Zpm95WeDPcwJDObMt
E7hW+ERITJ0gakacppZuVlbHTPT4DuMpDsT1tZzk1ZfO638Jias5WyVeF9g8E3tG
m6cvuyeSp4mD8WuKao2v52HvOecXctMGETaSg58upf6co1DG0XJ0oDGyuEXmc2MN
t+uRtHHxht53sLwLEpVZlrS2L/910DU7PzDwFDuEY4aKlWUz1Q2mdg6XIyJHOoW2
ySNF3AuoOc6VmZ4T3EY2ewjrZoIbX1aLfVFKuoM27RpOohnnIOYP4mtr8JPfq3Ej
M1IWL28hCXzZX3wgqvYEjh8wiXlDEij4Xm5riT2J5NLA1QGbVFkOxVwK7qvqMT3o
USAecl1GdJ6Bx31csQ7eOpv+gJ6/9BgnnXR6TyWjgA4fXnQNJzl5LguVy/4W+IoE
ezXmCDo0VbhgeX5RlytqX9c5+kTXp5dvfAocMqFb0GzYphvno2yqe4CiU7GTKib3
a2E6VHENKgTd3GHoqDs8N57hxsejzURhlcmBneSNvMIqdFJuynNos50Ri61PU+O4
QmX6xSCy4VnT8y4C3CLbts9JWSkFZVSTmeI/hkzWqmk08HguQTRTTOyTNtVX36yk
9c77Gd9MHi3YMOEqcQw4ze+EqnNIP+h+CKrV8gW4SUQK9amVKyX7vM+ValJ2LQBh
Z9ebwL89Vt6S26EQ6uv9E8Xo+lZQANBCVN9pI4r8ZcCg3EFnx0kJ6p+BQ88ePaJ0
jXn97ogMqxxaJlQZo91R/i47x14UlWdgOYE87MoqRcCYi//DI3pY8os35e1lj9Eg
V+cooRU46Bqwtff7jVyXxMUhRuQq8ZE//vL3LPj+GochhINFvvE9yAlQS9nOZ18V
TbVwRSqeiA==
=/i6B
-----END PGP MESSAGE-----

And the other type which looks like this

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

ba2c254d75426db8e8ac6cb59020a82633731ad9
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQEcBAEBCAAGBQJduy+HAAoJEEo3afbgQ4/jZ38H/1K1wOnHz6za0NdkzwfKCPV+
XXT0Nr4/qsD1FH7r8Pb1WBxWacq34YG2Y73x+c9kA62FWggLxm2J2EwLxE/UITxJ
DOxwLUXPNKN9/iSJcbH450x6SkMEia//yoZRAgC3iVfXyLFmJw/odkmEgdZRTAEG
4wqFENkb2D1QHGh9Eq/iBRdwpUlXIvc+6rKX81RSvGEmgCMd4HpWFGOIdP0yfJRe
rbolxhxpdVzY5eUj/DwGoivJKZliXWC/cEWFQdc0J6QhwouaoDe/WCbpI7RqjsJb
sYcmFrYYyn1X7s6llgX7mBeTqemsBV1CJsFt1pIxrxQscJbm3KfwugzLIclNj/c=
=vpbL
-----END PGP SIGNATURE-----

Should we decrypt and check both the above types in the same way? It looks like both are decrypted same way and both the above can be signed and encrypted. What is the difference?

These are different messages. The first is encrypted, and inside that there might be more information, but

$ gpg -vvv one.asc
gpg: using character set `utf-8'
gpg: armor: BEGIN PGP MESSAGE
Version: GnuPG v2
:pubkey enc packet: version 3, algo 1, keyid 8D136ECEBD8F1671
        data: [2047 bits]
gpg: armor header:
gpg: public key is BD8F1671
:encrypted data packet:
        length: 405
        mdc_method: 2
gpg: encrypted with RSA key, ID BD8F1671
gpg: decryption failed: No secret key

The second is a signed message, not encrypted. The message that is signed is in plain text

ba2c254d75426db8e8ac6cb59020a82633731ad9

and the signature is in the PGP SIGNATURE part


Nonlinearity of a Boolean function with odd number of input bits Highly nonlinear functions are used in combination generators and other stream ciphers.
We know that maximum nonlinearity (hamming distance to all affine functions) of $f$ is achieved when $f$ is bent function. This will be
$$NL=2^{n-1}-2^{(n/2)-1}$$ when $n$ is even. Also when $n$ is odd, this bound is not satisfied. What will it be?
The question is: Can we find $f$ with largest nonlinearity for an arbitrary odd integer $n$ case?

This is a famous open problem in coding theory, the covering radius of the first order Reed-Muller code, when the number of variables is odd.
As far as I know the best general upper bound on nonlinearity which in this paper is denoted N (=covering radius R) for $n=2k+1$ is still the one below:


How to provide secure password based encryption with password reset option I am trying to build website that will encrypt some data for the user using his/her the output of scrypt on it, now the idea is that this schema is not flexible because if the user loose their password then all of their data is lost, instead came to following options:
Option 1 :

Generate random 128 bit key $k_1$

Generate random 128 bit recovery key $k_2$

Run scrypt on user password to get $k_3$

Give $k_2$ to user to save it in secure place and not save it in database

Encrypt $k_1$ once with $k_2$ and once with $k_3$ and once with $k_2$ and store them in database

When user forget their password he/she uses $k_2$ to decrypt the encryption key $k_1$ and then go to step 2.

Option 2:

Generate random 128 bit key $k_1$

Generate random 128 bit recovery key $k_2$

Use scrypt on user password to derive $k_3$

$k_4 = k_1 \oplus k_2$

$k_5 = k_1 \oplus k_3$

To encrypt we use the $k_1 = k_4 \oplus k_5$

Give $k_2$ to user to save it in secure place and not store it in database

When a user forgets their password he/she provides the system with $k_2$, then $k_1 = k_3 \oplus k_2$, go to step 2

Option 3:

Use scrypt on user given password, this will be $k_1$

Generate random 128 bit key for encryption $k_2$

Encrypt $k_2$ with $k_1$

Use Shamir shared secret with number of shares is $2$ and threshold is $2$ and the secret is $k_1$

Store share in database $s_1$, and give the other $s_2$ to the user to save it in secure place.

When a user forgets their password she/he will provide the system with his/her sahmir shared $s_2$, and using shamir secret sharing algorithm and the $s_1$ we obtain $k_1$ and then go to step 1.

Now my exact question is: What is the pro and cons for option 1, option 2 and option 3? Which one will be the most secure one? And which one will be the best from a performance perspective?

In every of these options the essential step is to save it in secure place. Instead of implementing any of these options, just tell the user to keep the password in the same secure place that you have in mind for the 2nd key. All major risks will be the same as for keeping there the 2nd key, but this solution will cost you nothing - no implementation, no costs.
To answer your question precisely: What is the pro ...? I don't see any "pro", because they are not more secure than keeping the original password at the same secure place. To "cons": additional complexity to implement such process and to maintain it without getting any more security.
In case of option 3 additional complexity (also without additional security) comes from the fact that 2 of 2 keys are needed. This is effectively the same as "simple" splitting of the key into 2 parts without using any complex method.


When do ECC patents end? As the topic says, since when can ECC cryptography be freely used?

Is it not widely used because of patents? There is no alternative to it on embedded devices and smart cards.

Just to mention: I am not from the USA. I'm a simple user who wants ECC to be wide supported.

Let me preface this by saying that I am not a lawyer and if you are planning on using ECC in a system you sell, you should hire a lawyer.

There are a number of ECC related patents. However "in all of these cases, it is the implementation technique that is patented, not the prime or representation, and there are alternative, compatible implementation techniques that are not covered by the patents" (src). That said, the patents last 20 years, the implementation techniques that are patented might be freely usable (I say might because I believe there are other legal mechanisms to protect IP) 20 years after the patent was applied for. A very quick survey showed that many of the patents on the Wikipedia page were applied for in the late 80's to late 90's. Thus, by 2020 the currently existing patents should expire.

ECC can presumably be used without infringing on the patents. So, the patents themselves are not necessarily inhibiting widespread use. There are some who would argue that the real reason ECC isn't widely used is due to it's age and the fact that RSA came first. Age lends credibility (the longer it has been around w/o a break the more the community trusts it).


LoRaWAN 1.0.2 Session Key Security I am reading about LoRaWAN 1.0.2 specification. For the confidentiality and integrity of the comunication the protocol generate two session keys, the NwkSKey and the AppSKey (part 6.2.5 of the specification, page 35).

Both, application and network session keys are derived like following, the only difference is the first component (0x01 and 0x02):

AppSKey = aes128_ecb_encrypt(AppKey, 0x02 | AppNonce | NetID |DevNonce | pad_16 )

0x02 is a costant of 8 bit.
AppNonce is a nonce generated by network server of 24 bit.
NetID is network identifier of 24 bit and not change if the join procedure is related on the same network.
DevNonce is a nonce generated by end-device of 16 bit.
The pad_16 function appends zero octets so that the length of the data is a multiple of 16.

I'm not sure of the robustness of this key derivation. Is the variable part inside the block being encrypted not just 40 bits? Furthermore, if you use the same AppSKey for a long period, even 3/4 years, is the solution still robust?

Furthermore, the DevNonce is sent from the end-device in the join request message and the message is not encrypted.

aes128_ecb_encrypt (the AES block cipher in the forward direction) is a pseudorandom permutation family: if the adversary doesn't know the key, then knowing the output corresponding to some inputs doesn't help to find the output corresponding to some other input. In other words, the only way to find AppSKey for a given AppKey is to convince someone who knows AppKey to calculate and publish the value of AppSKey for that exact input (same AppNonce, same NetID and DevNonce).

Therefore the potential problems with the protocol are:

Can users who share an AppKey be convinced to repeat both AppNonce and DevNonce within the same NetID?
Can this use of AppKey result in calling the AES permutation with the same inputs as other uses of AppKey?

1. Nonce repetition

Nonce repetition needs to be done on both sides. AppNonce is a 24-bit value, so if it's chosen at random, it'll likely repeat at least once within a little over $2^{12} \approx 4000$ attempts (birthday paradox). DevNonce is a 16-bit value which is supposed to be random, so it'll likely repeat at least once within a little over $2^8 = 256$ attempts (§6.2.4). But since the two nonces are chosen by different devices, the probability that one nonce repeats is independent from the probability of the other nonce repeating. If AppNonce is genuinely random then to get a good chance of repeating you need about $2^{20} \approx 1,000,000$ attempts. At 11kbit/s, which is the nominal maximum bandwidth, you could go through this in a day, if the device's battery is up to it.

If the nonces are repeated, they'll end up using the same AppSKey. AppSKey is used for unauthenticated encryption with CCM*. Unauthenticated CCM* is CTR with a choice of initial counter value that ensures that counter values won't repeat if the CCM* IV doesn't repeat. So in order to get a block to repeat, you need to arrange not only for the key to repeat, but also the IV. Since the IV is calculated in a simple way from constant device characteristics and the frame count (§4.3.3), each session uses the same IV sequence. So if two sessions use the same AppSKey, then the corresponding messages in these sessions will be encrypted with the same mask. This reveals the xor of each pair of corresponding messages.

Uses of AppKey

In addition to the derivation of AppSKey, AppKey is also used to calculate integrity values (MIC) for join messages (§6.2.4) and join-accept messages (§6.2.5), to derive NwkSKey (§6.2.5), and to encrypt join-accept messages (§6.2.5).

NwkSKey is derived in the same way as AppSKey except with the prefix 0x01 instead of 0x02.
MIC are CMAC calculations. CMAC uses AES in the encryption direction, with inputs that are the result of xor-ing successive input blocks with an intermediate result that's an AES output. The intermediate result is not published.
The join-accept message is calculated by decrypting a block of data.

I don't see an obvious way to get the inputs to collide, but this would require extensive analysis.


Multiplication-homomorphic schemes I'm looking into multiplication-homomorphic schemes now and basically I see that there are 3 options: RSA, Boneh-Goh-Nissim and ElGamal.

RSA was proved to be insecure unless message is randomly padded, which action breaks the homomorphic property of the scheme.

Boneh-Goh-Nissim allows for one multiplication, but the decryption process is done through Pollard's lambda algorithm, which is basically guessing, i.e., there's no upper boundary on decryption time - looks dodgy for serious use.

ElGamal is great but the message expansion ratio is just crazy. If we use a 1024 bit key (512 was already broken), a 4 byte integer blows up to 256 bytes when encrypted. 64 times is harsh if we intend to encrypt GBs of plaintext data. Haven't yet tested the performance myself, but I guess that would suffer a lot too.

So the question is - are there other options I might take a look at?

Well, there seem to be some restrictions you have:

numbers are 32 bit integers
(several) GB of total data
expansion factor matters

Well, standard ElGamal is probably already close to the best you can get. Maybe ElGamal over elliptic curves would work, which have shorter representations at similar security levels (but then the operations on points are homomorphic, and the function from integers to points will most likely not preserve this property). But in general, it's not going to be any better: Trapdoor functions need this kind of size for each element. And if the original element is just 32 bit, there is this kind of expansion.


How long does it take to decrypt an RSA/ECB encrypted message? I am working on assignment where I have specific scenarios and I am little bit struggling with this one.

Alice sends and email to Bob.For this e-mail, she uses the following method of encryption: each single word of the text is viewed as an integer number in binary, obtained by concatenating the 8-bit binary values of the ASCII code of each letter. The number thus obtained for each word is then encrypted using the RSA algorithm and the resulting list of numbers is sent. Words that are too long to fit into this scheme are split into syllables, and each syllable is treated as a word.

I need to discuss whether eve can find efficient method to decrypt messages. My answer is:

I know if the plain text has two or more blocks of plaintext in common then we get same result for each of these blocks.  This is the bit of information that leaks even if this does not give immediate information what the original plain text might be, Eve can see the relationship between plaintext and cipher text.

Eve can also measure how much power /time it takes to decrypt cipher text. Eve can observe this power and time consumption and she might be able to get some information about how many “1” there are in d. If Eve manages to determine d she can decrypt entire cipher text as c^d mod n =m.

I also need to provide rough estimation about the time it would take to decrypt the message and this is the part I am struggling with.  The estimates of the time could be of the type: a few seconds, a few minutes, 1 hour, a few hours, one day, one week or longer. You may make assumptions about the speed of her computer: for example you could assume it would take 1 millisecond to perform RSA to encrypt or to decrypt one integer (of any size commonly used in RSA), if the encryption, respectively decryption key is given.

Any suggestions?

This is basically a substitution cipher where words are converted to numbers and then those numbers are substituted for new numbers as the encryption step.  You'd need to assume the language of plaintext, let's assume it's English.

Every time the word "the" occurs in the original text, it will cause the same number to be output to replace it.  Using some word frequency tables, it may be possible to find patterns that occur in the cyphertext that represent common patterns in English usage.

I guess I would have to look and see if there is a technical definition for decrypt, but even if you managed to puzzle out a possible sentence by analyzing the cyphertext, does that count as a decryption if you cannot reproduce your assumed input generating the same output.

Despite this being a very bad way to use RSA, it would still not make it any easier to officially decrypt the message.  The only way to do this with absolute certainty, is to factor the primes that make up the private key.  Depending on the size of the primes involved, this is a pretty intractable problem...

As the commentor above notes... if a word won't fit into the modulus, then keysize might be pretty small.  The longest word in English is something like 28 letters, so 28*8 is 224 bits.  There is no way that antidisestablishmentarianism was what the question had in mind, so lets make an assumption that any word longer than 8 characters is one that would need to be broken up...  That would be a modulus of 64 bits.  So now, the question is, how long would it take to factor a 64 bit number.  On modern computers, one assumes that could be handled in minutes.  ( https://stackoverflow.com/questions/4244319/how-to-find-all-the-prime-factors-in-a-unsigned-long-long-integer )


What is the importance of adding round key in AES I know this may not be the place to ask this but I have found it difficult to find an answer to this question. I know the steps of the AES encryption algorithm but I am finding it difficult to understand the concept stage by stage.

How would by not adding the round key at each stage increase the vulnerability in AES encryption?

The round key is derived from the key and adding it is what makes the algorithm a block cipher (AKA: a keyed permutation) rather than just a permutation.

In the image below you can see a typical block cipher. If the round key were not added in any round then the block cipher output would not depend on the key at all and it would be an unkeyed permutation.

as far as adding the round key each round rather than just at the start and end that's a design choice which improves security. xor-encrypt-xor can be used to easily tweak a block cipher and the basic principle of xor-permute-xor can be used with a strong pseudo-random permutation to construct a block cipher. AES, if round keys were added only at the first and last round, would look something like that.

The key schedule and the round keys added each round are a design choice which positions a lot of messy and difficult operations in such a way that they only have to be computed once for every key. When encrypting a lot of data with a single key, key setup is done once. When brute forcing a key, key setup must be done for every key tried. This translates over to cryptanalysis too.

image credit:Permutation-based encryption, authentication and authenticated encryption


Any scenario for using ElGamal-SIGNATURE over RSA? On a homework assignment, we're asked to give an example in which scenario one would use an ElGamal-Signature over an RSA-Signature.
I found this question, but the answer also only describes why RSA is superior. I searched a while now, but I don't really find any reason why one would use a Schoolbook-ElGamal (not DSA or elliptic curves) instead of RSA.

Does anyone have an additional idea?

ElGamal signature works as follows.  Define a large prime $p = 2qs + 1$ where $q$ is a prime.  Let $g$ be an element of order $q$ and a hash function $H\colon \{0,1\}^* \to \mathbb{Z}_q$. The public key is $y = g^x \bmod p$ and the private key is $x \in \mathbb{Z}_q$. The signature of a message $m$ is given by a pair $(r,s)$ where $$r=g^k \bmod p\quad\text{and}\quad s = k^{-1}(H(m) - xr) \bmod q$$
for a random integer $k \in \mathbb{Z}_q$.  The validity of a signature $(r,s)$ on message $m$ is checked by verifying that $r^sy^r \equiv g^{H(m)} \pmod p$.

It is worth to see that the two expensive operations in the signature generation, namely computing $g^k \bmod p$ and $k^{-1} \bmod q$, are independent of the message to be signed.  They can therefore be precomputed.  ElGamal signatures can be preferred when signing should be done very fast, like for example to authenticate a car at a toll bridge.  In this mode (called off-line/on-line),

[off-line phase] several coupons $(r_i, t_i)$, with $r_i = g^{k_i} \bmod p$ and $t_i = k_i^{-1} \bmod q$, for random integers $k_i \in \mathbb{Z}_q$ are pre-computed;
[on-line phase] when a message $m$ has to be signed, the signer takes a fresh coupon $(r_i, t_i)$ and computes the signature as $r = r_i$ and $s = t_i(H(m) - xr_i) \bmod q$.

Notes.

A coupon can only be used once.  Each signature needs a fresh coupon.
In the on-line phase, the cost of an ElGamal signature is only a couple of multiplications modulo $q$ (which is much faster than a full modular exponentiation in the case of RSA).


How to hash similar strings to the same hash value? Suppose that $s_1$ and $s_2$ are two stings that have a small hamming distance. Is there a preimage resistant "hash" function ($H$) that can map them to the same value i.e., $H(s_1) = H(s_2)$?

As pointed out by poncho, a hash function $H(.)$ that would consistently map two close strings $s_1$ and $s_2$ to the same value, would have to map all the strings to the same value. (Since you could go from one string to the next and it would always have to map to the same value.) So this does not make any sense.

I think, like you also suggest, that an error correction code might be what you want. Such a code is defined by a set of codewords $\{c_1,...,c_n\}$ that are at a certain (Hamming) distance from each other, and around each codeword $c_i$ there is a Hamming sphere $S_i$ that contains those words that are closer to $c_i$ than to any other codeword. A perfect decoder will map any word to the closest codeword, so that it will map any word in $S_i$ to $c_i$. So if you have two words in the same Hamming sphere $S_i$, your decoder will decode them to the same codeword $c_i$. (You can easily generate such words by taking $c_i$ and randomly flipping a number of bits.)

This is not exactly the hash function you wanted, but I think this is as good as it gets if you want to map two words at a small Hamming distance from each other to the same value.


Vulnerabilities of encrypting data with known regularities I need to encrypt data that has a pre-defined header and footer structure, and furthermore the data follows pre-defined patterns. The header and footer structure follow a defined structure but cannot be left out because they are never truly equal. An example of this kind of data is an html file: it will in most cases start with a doctype declaration (which has a pre-defined form) and html opening tag. The file ends with the html closing tag, and even though the data in between tags can be arbitrary, the tags are fixed structures as well. This is like a known-plaintext attack.

Suppose an attacker were to do a brute-force attack, then he could easily verify that a key is wrong after decrypting only a few bytes. My question is: is this a vulnerability? I presume that when the key size is large enough, it is not, but consider the case for a small enough key where the amount of work required could make a significant difference. Ideally, it should only be possible to check whether the decrypted data is correct after all data has been decrypted. (I assume that it requires much more work to process large amounts of data, similar to PBKDF using many iterations to make trying many words infeasable; is this correct?) Could the information that plaintext must follow a pattern be of any use to an attacker?

If it is a vulnerability, how would one resolve the issue? In other words, is it possible to encrypt data with many regularities in such a way that these regularities only become apparent after decrypting all the data?

My question applies to encryption algorithms in general, but I intend to use AES with a 256-bit key.

Typically the cost of brute force so greatly out weighs the cost of decrypting a single block, that the fact that an adversary can check for proper decryption after decrypting a single block is not a serious concern. Otherwise protocols like SSL would not be secure.

That said, as you point out, this relates to the key space. If the key space is too small, then decrypting the first block with every possible key would be feasible for an adversary. If you could make it necessary to decrypt every block in order to get the plaintext, that would slow down an adversary. But, with the speeds we see in encryption algorithms, you'd have to encrypt terrabytes for this to matter. For example, the throughput of AES running on a GPU was shown to be around 35,000 Mbps. That number will only continue to rise. The point is to use a cipher that supports a large enough key space and choose keys randomly from the entire space.

If you still feel this is a problem though, why not do the following $E^{ofb}_{k_1}(E^{cbc}_{k_2}(P)||k_2)$ where $||$ is concatenation and $P=p_1\cdots p_n$ (i.e., a number of blocks of plaintext). The use of OFB on the outside ensures that the entire ciphertext must be decrypted to get the last block ($k_2$), which is then used to get $P$.


Can I construct a zero-knowledge proof that I solved a Project Euler problem? Is there a practical method, and if so what is the method, to reveal that I have the following type of answer but conceal the answer itself? The answer is, let's say, the solution to a Project Euler problem.

That is all. However, I'm new here. I'll try to explain why I hope this question will be considered appropriate. The explanation is a bit lengthy, maybe too defensive!

The question concerns implementing a specific information security system. To make that clear, I'll pose a birthday problem and the information to conceal will be the answer to that problem. Project Euler doesn't have any birthday problems, but it's not really so different from typical Project Euler problems. The Project Euler organizers believe that preventing widespread publication of their answers is vital to the goal of their project. Many Project Euler participants, including me, believe that it's valuable to convince people that we have solved the problems that we claim we have. (OK, I suppose we can also refer people to the Project Euler leaderboard, but how does anyone know that that is me?)

The specific problem is, what's the least number of people we must plan to select in order to have at least 95% confidence that five of our selected people will have their birthdate (day of the year) in common? Let the problem presuppose the usual sorts of silly assumptions: that birthdates are uniformly distributed throughout the year, no one is ever born on February 29, the world's population is effectively infinite, and we can do perfect random sampling from the world's population. The answer is just some number, possibly a big one.

Now, once I compute the number, can I publish information that proves that I have it without revealing its identity? I realize that there's no asymmetric computation involved. It's OK that others who know my birthday problem can solve it just as I did. It's not OK if others can get the answer from my information without even knowing my birthday problem. Crucially, I'm not sure what to say about people who do know my birthday problem but want to cheat by deriving the answer from my information instead of solving the birthday problem for themselves.

Verifiable to someone who already has the correct answer

Verifiable to whom?  Someone else with the correct answer?  Then you may be able to get away with a salted bcrypt hash; e.g., you can easily say make a cryptographically strong one-way hash of an answer:

>>> import bcrypt #using py-bcrypt python module
>>> hashed_answer = bcrypt.hashpw('[secret answer to problem 283]', bcrypt.gensalt(log_rounds=16))
$2a$16$fPitqoBxyVJbxGsWCecweu2Wfrz8KhgnargfA9F//c0ZJ6E4ONwHK
# the above hash was generated using the actual answer to problem 283

Then if you have the answer you can check that I also have the answer with:

>>> hashed_answer == bcrypt.hashpw('[secret answer to problem 283]', hashed_answer)
True

You could also use an online javascript bcrypt calculator, where you type the answer as the password, use my hash as the salt $2a$16$fPitqoBxyVJbxGsWCecweu2Wfrz8KhgnargfA9F//c0ZJ6E4ONwHK, and then press run and check that the hash with your answer equals my hash.

You should make sure that the answer isn't brute-forceable by using a suitably strong number of rounds.  (In this case where the answer is a base-10 number between 16-20 digits long and it takes my cpu about 4 seconds to generate a hash to brute force the answer would take a single cpu about a billion years to brute-force).

Granted people who don't have the answer to 283 cannot verify that you have an answer.

Also without solving your five person birthday problem; by the pigeonhole principle its known that the answer is less than (365)*4+1 ~ 1461; so you must use a very strong hash or add more information; e.g., one that takes days to calculate to make bruteforcing impractical.

Verifiable to someone who does not know the answer

Now if you want to have someone who doesn't know the answer check that you know an answer, you'll have to appeal to a trusted authority.  This could be projecteuler.net where a list of users who have solved any individual problem is available.  Users could authenticate their answer is correct with project euler (either via checking a hashed answer or directly submitting the plaintext answer to the server) and then project euler could let the world know.

As for identifying that minopret on project euler to their real life identity, project euler could decide to do this in a variety of ways.  One scheme would have people type in an email address to a form and then you see the problems that that user has solved (you don't want to just list email addresses to mitigate potential spam).  So if you were applying to a job and wanted to demonstrate your project euler problem solving skills, you tell your employer the email you use on PE and they could check that you have control of your email address and then see the number of answers you have done correctly.

Aside: I solved your 5-birthday problem (was at work so couldn't solve earlier).  As its a small integer, it probably wouldn't be that difficult to brute force even with an unreasonably large hash, so I would suggest requiring a less brute-forceable answer.  Something like first find the least number of people (N) where the probablity of having at least one set of 5 (or more) people with the same birthday is greater than 0.95 and then give the sum of that number + the probability rounded to six decimal digits.  For example, if this was the standard birthday problem (two people with the same birthday to more than 0.95) the answer would be 47 + 0.954774 = 47.954774.  Then my bcrypt hashed answer to the at least 5 birthday problem at greater than 95% confidence would be '$2a$20$ejlHCtR/G.19k9TCTPtsOOkZm8J9kbvwm6zrcJ0q9NNwcun1eOpoS' (with an ~ minute long hash), which you could check with:

'$2a$20$ejlHCtR/G.19k9TCTPtsOOkZm8J9kbvwm6zrcJ0q9NNwcun1eOpoS'==bcrypt.hashpw('____.95____', '$2a$20$ejlHCtR/G.19k9TCTPtsOOkZm8J9kbvwm6zrcJ0q9NNwcun1eOpoS')

where you replace '____.95____' with the actual number (no leading zeros/spaces).


Why does the PAKE ideal functionallity allow the keys to be the same when the passwords differ? My intuition for the security a symmetric PAKE is supposed to provide comes from the example of a login page. Both the user and the server know the password (assuming unhashed passwords), and the purpose of the protocol is to authenticate both the user and the server to each other using this fact, while simultaneously generating a session key known only to them and avoiding any man-in-the-middle attacks. Specifically, I thought that one of the key properties of a PAKE is that the user and the server would get different keys if they provide different passwords, so a malicious party attempting to log in would be thwarted if it does not know the password. However, this does not seem to be the case according to the security definition.
The standard UC functionality for symmetric PAKE comes from Canetti et al.

Notice (top bullet under the $\textsf{NewKey}$ query) that if one of the parties is corrupted then the adversary gets to choose the session key $sk$, regardless of whether the two parties provided the same password. By using two queries to $\textsf{NewKey}$, the adversary can set both parties' session keys to be the same. Why would the definition be chosen to allow this? If the passwords differ, the functionality could instead have been written to give the adversary the power to choose only the compromised party's key, and not the honest party's key.

The paper contains text that explains why this is OK. I quote:

The main idea behind the FKE functionality is as follows: If both participating parties are not corrupted, then they receive the same uniformly-distributed session key, and the adversary learns nothing about the key except that it was generated. However, if one of the parties is corrupted, then the adversary is given the power to fully determine the session key. The rationale for this is that the aim of key exchange is to enable honest parties to generate a key that is unknown to an external adversary. If one of the participating parties is corrupted, then the adversary will learn the generated key (because it is one of the participants), and so the security requirement is meaningless. In such a case, there is nothing lost by allowing the adversary to determine the key.

However, from your question, I think I understand what you are worried about. If the adversary $P_k$ can set the value of its key with $P_i$ and with $P_j$ then it could seemingly behave like a man-in-the-middle between $P_i$ and $P_j$. However, this is not the case. Specifically, $P_i$ knows that its key with $P_k$ is $sk$, and when communicating with this key, it knows that the communication is with $P_k$ and not with $P_j$ (and vice versa). When $P_i$ wants to communicate with $P_j$, it has a different session key.
Bottom line, the reason that this doesn't matter is that the identity of the other party is given together with the key.
One more note: it may not be absolutely necessary to allow this, but there's no reason to disallow it. Disallowing it may rule out protocols that are perfectly fine. Therefore, it's better to allow it if there's no reason not to.


Why does EdDSA require a b-bit private key instead of b/2-bit? By design, EdDSA requires a $b$-bit string as the secret key $k$, and when signing, it is expanded to a $2b$-bit string $H(k)$, some bit-twiddling is done, and the first half is used as the private key in the signature. [1]

The curve will have a $b$-bit security level, and solving discrete log can be done in $b \over 2$.

Why is it that EdDSA requires a $b$-bit secret key instead of only $b \over 2$-bit which seems like it would provide the same level of security as the curve itself?

One possible reason (and probably the one that was behind that design choice) is to avoid multi-target attacks.

Consider a setup where there are $k$ public/private key pairs, and the attacker's goal is to find one of these private keys. The attacker does not care which private key is obtained; getting any of them is a "win". For instance, the attacker wants to make a fake X.509 certificate by recovering the private key of a certificate authority: any private key in a chain to any root CA in the set of trusted root CA will do. A brute force attack on the $b$-bit seed will succeed with average cost $2^b/k$ (the attacker computes the public key for each potential $b$-bit seed, then looks up the public key in the set of targets; the looking-up does not involve complicated maths and can be done in "negligible" time, compared to the computation of the public key). If $b = 128$ and $k$ is large, then this can be substantially less than $2^{128}$.

From an "academic" point of view, this means that 128-bit seeds only provide "64-bit security": if there is a set of $2^{64}$ targets, then the attack succeeds in cost $2^{64}$, while the defenders collectively spent an effort of only $2^{64}$. Bumping seed size up to 256 bits is an easy and inexpensive way to prevent that kind of academic break.


Compute discrete logarithm mod $n=p \times q$ knowing factorisation I read in a document that for a given $n = p\times q$ ($p$, $q$ primes), if you know $p$ and $q$ then you can easily solve the discrete logarithm problem, i.e. for fixed $a,b$, you can find $x$ such that
$$a^x = b \bmod n$$
But I don't see how this can be done... I tried to check if the Chinese reminder theorem could help me, and this reduces to find the discrete logarithm modulo $p$ and modulo $q$, but I still don't see how we can get this new discrete logarithm without bruteforcing (which is still exponential, even if you get a square root improvement over the naive bruteforce).

Thank you!

This is not true in general. Bach showed that given the factorization of $n$, computing the discrete log modulo $n$ requires computing it modulo the factors (also cf. this previous question for more details.). So, if both the factors are large then DLP is still hard.


How long does it take to crack PBKDF2? How much time will it take to crack PBKDF2 while using a 9 character password? I'm not specifying any specific system or platform. If a brute force attack is made using the best ever super computer around how much time will it take to crack it?

PBKDF2 (as defined by RFC 2898) is a function of the form

$$DK = \text{PBKDF2}(\text{PRF}, Password, Salt, c, dkLen)$$

In most practical use cases, the $\text{PRF}$ is $\text{HMAC}$ instantiated with a Merkle-Damgård hash function such as $\text{SHA-1}$. The time to compute $\text{PBKDF2}$ is roughly linear with the iteration parameter $c$, all other things being equal. The output $DK$ has $dkLen$ bytes, and can be thought as a random-like function of $Salt$ dependent on $Password$, or vice versa.

When used to manage passwords, $c$ and $dkLen$ are typically assumed public; $c$ from 1000 to 100000 is common (much more tends to be taxing for normal use). $dkLen$ could be 16 (or other value making it practically impossible that a particular $DK$ is reached by chance). $Salt$ typically depends on the username, and should also include a server-unique value, preferably secret (at least in part). Normally, neither this secret, nor $DK$ values, should be accessible to an attacker. However PBKDF2 is here to act as a second line of defense should this information leak, and therefore the standard assumption when considering an attack using PBKDF2 to protect passwords is that all $(DK,Salt)$ pairs have leaked (as well as $c$ and $dkLen$); again, that itself should be avoided inasmuch as possible (which is not much more than it is possible to prevent an adversary from accessing an unencrypted backup of the system; notice that if an adversary somewhat can pwn the system, that's at least equivalent, and may give more direct ways to get at the passwords).

With these assumptions (and constant $c$), the best known attacks basically try various $DK,Salt,Password$ combinations, computing $\text{PBKDF2}(\text{PRF}, Password, Salt, c, dkLen)$ until that matches $DK$: this will reveal an acceptable password for the username extracted from $Salt$ on the system attacked, which will also be the original password with overwhelming certainty for common $dkLen$ (perhaps allowing to attack that user on other systems where he or she uses the same password, or a similar one). For large $c$, the attack duration is dominated by the evaluation of $\text{PRF}$ at least $c$ times for each $DK,Salt,Password$ tried.

If the passwords are random and equally likely among $N$ (e.g. consist of $n$ symbols each chosen randomly among $m$, leading to $N=m^n$), having many $DK,Salt,Password$ does not help, and an attack is expected to find the password of a given user with odds $p$ after no less (and about) $N\cdot c\cdot p$ evaluation of $\text{PRF}$; that's an expected $N\cdot c/2$ $\text{PRF}$ evaluations. For example, with the iteration count $c$ set to 100000, $m=26$, $n=9$, and $\text{PRF}$ HMAC-SHA1, an attack is expected to require about $2^{60}$ evaluations of the round function of SHA-1. That's about the number of hashes performed every 5 second for the purpose of bitcoin mining by mid 2014 according to that source, or what could be done by a 2000-core general purpose computer in a year of operation. So with the iteration count set to 100000, the expected duration for an attack ranges from little for a resourceful adversary doing the job with ASICs or FPGAs, to somewhat too much for the average guy with a bunch of PCs.

If the passwords are chosen by users, the best attack tries the password from most likely to least likely, for each $DK,Salt,Password$ available. For 8 letters perhaps 1% of users will pick password as the password, and even for 9 letters, with a few hundred users, finding a valid $(username,Password)$ will be trivial for any adversary worth consideration after $DK,Salt,Password$ leaked.

There are better alternatives to PDKDF2; notably scrypt, which requires a parameterizable amount of RAM to perform the calculation, making ASICs and FPGAs much less practical; and can be distributed on multiple cores, allowing a corresponding increase in the iteration count (thus security) in some setups. As pointed in another answer, that's an active research area.


How to solve polynomial modular equation to create a correct decryption algorithm I recently had a variant of the following problem in my cryptography course and I had trouble solving it and was looking to get some help.

Given the symmetric key cryptosystem: $\text{KG, Enc, Dec}$ where $\text{KG}$ is a key generator that produces a random key in the space $Z_n = \{1, 2, 3, \ldots, n-1\}$, $m$ is a message from the space $Z_n$, and $\text{Enc}(K, m)$ is an encryption algorithm which computes ciphertext $c = (5m - 4k + 3) \bmod n$, design a decryption algorithm $\text{Dec}(K, c)$ such that it fulfills decryption correctness.

At first, I just tried solving for $c$ in $c = 5m - 4k + 3$, but realized that it does not account for $\bmod n$. Then it tried the following solution:

$$
\text{let} (d, x, y) = \text{extGCD}(c, n), m = (c\times x+4k-3)/5
$$

Where $\text{extGCD}$ is the Euclidian extended GCD function (essentially finding the modular inverse). That did not work either.

How would one go about solving this problem? What am I missing (so I can look into it further)?

We can write $m$ as

$$m = (c -3 + 4k) \cdot 5^{-1} \pmod n$$

There is a problem here that the 5 may not has an inverse for every $n$. For example, it doesn't have an inverse in $\mathbb{Z}_{10}$.

It has an inverse in $\mathbb{Z}_{n}$ if $\gcd(5,n) =1$.

If it has the inverse one can find it by the Extended Euclidean Algorithm to form the Bézout's identity $5 x + n y = 1$ then take $\bmod n $ to achive the inverse as $5 x = 1 \bmod n$

As pointed by poncho, for finding the inverse of $5$ there is a better method $$(n+1)/5, (2n+1)/5, (3n+1)/5, (4n+1)/5$$ if the inverse exist. To see the inverse exist, one first needs to see that the $\gcd(5,n)=1$.

In the general case, after some threshold, this approach may not be helpful, since testing all $$(n+1)/x, (2n+1)/x, \ldots, ((x-1)n+1)/x$$ will pass the calculation of the Bézout's identity.


Pre-image resistant but not 2nd pre-image resistant? Are there any cryptographic hash functions for which there is a known pre-image attack, or a known second pre-image attack, but not both?

The attack doesn't have to be practical - just anything that beats the security claim of the hash function.

Intuitively, 2nd pre-image attacks would be easier to find than pre-image attacks, but I'm not aware of any examples or that either property implies the other.

I believe there are no known pre-image attacks on the common crop of hash functions in use today, so I'm interested in historic, obsolete and proposed-but-not-adopted hash functions, but not toy hash functions constructed specifically to demonstrate the possibility of such attacks.

A cryptographic hash function $f : \{0,1\}^{*} \to \{0,1\}^n$ has three properties: (1) preimage resistance, (2) second-preimage resistance, and (3) collision resistance. Even further, these properties form a hierarchy where each property implies the one before it, i.e., a collision-resistant function is also second-preimage resistant, and a second-preimage resistant function is also preimage-resistant (with a condition on $f$).

In the case of (3) ⇒ (2), it's not too hard to see why: if an adversary cannot find any colliding message pairs, then they certainly cannot find a colliding message when one of the messages is fixed.

However, (2) ⇒ (1) is substantially trickier. For some intuition, consider a second-preimage resistant hash function $f$ that was not preimage resistant (modeled by being given access to a preimage-finding oracle). Suppose you were given a $m_1$; then you could compute $H(m_1)$ and consult the oracle for the preimage of $H(m_1)$. The oracle would then return a $m_2$ such that $H(m_1) = H(m_2)$.

This is very nearly a second preimage. The only question is if $m_1 \ne m_2$. Intuitively, given that $f$ maps infinitely-many inputs to a finite number of outputs, there "should be" a high probability that $m_1 \ne m_2$. For all real-life hash functions, this is pretty much the case, so a second-preimage resistant hash function should not lack preimage resistance.

However, it is possible to define "pathological" hash functions that have perfect, provable second-preimage resistance but not preimage resistance. The example given in chapter 9 of the Handbook of Applied Cryptography is this:

$$f(x) =
\begin{cases}
 0 || x & \text{if } x \text{ is } n \text{ bits long}\\
 1 || g(x) & \text{otherwise}
\end{cases}$$

where $g(x)$ is a collision-resistant hash function. In this case, for digests beginning with $0$, it's trivial to find a preimage (indeed, it's just the identity function), but such cases are provably second-preimage resistant, as there are no possible second preimages. In other words, this $f$ is bijective across the space of $n$-bit inputs.

To be more precise about when (2) ⇒ (1), Rogaway and Shrimpton have presented a theoretical analysis of the various relations between the three properties listed above in their Cryptographic Hash-Function Basics. Essentially, their analysis treats a hash function as having a finite, fixed-length domain, i.e. $f : \{0,1\}^m \to \{0,1\}^n$, wherein they show

"conventional implications", like the implication (3) ⇒ (2); these are essentially "true" implications in the sense that they are unconditional, and
"provisional implications", like the implication that (2) ⇒ (1); these are conditional in nature, relying on how much $f$ compresses the message space (as the message space gets larger relative to the digest space, the "stronger" the implication in a probabilistic sense).

So, provisional implications are essentially true if a hash function compresses the message space to a sufficient degree. (The "sufficient" example they provide is a hash compressing 256-bit messages to 128 bits.) Hence, second-preimage resistance implies preimage resistance only if the function in question compresses its input sufficiently. For length-preserving, length-extending, or low-compression functions, second-preimage resistance does not necessarily imply preimage resistance (as stated by the authors on page 8 about halfway down the page).

This should be intuitive given the above algorithm for finding second preimages given a preimage oracle. If you are expanding 6-bit inputs to 256 bits, it's actually quite unlikely that a preimage oracle would be able to find a second preimage. This isn't a formal argument, by any means, but it's a nice heuristic one.

Now, back to real life. Given the above algorithm for using a preimage oracle to find second preimages, I would not expect any real-life hash functions to have preimage attacks and not second-preimage attacks, especially since real hash functions typically compress data well.

On the other hand, I'm not personally aware of any historically-used, non-toy cryptographic hash function which has a second-preimage attack but not a preimage attack. Typically, collision resistance is the first thing attacked by cryptanalysts since it is (in a sense) the "hardest" property to satisfy. But if a hash function is found to be broken with regard to collisions, cryptanalysts typically go straight for the heart: preimage attacks. So, I don't know how much luck you'll have trying to find such a hash function.

You can look at the hash function lounge for some historic hash functions; it hasn't been updated since 2008, apparently, but still contains some useful info. I glanced through a few attacks and found mostly collision and preimage attacks, but you may have more luck.


Proving correctness of pseudorandom generator construction given existing pseudorandom generator Say if I have a given pseudorandom generator G which takes a k-bit input and outputs a 3k-bit number.

How should I show that a specific construction using this pseudorandom generator is valid?

For example, if I want a generator which takes a 2k-bit input and output a 3k-bit number. Is the following scheme valid?

1. split the 2k-bit input into two half
2. passes the two half through the given generator G to get two 3k-bit numbers
3. XOR the two numbers to output the final 3k-bit number.

Call your original ($k$-to-$3k$ bit) PRG $G$ and your construction $G'$.

Let $\mathcal{U}_t$ denote the uniform distribution on $\{0,1\}^t$. Then $G'$ is a PRG as long as the distributions $\mathcal{U}_{3k}$ and $G'(\mathcal{U}_{2k})$ are indistinguishable with effort polynomial in $k$; see this reference.

Distribution $G'(\mathcal{U}_{2k})$ is just $G(\mathcal{U}_k) \oplus G(\mathcal{U}_k)$, where the two occurrences of $\mathcal{U}_k$ in the latter expression are independent. By the PRG property of $G$ applied to the first term, the distribution is indistinguishable from $\mathcal{U}_{3k} \oplus G(\mathcal{U}_k)$.

Since $\mathcal{U}_t \oplus \mathcal{D}$ is distributed identically to $\mathcal{U}_t$, for any independent distribution $\mathcal{D}$, we get the desired result.

I find this question a bit odd though. If all you want is a $2k$-to-$3k$ PRG constructed from a $k$-to-$3k$ PRG, then what about the following simpler construction: given $2k$ bits, throw away the first half and run the second half through the $k$-to-$3k$ PRG?


Is a secure deterministic MAC always a PRF? Given a secure MAC scheme $ \Pi=(Gen, Mac, Vrfy) $, wheres $ Gen $ produces uniformly distributed keys, and the algorithm $ Mac $ is deterministic, is $ Mac $ necessarily a pseudorandom function?

I think that it is a PRF: since there is no forger A that can somehow obtain information from the given tags, and thus deduce something about how the $Mac$ function is built (i.e. how a tag is created), I conclude that there's no distinguisher D that can distinguish between a tag and a random string emitted by a random function.

Is my intuition right? If not, I'd like to have some intuition as to why a deterministic MAC can't be a PRF. (An example of such a MAC would be great.) If yes, further intuition would be great as well.

Your intuition is not right. The fact that no forger can obtain new valid message/tag pairs doesn't say anything about the "shape" of the MAC. For instance, if $\Pi$ is a secure MAC, then the MAC obtained by appending a bunch of zeros at the end of the tag is secure as well:

  If a forger $\mathcal{A}$ is able to create a new and valid message/tag pair $(m,t)$ for our modified MAC (the one obtained by appending the zeros to a secure MAC), then $(m,t')$ would be a new and valid message/pair for $\Pi$, where $t = t'||0^n$ (you would need to be more precise with the games being played here, but the idea is that any msg/tag pair for one MAC corresponds to one msg/tag pair for the other)

But of course this is not a pseudorandom function.

I think your intuition is that a secure MAC can not reveal anything about the underlying message, but this is not right. The security of a MAC relies on the hardness of generating new messages/tag pairs, not in the difficulty of learning anything about the underlying message. In fact, a MAC can reveal the whole message! can you imagine how?