Michrochipが採用している暗号ロジック。ひょんなことから、ちくと調べたりしたので記録を残す。GHDLで動かすところまで。進化したやつじゃなくレガシーなやつ。
参考ページ
仕様が超簡単。で、C言語よりもVHDLのほうが実装しやすいのでやってみる。
暗号化のブロック図(Wikipediaより)。
32bitの入力(上のブロック)を64bitの鍵を使いながら528回こねくり回して暗号化する。
VHDLで実装するにあたっては、クロックごとにシフトを実行し、NLFやらXORやらは組み合わせ回路として実装する。
復号化のブロック。
こちらも同じ方法でできそう。
で、さっそく。暗号化から。
keeloq_enc.vhd
library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
entity keeloq_enc is
port (
i_pr : in std_logic_vector(31 downto 0);
i_kr : in std_logic_vector(63 downto 0);
o_busy : out std_logic;
o_cr : out std_logic_vector(31 downto 0);
i_start : in std_logic;
i_clk : in std_logic
);
end keeloq_enc;
architecture ppl_type of keeloq_enc is
signal i_start_prev : std_logic:='0';
signal i_start_pres : std_logic:='0';
signal i_start_rising : std_logic:='0';
signal indicator_busy : std_logic:='0';
type t_state is (STATE_IDLE,STATE_RUN);
signal state : t_state := STATE_IDLE;
signal pr : std_logic_vector(31 downto 0):=X"00000000";
signal kr : std_logic_vector(63 downto 0):=X"0000000000000000";
signal nlf_arg : std_logic_vector(4 downto 0):="00000";
signal nlf : std_logic:='0';
constant nlf_table : std_logic_vector(31 downto 0):=X"3a5c742e";
signal newz : std_logic:='0';
signal cnt : integer range 0 to 1023:=0;
constant cnt_max : integer range 0 to 1023:=528;
begin
i_start_pres<=i_start;
i_start_rising<='1' when (i_start_prev='0' and i_start_pres='1') else '0';
o_busy<=indicator_busy;
o_cr<=pr when indicator_busy='0' else X"00000000";
nlf_arg<=pr(31)&pr(26)&pr(20)&pr(9)&pr(1);
nlf<=nlf_table(CONV_INTEGER(nlf_arg));
newz<=(nlf xor (pr(16) xor pr(0)) xor kr(0));
process (i_clk,i_start_rising,state) begin
if i_clk'event and i_clk='1' then
i_start_prev<=i_start;
if i_start_rising='1' and state=STATE_IDLE then
pr<=i_pr;
kr<=i_kr;
indicator_busy<='1';
state<=STATE_RUN;
cnt<=0;
end if;
if state=STATE_RUN then
if cnt<cnt_max then
pr<=newz&pr(31 downto 1);
kr<=kr(0)&kr(63 downto 1);
cnt<=cnt+1;
else
indicator_busy<='0';
state<=STATE_IDLE;
end if;
end if;
end if;
end process;
end;
keeloq_enc_tb.vhd
library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
entity keeloq_enc_tb is
end keeloq_enc_tb;
architecture sim of keeloq_enc_tb is
component keeloq_enc is port (
i_pr : in std_logic_vector(31 downto 0);
i_kr : in std_logic_vector(63 downto 0);
o_busy : out std_logic;
o_cr : out std_logic_vector(31 downto 0);
i_start : in std_logic;
i_clk : in std_logic
); end component;
signal clksys : std_logic:='0';
constant STEPSYS : TIME := 6.25 ns;
signal i_pr_tb : std_logic_vector(31 downto 0):=X"f741e2db";
signal i_kr_tb : std_logic_vector(63 downto 0):=X"5cec6701b79fd949";
signal o_busy_tb : std_logic;
signal o_cr_tb : std_logic_vector(31 downto 0);
signal i_start_tb : std_logic:='0';
signal countup_to_start : integer range 0 to 255:=0;
begin
keeloq_enc_inst : component keeloq_enc port map(
i_pr=>i_pr_tb,
i_kr=>i_kr_tb,
o_busy=>o_busy_tb,
o_cr=>o_cr_tb,
i_start=>i_start_tb,
i_clk=>clksys
);
clksys <= not(clksys) after STEPSYS/2;
process(clksys)begin
if clksys'event and clksys='1' then
if countup_to_start<30 then
i_start_tb<='0';
countup_to_start<=countup_to_start+1;
elsif countup_to_start=30 then
i_start_tb<='1';
countup_to_start<=countup_to_start+1;
else
i_start_tb<='0';
end if;
end if;
end process;
process begin
wait for 5 us;
assert (false) report "Simulation End!" severity failure;
end process;
end;
Makefile
VHDLC=/usr/bin/ghdl
SRC=keeloq_enc.vhd
TBSRC=keeloq_enc_tb.vhd
VCD=keeloq_enc.vcd
SIMRTL=keeloq_enc_tb
all :
@make comp
@make tb
@make tb_e
@make vcd
comp :
$(VHDLC) -a --ieee=synopsys -fexplicit $(SRC)
tb :
$(VHDLC) -a --ieee=synopsys -fexplicit $(TBSRC)
tb_e :
$(VHDLC) -e --ieee=synopsys -fexplicit $(SIMRTL)
vcd :
$(VHDLC) -r --ieee=synopsys -fexplicit $(SIMRTL) --vcd=$(VCD)
Hosein Hadipourさんのテストベクタの上のほうのやつと同じテストベクタにして、同じ結果になっています。
では、復号化。
keeloq_dec.vhd
library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
entity keeloq_dec is
port (
i_cr : in std_logic_vector(31 downto 0);
i_kr : in std_logic_vector(63 downto 0);
o_busy : out std_logic;
o_pr : out std_logic_vector(31 downto 0);
i_start : in std_logic;
i_clk : in std_logic
);
end keeloq_dec;
architecture ppl_type of keeloq_dec is
signal i_start_prev : std_logic:='0';
signal i_start_pres : std_logic:='0';
signal i_start_rising : std_logic:='0';
signal indicator_busy : std_logic:='0';
type t_state is (STATE_IDLE,STATE_RUN);
signal state : t_state := STATE_IDLE;
signal cr : std_logic_vector(31 downto 0):=X"00000000";
signal kr : std_logic_vector(63 downto 0):=X"0000000000000000";
signal nlf_arg : std_logic_vector(4 downto 0):="00000";
signal nlf : std_logic:='0';
constant nlf_table : std_logic_vector(31 downto 0):=X"3a5c742e";
signal newz : std_logic:='0';
signal cnt : integer range 0 to 1023:=0;
constant cnt_max : integer range 0 to 1023:=528;
begin
i_start_pres<=i_start;
i_start_rising<='1' when (i_start_prev='0' and i_start_pres='1') else '0';
o_busy<=indicator_busy;
o_pr<=cr when indicator_busy='0' else X"00000000";
nlf_arg<=cr(30)&cr(25)&cr(19)&cr(8)&cr(0);
nlf<=nlf_table(CONV_INTEGER(nlf_arg));
newz<=((nlf xor cr(31) xor kr(15)) xor cr(15));
process (i_clk,i_start_rising,state) begin
if i_clk'event and i_clk='1' then
i_start_prev<=i_start;
if i_start_rising='1' and state=STATE_IDLE then
cr<=i_cr;
kr<=i_kr;
indicator_busy<='1';
state<=STATE_RUN;
cnt<=0;
end if;
if state=STATE_RUN then
if cnt<cnt_max then
cr<=cr(30 downto 0)&newz;
kr<=kr(62 downto 0)&kr(63);
cnt<=cnt+1;
else
indicator_busy<='0';
state<=STATE_IDLE;
end if;
end if;
end if;
end process;
end;
keeloq_dec_tb.vhd
library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
entity keeloq_dec_tb is
end keeloq_dec_tb;
architecture sim of keeloq_dec_tb is
component keeloq_dec is port (
i_cr : in std_logic_vector(31 downto 0);
i_kr : in std_logic_vector(63 downto 0);
o_busy : out std_logic;
o_pr : out std_logic_vector(31 downto 0);
i_start : in std_logic;
i_clk : in std_logic
); end component;
signal clksys : std_logic:='0';
constant STEPSYS : TIME := 6.25 ns;
signal i_cr_tb : std_logic_vector(31 downto 0):=X"e44f4cdf";
signal i_kr_tb : std_logic_vector(63 downto 0):=X"5cec6701b79fd949";
signal o_busy_tb : std_logic;
signal o_pr_tb : std_logic_vector(31 downto 0);
signal i_start_tb : std_logic:='0';
signal countup_to_start : integer range 0 to 255:=0;
begin
keeloq_dec_inst : component keeloq_dec port map(
i_cr=>i_cr_tb,
i_kr=>i_kr_tb,
o_busy=>o_busy_tb,
o_pr=>o_pr_tb,
i_start=>i_start_tb,
i_clk=>clksys
);
clksys <= not(clksys) after STEPSYS/2;
process(clksys)begin
if clksys'event and clksys='1' then
if countup_to_start<30 then
i_start_tb<='0';
countup_to_start<=countup_to_start+1;
elsif countup_to_start=30 then
i_start_tb<='1';
countup_to_start<=countup_to_start+1;
else
i_start_tb<='0';
end if;
end if;
end process;
process begin
wait for 5 us;
assert (false) report "Simulation End!" severity failure;
end process;
end;
Makefileは省略。
はい。ちゃんと元の値に復号できています。
で、このアルゴリズムですが、FPGAを160MHzで動かして3.4usかかるわけです。
暗号文と平文が１組わかっているとして総当たりで秘密鍵を割り出そうとします。そすと、
3.4e-6*(2^64)秒=200万年
かかります。まぁ総当たりでの攻撃は鍵の長さとラウンド数に依存するので、こんな簡単なアルゴリズムでも鍵を割り出すのは困難です。世の中にはいろんな方法を考える人がいて、このレガシーな暗号生成アルゴリズムはすでに、、、
ひさしぶりの更新。いやー完全にさぼりです。なんかやる気起きんのよねー。
コメントをお書きください