Cuantos caracteres la clave te faltan?
Dependiendo de eso mi respuesta

Hmm, son muchos para hacer lo primero y mas facil que te iba a sugerir..
Sabes alguna palabra del mensaje de casualidad?
Porque una forma es tomar la llave, y el mensaje cifrado, y hacer fuerza bruta sobre los ultimos caracteres de la clave. Cuando conseguis una clave para utilizar, descifras el texto. Hasta que de algo con sentido.
Una vez por cada clave posible (es poco practico).
Claro esta, que si tenes idea de alguna de las palabras que hay en el mensaje, esto se puede automatizar.
De otra forma, ECB es Electronic Code Book es de las mas viejas, y haciendo analisis de patrones algunas propiedades se pueden encontrar del texto original sin saber la llave y a partir de ahi construirla.

Esta clase de desafios me encantan, si te gustaria contactarme privadamente te podria dar una mano.

 

Te cuento por aca para que quede registrado.
No use un ataque de bicicleta sino un ataque por fuerza bruta.
Puse los 3 i7 a trabajar junto a sus GPUs y la tuve en un ratito(en terminos de AES) la clave.
Lo que hice fue generar todas las claves alfanumericas de 5 caracteres desde !!!!! hasta ZZZZZ acotado y despues reemplazar las XXXXX en la clave que te dieron por ese contenido una a la vez.
Utilize crypto++, luego de desencriptarlo lo volvi a cifrar con la llave que me dio hasta que el cifrado nuevamente fuera igual al hex cifrado que te dieron..
Si coincide, esa es la clave.
Te dejo el ejercicio de implementarlo a vos mismo y si no te sale mas tarde te paso el codigo..
Tene en cuenta que las posibilidades totales son PR25:!128
Si necesitas calcular las permutaciones, fijate que entre mis posts hay uno que tiene el codigo en C++ para calcular las permutaciones con repeticion de un grupo dado.

Solo te faltaria leerte el manualcito de Crypto++ o usar alguna otra solucion similar que soporte AES en modo ECB con tama;o de bloque de 1 byte


EDIT: El host mas chiquito es este:
byakko@linuxblade ~ $ uname -ra
Linux linuxblade 4.2.0-gentoo #3 SMP PREEMPT Tue Sep 1 03:07:53 ART 2015 x86_64 Intel(R) Core(TM) i7-4702HQ CPU @ 2.20GHz GenuineIntel GNU/Linux