diff options
| -rw-r--r-- | analysis/countermeasures/simulation.ipynb | 297 |
1 files changed, 171 insertions, 126 deletions
diff --git a/analysis/countermeasures/simulation.ipynb b/analysis/countermeasures/simulation.ipynb index 5d3affc..10549c0 100644 --- a/analysis/countermeasures/simulation.ipynb +++ b/analysis/countermeasures/simulation.ipynb @@ -17,8 +17,8 @@ }, { "cell_type": "code", - "execution_count": 97, - "id": "33ee6084-2ac3-4f95-9610-0fbc06026538", + "execution_count": 8, + "id": "df261585-28d8-4df6-8b76-0d4bf1930608", "metadata": {}, "outputs": [], "source": [ @@ -50,7 +50,7 @@ }, { "cell_type": "markdown", - "id": "73e5efc6-b5ea-474f-9c71-8b54561d4ec1", + "id": "4b408b91-04dd-40a4-b4f2-1777111f1c80", "metadata": {}, "source": [ "Let's first initialize some useful objects. We will be working with projective coordinates and the `add-2007-bl` and `dbl-2007-bl` formulas, though any formulas would work. However, one obtains different results if working with complete formulas." @@ -58,8 +58,8 @@ }, { "cell_type": "code", - "execution_count": 3, - "id": "b1b9596c-1eba-4ace-af84-8cb279d84cc2", + "execution_count": 9, + "id": "b0afb195-8390-44c5-931e-75a70ccd4e9e", "metadata": {}, "outputs": [], "source": [ @@ -69,8 +69,8 @@ }, { "cell_type": "code", - "execution_count": 4, - "id": "b0afb195-8390-44c5-931e-75a70ccd4e9e", + "execution_count": 10, + "id": "7e762e13-95dd-4b57-9f49-57dc0cb115ec", "metadata": {}, "outputs": [], "source": [ @@ -83,12 +83,13 @@ }, { "cell_type": "code", - "execution_count": 5, - "id": "52c877e1-5021-4ec2-9daa-dd20bec6bcb2", + "execution_count": 11, + "id": "1c6f853d-df28-49f8-9ae3-3cf9e21fc219", "metadata": {}, "outputs": [], "source": [ "gsr = GroupScalarRandomization(mult)\n", + "gsr160 = GroupScalarRandomization(mult, 160)\n", "asplit = AdditiveSplitting(mult)\n", "msplit = MultiplicativeSplitting(mult)\n", "esplit = EuclideanSplitting(mult)\n", @@ -2753,37 +2754,56 @@ ] }, { + "cell_type": "markdown", + "id": "f71c790d-83eb-4bb3-801a-a784c6f4b433", + "metadata": {}, + "source": [ + "The EPA test introduces the neutral (infinity) point to the scalar multiplication and observes whether the computation outputs an error (and how often). During a scalar multiplication $kP$, several multiples of the input point are gradually computed $k_1P,k_2P,\\dots,k_rP=kP$. If any of the scalars $k_i$ is a multiple of the order of $P$, then the neutral point $k_iP=\\infty$ appears and is used for futher computations which might lead to an error. The probability that this happens is mainly given by the size of the scalar $k$ and the order of the point $P$. The simulation below uses a point of order 373." + ] + }, + { + "cell_type": "markdown", + "id": "47defb90-6780-4dba-a732-fa7660cd1fdb", + "metadata": {}, + "source": [ + "We can present the implementation the full order $373n$ (`params373full`) or we can hide the divisor and claim only $n$ (`params373hidden`)." + ] + }, + { "cell_type": "code", - "execution_count": 71, + "execution_count": 74, "id": "6c60a21d-5df6-493a-82f5-6d8c43398caa", "metadata": {}, "outputs": [], "source": [ - "params373 = load_params_ectester(io.BytesIO(b\"0xeaabdf71acab107ab3ca581802a436a8b3a16b0ab2835994240b57d76d4ced13,0x6c66649a7c6a6c5f5c93d3bf27409b2b84cfcd2365fc902f061c2306046a7d2b,0x01d4b68f60ee4794fb2a364c6ab66ecefa0801fd8bd2266a29f7e756d3b9ec0a,0xaef417d0cbb8c113f92a9430e675c127690fab2bd3dc723b468e0309ca7de069,0x92b8fed2813c5820ef5ebfc9b1c26ccff580814d75bea54eab1426913f445dc4,0xa10fb2bff2bb695645dc8c133967c82d8a23c2ca1710a880c8d6b7dbd77565,0x1\"), \"projective\")\n", - "params373cofactor = load_params_ectester(io.BytesIO(b\"0xeaabdf71acab107ab3ca581802a436a8b3a16b0ab2835994240b57d76d4ced13,0x6c66649a7c6a6c5f5c93d3bf27409b2b84cfcd2365fc902f061c2306046a7d2b,0x01d4b68f60ee4794fb2a364c6ab66ecefa0801fd8bd2266a29f7e756d3b9ec0a,0xaef417d0cbb8c113f92a9430e675c127690fab2bd3dc723b468e0309ca7de069,0x92b8fed2813c5820ef5ebfc9b1c26ccff580814d75bea54eab1426913f445dc4,0xa10fb2bff2bb695645dc8c133967c82d8a23c2ca1710a880c8d6b7dbd77565,0x175\"), \"projective\")\n", + "params373hidden = load_params_ectester(io.BytesIO(b\"0xeaabdf71acab107ab3ca581802a436a8b3a16b0ab2835994240b57d76d4ced13,0x6c66649a7c6a6c5f5c93d3bf27409b2b84cfcd2365fc902f061c2306046a7d2b,0x01d4b68f60ee4794fb2a364c6ab66ecefa0801fd8bd2266a29f7e756d3b9ec0a,0xaef417d0cbb8c113f92a9430e675c127690fab2bd3dc723b468e0309ca7de069,0x92b8fed2813c5820ef5ebfc9b1c26ccff580814d75bea54eab1426913f445dc4,0xa10fb2bff2bb695645dc8c133967c82d8a23c2ca1710a880c8d6b7dbd77565,0x1\"), \"projective\")\n", "params373full = load_params_ectester(io.BytesIO(b\"0xeaabdf71acab107ab3ca581802a436a8b3a16b0ab2835994240b57d76d4ced13,0x6c66649a7c6a6c5f5c93d3bf27409b2b84cfcd2365fc902f061c2306046a7d2b,0x01d4b68f60ee4794fb2a364c6ab66ecefa0801fd8bd2266a29f7e756d3b9ec0a,0xb6d416d083c38c7d1345e050a880ab34dd62d2d1f54412296d2e434bf68df5e5,0xb3bd58bb4460da59cd6915160158062efd150bd7914d27631e70f03e0ec71a21,0xeaabdf71acab107ab3ca581802a436aa5a461ad0739b4583a4a0d9e350ee0c29,0x1\"), \"projective\")\n", "point373 = Point(X=mod(0x9b594237f596a9735053560e16df025b16eb566eacfb28ce24594782bc3e437f, params373.curve.prime),\n", " Y=mod(0xd8e171dcd78b13eaa05e6a12e66859c0ea37e133ac299544faa9f940c96f33c3, params373.curve.prime),\n", " Z=mod(1, params373.curve.prime), model=coords)\n", - "key373 = 0x84586844db93f75d3f12326d9f7e8d519723eb13d5e959cec9092bc9e29883e1" + "key = 0x5e22f7335e91e9ce65fe506178f34125f9f748ce6711888037c965f42a9a37\n", + "key_error = 0x7d767257fdc6eba6c1f7ba0812c8c7a7ae77934bd19d36c54b4faf31622bc9" ] }, { "cell_type": "code", - "execution_count": 74, + "execution_count": 75, "id": "cffb4735-4191-46ed-aab5-8f66688b1208", "metadata": {}, "outputs": [], "source": [ - "def test_epa(countermeasure, tries, params=params373):\n", + "def test_epa(countermeasure, tries, params=params373full, key=key):\n", " outputs = set()\n", " errors = 0\n", " correct = 0\n", - " expected = params.curve.affine_multiply(point373.to_affine(), key373)\n", + " try:\n", + " expected = params.curve.affine_multiply(point373.to_affine(), key)\n", + " except Exception:\n", + " expected = params.curve.neutral\n", " for _ in range(tries):\n", - " countermeasure.init(params, point337)\n", + " countermeasure.init(params, point373)\n", " try:\n", - " res = countermeasure.multiply(key373)\n", + " res = countermeasure.multiply(key)\n", " aff = res.to_affine()\n", " outputs.add(aff)\n", " if aff == expected:\n", @@ -2804,71 +2824,69 @@ ] }, { - "cell_type": "code", - "execution_count": 75, - "id": "5da3b57b-e5b4-4e72-8ad3-9c704c357e1d", - "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "1 unique outputs, 100 correct, 0 errors\n", - "{Point([x=59642274662531431971038646210249691462441292380475222936346030859219614397850, y=77708603406505118079923801589161040828883593753086992229575020097072579628359] in shortw/affine)}\n" - ] - } - ], - "source": [ - "test_epa(mult, 100)" - ] - }, - { "cell_type": "markdown", - "id": "ed65740d-29c7-4709-a52d-8c25000d8746", + "id": "9ec5ceaa-794b-4a40-ae1f-47843be196a8", "metadata": {}, "source": [ - "### Group scalar randomization" + "When no countermeasures are applied, the scalar multiplication is deterministic. We either always get an error or never, depending on the scalar." ] }, { "cell_type": "code", "execution_count": 76, - "id": "471f241d-bee0-4eab-8c38-6e3a94d0c8f2", + "id": "9b230a59-a6c5-4984-b18d-58ae950ee5a4", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "63 unique outputs, 1 correct, 31 errors\n" + "0 unique outputs, 0 correct, 100 errors\n" ] } ], "source": [ - "test_epa(gsr, 100)" + "test_epa(mult, 100, key=key_error)" ] }, { "cell_type": "code", "execution_count": 77, - "id": "6d9d7853-d319-450c-b6c0-4724591960ff", + "id": "5da3b57b-e5b4-4e72-8ad3-9c704c357e1d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "64 unique outputs, 0 correct, 30 errors\n" + "1 unique outputs, 100 correct, 0 errors\n", + "{Point([x=50582717080162824157923262995758700615600207445800422082261146290031270523338, y=59054557706692485786050046234492855554939576857752133711491107905567203734259] in shortw/affine)}\n" ] } ], "source": [ - "test_epa(gsr, 100, params373cofactor)" + "test_epa(mult, 100, key=key)" + ] + }, + { + "cell_type": "markdown", + "id": "ed65740d-29c7-4709-a52d-8c25000d8746", + "metadata": {}, + "source": [ + "### Group scalar randomization" + ] + }, + { + "cell_type": "markdown", + "id": "4a679785-8604-4001-a53f-1ee5b5c1cb9f", + "metadata": {}, + "source": [ + "With GSR, the sequence of scalars $k_i$ is no longer deterministic. The scalar multiplication sometimes outputs an error." ] }, { "cell_type": "code", - "execution_count": 78, + "execution_count": 66, "id": "e9442e73-aa8f-463d-87b9-b6875ab68f1c", "metadata": {}, "outputs": [ @@ -2876,8 +2894,8 @@ "name": "stdout", "output_type": "stream", "text": [ - "1 unique outputs, 76 correct, 24 errors\n", - "{Point([x=59642274662531431971038646210249691462441292380475222936346030859219614397850, y=77708603406505118079923801589161040828883593753086992229575020097072579628359] in shortw/affine)}\n" + "1 unique outputs, 74 correct, 26 errors\n", + "{Point([x=50582717080162824157923262995758700615600207445800422082261146290031270523338, y=59054557706692485786050046234492855554939576857752133711491107905567203734259] in shortw/affine)}\n" ] } ], @@ -2887,114 +2905,129 @@ }, { "cell_type": "markdown", - "id": "53c4fccc-2216-402d-908c-74b8811b43ca", + "id": "a802b5d2-8eb8-4370-a810-b326bdd6ee70", "metadata": {}, "source": [ - "### Multiplicative splitting" + "The size of the randomized scalar $k+rn$ is approximately $\\log(nr)$. If we increase the size of the mask $r$ (from 32 to 160), the number of the scalars $k_i$ increases and the number of errors is then higher too." ] }, { "cell_type": "code", - "execution_count": 79, - "id": "7e0a2599-5e4e-4c4b-a99d-da8c0f3dc7d8", + "execution_count": 71, + "id": "471f241d-bee0-4eab-8c38-6e3a94d0c8f2", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "62 unique outputs, 0 correct, 33 errors\n" + "1 unique outputs, 52 correct, 48 errors\n", + "{Point([x=50582717080162824157923262995758700615600207445800422082261146290031270523338, y=59054557706692485786050046234492855554939576857752133711491107905567203734259] in shortw/affine)}\n" ] } ], "source": [ - "test_epa(msplit, 100)" + "test_epa(gsr160, 100, params373full)" ] }, { - "cell_type": "code", - "execution_count": 83, - "id": "660a800a-a4ba-407c-9b9c-3054195b0847", + "cell_type": "markdown", + "id": "69c7cc4c-9149-4b50-87ca-f9ca760d8c67", "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "67 unique outputs, 0 correct, 25 errors\n" - ] - } - ], "source": [ - "test_epa(msplit, 100, params373cofactor)" + "If the order used for the randomization is not a multiple of the input point, we also see incorrect results." ] }, { "cell_type": "code", - "execution_count": 84, - "id": "aaf16a9e-fd9a-475f-af8b-1c8dfcb86380", + "execution_count": 68, + "id": "3c95a1f8-27f3-48f5-a758-8faa77527b81", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "1 unique outputs, 68 correct, 32 errors\n", - "{Point([x=59642274662531431971038646210249691462441292380475222936346030859219614397850, y=77708603406505118079923801589161040828883593753086992229575020097072579628359] in shortw/affine)}\n" + "61 unique outputs, 1 correct, 35 errors\n" ] } ], "source": [ - "test_epa(msplit, 100, params373full)" + "test_epa(gsr, 100, params373hidden)" ] }, { "cell_type": "markdown", - "id": "bb4c2c8e-a3ca-4a51-90e3-7326736b9bdb", + "id": "53c4fccc-2216-402d-908c-74b8811b43ca", "metadata": {}, "source": [ - "### Additive splitting" + "### Multiplicative splitting" + ] + }, + { + "cell_type": "markdown", + "id": "d1e47679-3933-4dec-8847-3d273f4bb4c9", + "metadata": {}, + "source": [ + "Multiplicative splitting computes two scalar multiplications with scalars of sizes $\\log(r)$ and $\\log(n)$. The sum of these is the same as in GSR and so the probability of an error is roughly the same." ] }, { "cell_type": "code", - "execution_count": 82, - "id": "261d88ba-757a-4f6c-82c7-332eda3165b8", + "execution_count": 72, + "id": "aaf16a9e-fd9a-475f-af8b-1c8dfcb86380", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "2 unique outputs, 0 correct, 48 errors\n" + "1 unique outputs, 63 correct, 37 errors\n", + "{Point([x=50582717080162824157923262995758700615600207445800422082261146290031270523338, y=59054557706692485786050046234492855554939576857752133711491107905567203734259] in shortw/affine)}\n" ] } ], "source": [ - "test_epa(asplit, 100)" + "test_epa(msplit, 100, params373full)" ] }, { "cell_type": "code", - "execution_count": 85, - "id": "7adc9dec-75be-46d8-ada4-7e64b11b7a0b", + "execution_count": 73, + "id": "7e0a2599-5e4e-4c4b-a99d-da8c0f3dc7d8", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "2 unique outputs, 0 correct, 39 errors\n" + "62 unique outputs, 1 correct, 32 errors\n" ] } ], "source": [ - "test_epa(asplit, 100, params373cofactor)" + "test_epa(msplit, 100, params373hidden)" + ] + }, + { + "cell_type": "markdown", + "id": "bb4c2c8e-a3ca-4a51-90e3-7326736b9bdb", + "metadata": {}, + "source": [ + "### Additive splitting" + ] + }, + { + "cell_type": "markdown", + "id": "c055e8f1-81f3-436c-bbb4-8bc851aad85f", + "metadata": {}, + "source": [ + "Since the additive splitting performs two scalar multiplications with scalars of size $\\log(n)$, the probability of an error increases when compared to GSR or multiplicative splitting." ] }, { "cell_type": "code", - "execution_count": 86, + "execution_count": 44, "id": "758053ff-61fc-4139-8434-0e1e1d7beb24", "metadata": {}, "outputs": [ @@ -3002,8 +3035,8 @@ "name": "stdout", "output_type": "stream", "text": [ - "1 unique outputs, 44 correct, 56 errors\n", - "{Point([x=59642274662531431971038646210249691462441292380475222936346030859219614397850, y=77708603406505118079923801589161040828883593753086992229575020097072579628359] in shortw/affine)}\n" + "1 unique outputs, 47 correct, 53 errors\n", + "{Point([x=50582717080162824157923262995758700615600207445800422082261146290031270523338, y=59054557706692485786050046234492855554939576857752133711491107905567203734259] in shortw/affine)}\n" ] } ], @@ -3013,67 +3046,82 @@ }, { "cell_type": "markdown", - "id": "ca71364a-d1ef-493e-908e-208755310e01", + "id": "f2d595c2-fbb0-49ce-8688-fbc17880e7d1", "metadata": {}, "source": [ - "### Euclidean splitting" + "The additive splitting might reduce one of the scalars $k-r$ modulo $n$. If the order $n$ is not correct, it produces incorrect results." ] }, { "cell_type": "code", - "execution_count": 81, - "id": "c953d295-5ce6-4078-87eb-e9f3d22ffb14", + "execution_count": 63, + "id": "261d88ba-757a-4f6c-82c7-332eda3165b8", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "1 unique outputs, 71 correct, 29 errors\n", - "{Point([x=59642274662531431971038646210249691462441292380475222936346030859219614397850, y=77708603406505118079923801589161040828883593753086992229575020097072579628359] in shortw/affine)}\n" + "2 unique outputs, 34 correct, 46 errors\n" ] } ], "source": [ - "test_epa(esplit, 100)" + "test_epa(asplit, 100, params373hidden)" + ] + }, + { + "cell_type": "markdown", + "id": "ca71364a-d1ef-493e-908e-208755310e01", + "metadata": {}, + "source": [ + "### Euclidean splitting" + ] + }, + { + "cell_type": "markdown", + "id": "0a88116b-755b-4333-909a-cdf51e6bc7ff", + "metadata": {}, + "source": [ + "Euclidean splitting computes three scalar multiplication, but with scalars of half the size than the original scalar $k$. The number of errors is slightly higher than GSR or multiplicative splitting." ] }, { "cell_type": "code", - "execution_count": 87, - "id": "7e3400ee-5962-4ece-a718-e0a428d66640", + "execution_count": 48, + "id": "2def5387-427f-4697-a553-8345531e4858", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "1 unique outputs, 68 correct, 32 errors\n", - "{Point([x=59642274662531431971038646210249691462441292380475222936346030859219614397850, y=77708603406505118079923801589161040828883593753086992229575020097072579628359] in shortw/affine)}\n" + "1 unique outputs, 58 correct, 42 errors\n", + "{Point([x=50582717080162824157923262995758700615600207445800422082261146290031270523338, y=59054557706692485786050046234492855554939576857752133711491107905567203734259] in shortw/affine)}\n" ] } ], "source": [ - "test_epa(esplit, 100, params373cofactor)" + "test_epa(esplit, 100, params373full)" ] }, { "cell_type": "code", - "execution_count": 88, - "id": "2def5387-427f-4697-a553-8345531e4858", + "execution_count": 64, + "id": "c953d295-5ce6-4078-87eb-e9f3d22ffb14", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "1 unique outputs, 61 correct, 39 errors\n", - "{Point([x=59642274662531431971038646210249691462441292380475222936346030859219614397850, y=77708603406505118079923801589161040828883593753086992229575020097072579628359] in shortw/affine)}\n" + "1 unique outputs, 58 correct, 42 errors\n", + "{Point([x=50582717080162824157923262995758700615600207445800422082261146290031270523338, y=59054557706692485786050046234492855554939576857752133711491107905567203734259] in shortw/affine)}\n" ] } ], "source": [ - "test_epa(esplit, 100, params373full)" + "test_epa(esplit, 100, params373hidden)" ] }, { @@ -3085,9 +3133,17 @@ ] }, { + "cell_type": "markdown", + "id": "006600fa-74dc-4b95-b3f1-4ada49835980", + "metadata": {}, + "source": [ + "This countermeasure is not a scalar randomization and so the errors are deterministic." + ] + }, + { "cell_type": "code", - "execution_count": 89, - "id": "48aa14c5-d55e-4271-aff6-e9990850c0db", + "execution_count": 53, + "id": "f7060ac2-06b0-4b50-a2e3-287468ad0ad7", "metadata": {}, "outputs": [ { @@ -3099,51 +3155,40 @@ } ], "source": [ - "test_epa(bt, 100)" + "test_epa(bt, 100, params373full)" ] }, { - "cell_type": "code", - "execution_count": 90, - "id": "bb5802fd-2dcc-4adb-9140-0da557ae7614", + "cell_type": "markdown", + "id": "7676196e-6283-4176-aca5-46fc1ba0a410", "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "1 unique outputs, 100 correct, 0 errors\n", - "{Point([x=59642274662531431971038646210249691462441292380475222936346030859219614397850, y=77708603406505118079923801589161040828883593753086992229575020097072579628359] in shortw/affine)}\n" - ] - } - ], "source": [ - "test_epa(bt, 100, params373cofactor)" + "Incorrect order produces incorrect results." ] }, { "cell_type": "code", - "execution_count": 91, - "id": "f7060ac2-06b0-4b50-a2e3-287468ad0ad7", + "execution_count": 65, + "id": "48aa14c5-d55e-4271-aff6-e9990850c0db", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "1 unique outputs, 100 correct, 0 errors\n", - "{Point([x=59642274662531431971038646210249691462441292380475222936346030859219614397850, y=77708603406505118079923801589161040828883593753086992229575020097072579628359] in shortw/affine)}\n" + "1 unique outputs, 0 correct, 0 errors\n", + "{Point([x=24769856295107603556435636887559104285220764156777537502567506606504075004201, y=40255301248838694734815795560593391161833271862220457358477700991143317762809] in shortw/affine)}\n" ] } ], "source": [ - "test_epa(bt, 100, params373full)" + "test_epa(bt, 100, params373hidden)" ] }, { "cell_type": "code", "execution_count": null, - "id": "0868e4d0-5a07-42cb-bc17-d1080ace15aa", + "id": "46979534-30e4-4897-a424-72f338611d9b", "metadata": {}, "outputs": [], "source": [] @@ -3165,7 +3210,7 @@ "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", - "version": "3.12.3" + "version": "3.10.12" } }, "nbformat": 4, |