Instead of letting Crypt::CBC try and figure out a cipher on its own (where it's clearly picking 'Random' as the cipher you want to use in this case), you can specify one yourself...

my $cipher = Crypt::CBC->new( -key => $key, cipher => 'Rijndael' );
[download]

That will cause it to use Crypt::Rijndael for the cipher.