Past exam of the computer science course of the University of Oxford / 2015 / Computer security / 1

The Bell-LaPadula model protects information confidentiality by controlling information flow between security levels. Its simple security property says that a subject may read only objects whose classification does not exceed its maximum clearance:Thus a user cleared for confidential material cannot directly read a secret file. A readwrite permission includes reading and must satisfy the same restriction. This is an access control rule about who can learn existing contents; it says nothing by itself about where a cleared subject can subsequently copy them.

The Bell-LaPadula star property restricts information flow using the subject's current level. With the paper's distinction between blind writing and reading, its usual current-level formulation isHere $f_C(s)\le f_S(s)$ also holds. The first row means that reading above the current level is forbidden; the second is the familiar prohibition on writing down. Their conjunction gives the third row. Blind writing upwards is allowed because it need not disclose the higher file's contents to the writer.

For example, a subject operating at secret level cannot copy a secret file into a public file, even though its clearance would permit reading both files. More generally, any simultaneously readable object must be at most as highly classified as any writable object. A subject must not evade the rule by retaining secret information and then lowering its current level: level-changing transitions need their own safe treatment of retained information and open accesses.

First, the Bell-LaPadula model is a information confidentiality policy. It permits a low-level subject to overwrite a more highly classified object by blind writing. That can destroy a high-level file or introduce false data without disclosing its old contents. Thus it does not supply a data integrity policy, and it also does not ensure service availability. Modern multiuser operating systems require protection against modification and resource exhaustion as well as disclosure.

Second, a single hierarchy of classifications cannot express ordinary independent user ownership and selective collaboration. Two users at the same level may still need different permissions on their respective files; conversely, an authorised publication may deliberately release selected information to lower levels. The simple model lacks those owner-specific permissions and controlled release decisions. Adding discretionary access control, categories and explicit declassification mechanisms is substantial additional policy.

For distinct prime numbers $p,q$, compute the Euler totient functionThe RSA cryptosystem private exponent is a modular multiplicative inverse of the public exponent:Use the extended Euclidean algorithm on $3$ and $\phi (n)$. It produces integers $u,v$ with $3u+\phi (n)v=1$, and reducing $u$ modulo $\phi (n)$ gives a suitable positive $d$. Searching through possible exponents is unnecessary.

To see correctness even for a plaintext sharing a factor with $n$, write $3d=1+t\phi (n)$. Modulo $p$, either $m=0$ or Fermat's little theorem gives $m^{3d}=m$; the same holds modulo $q$. The Chinese remainder theorem then gives $c^d=m(\mathrm{mod}n)$. One may alternatively invert $3$ modulo $\mathrm{lcm}(p-1,q-1)$, but inversion modulo $\phi (n)$ is sufficient for this paper.

The essential exponent condition isOtherwise the modular multiplicative inverse defining $d$ does not exist. For large prime numbers greater than three, this is equivalent toIf, for example, $p\equiv 1(\mathrm{mod}3)$, the multiplicative group modulo $p$ has order divisible by three, and cubing is not a bijection; distinct plaintexts can have the same ciphertext. Unique decryption of all messages would then be impossible.

The prime numbers must also be distinct for the displayed totient formula, and selected sufficiently large and independently that integer factorization of $n=pq$ is infeasible. A small factor, equal factors, or an exceptionally small difference between $p$ and $q$ gives an avoidable factorisation weakness. These size and generation conditions address security; the congruence condition addresses invertibility of cubing.

All calculations are in modular arithmetic modulo $n$. Expand the two expressions appearing in the proposed quotient:The first is exactly $m$ times the second. Multiplication by the assumed modular multiplicative inverse therefore givesThe representative in $\{0,\dots ,n-1\}$ is the plaintext. This RSA related-message attack uses a relation between messages to turn two cubic equations into a linear equation; it does not recover the private key or factor $n$ in the invertible case.

For each candidate nonzero offset $k\in \{1,\dots ,2^{16}-1\}$, expansion givesConsequently, if $D_k$ is invertible, the candidate isCompute the modular multiplicative inverse using the extended Euclidean algorithm, then verify both $m_k^3\equiv c_1$ and $(m_k+k{)}^3\equiv c_2(\mathrm{mod}n)$. The RSA cryptosystem cubing map is a bijection, so an accepted candidate cannot be a different plaintext with the same first ciphertext. This costs fewer than $2^{16}$ trials, each involving polynomially many operations in the bit length of $n$.

There is a useful way to handle every denominator exception for a correct nonzero $k$. Compute $g=\gcd (D_k,n)$. If $1<g<n$, this greatest common divisor factors $n$, allowing ordinary RSA cryptosystem decryption. If $g=n$, then $D_k=0(\mathrm{mod}n)$. The permitted prime numbers are $2(\mathrm{mod}3)$ and much larger than $k$, so $k$ is invertible modulo each. The equation $m^2+km+k^2=0$ would make $m/k$ a nontrivial cube root of one, impossible in a group of order coprime to three. Thus $g=n$ cannot occur for the correct nonzero offset under these hypotheses.

If the bound in the question is read as also allowing $k=0$, then $c_1=c_2$ and there is no additional information: the problem reduces to inverting a single ordinary RSA cryptosystem ciphertext. The small-offset attack requires a nonzero difference; that is the natural reading of distinct related messages.

Avoid constructing the huge integers $c^{3^j}$ explicitly. Maintain $a_0=c$ and $a_j=a_{j-1}^3\mathrm{mod}n$, computing $g_j=\gcd (a_j-c,n)$ after each step.

In case (1), the nontrivial greatest common divisor $g_k$ is one of the prime factors $p,q$. Divide $n$ by it, compute $d$ with the extended Euclidean algorithm, and return $c^d\mathrm{mod}n$.

In case (2), $a_k=c(\mathrm{mod}n)$. The preceding value satisfies $a_{k-1}^3=c(\mathrm{mod}n)$. Cubing is a bijection on the residue classes modulo $n$, so there is only one such cube root, namely the original plaintext $m$. ThereforeFor $k=1$, the preceding value is $a_0=c$; a fixed point is its own plaintext. Keeping the previous iterate makes the recovery immediate once the RSA cycling attack succeeds.

Take the positive integer $k$ whose existence is allowed by the question and writeModulo $p$, if $c=0$ then $c^{3^k}=c$ directly. Otherwise Fermat's little theorem applies, since $3^k-1$ is a multiple of $p-1$. Hence $c^{3^k}=c(\mathrm{mod}p)$. The same two-case argument works modulo $q$. By the Chinese remainder theorem,soThis also covers a ciphertext that is not coprime to $n$; applying Euler's theorem without checking that hypothesis would miss this detail. Equivalently, repeated application of a permutation on a finite set eventually returns to the starting point, although the arithmetic argument gives the requested sufficient exponent.

The fact that a nontrivial factor usually appears before a full return does not say that either event appears soon. Each iteration of the RSA cycling attack is inexpensive, but the number of iterations can be enormous. The multiplicative orders governing returns modulo $p$ and $q$ need not be small, and writing down a large return exponent does not provide a fast way to search the preceding iterations.

If this procedure factored arbitrary well-generated RSA cryptosystem moduli in feasible time with substantial success, it would solve the associated integer factorization problem efficiently. If it instead rapidly returned the predecessor of a ciphertext without factoring, it would solve the RSA inversion problem. Both are intended to be infeasible for appropriate parameters. Efficient integer factorization certainly breaks RSA cryptosystem security; the reverse implication for general RSA inversion problem algorithms is not known.

Thus the stated observation alone provides no serious general attack on well-generated parameters. It also does not prove a lower bound: special moduli or messages with short cycles can be weak, and the hardness claims are computational assumptions.