I have to encrypt 64-bit messages and then send them as a 64-bit message as well. I can't afford to send more than one 64-bit encrypted message for one 64-bit unencrypted message.
If that is the case, then the security that you can achieve is rather limited; you'll have to accept those limits, or find a way to allow some ciphertext expansion.
One thing that the attacker can do is generate a completely random ciphertext 64 bit ciphertext and submit that. If the encryption process accepts arbitrary 64 bit plaintexts and generates 64 bit ciphertexts, then every ciphertext will correspond to some plaintext, and in particular, the random ciphertext will correspond to some random plaintext. The best you can do in this scenario is to make sure that the attacker has no better attack; that is, he can cause you to decrypt into unpredictable values, but he cannot do any better.
What you'll need to do is have the recipient vet the decrypted plaintext somehow (e.g. if there is a 'type' field that is from 0-5, reject any message where the type field is outside that range). No security person would be overjoyed at the security you can achieve with this; however that's the best you can do.
As for how to make random plaintext/ciphertext mappings, well, it turns out that for 64 bits, there just happens to be some standard block ciphers that can do that ; 3DES naturally has a 64 bit block size, as well as some Speck parameter sets. 3DES is still fairly commonly implemented in crypto libraries (generally deprecated, but still there), and Speck is quite simple. What you would do is use the block cipher in ECB mode ; take your 64 bit plaintext, and give it to the block cipher in encrypt mode; that'll give you a 64 bit ciphertext. The recipient will take the 64 bit ciphertext, and give it to the block cipher in decrypt mode; that'll give you a 64 bit plaintext (which you'll vet). The block cipher acts like a random permutation; that is, the attacker will not be able to predict what any ciphertext he has not seen to decrypt to.
This does bring up the question of replay attacks. Those are even more challenging in this scenario, and I'm rather hoping those are not a concern (especially if message transmission is not guaranteed; that is, it Is possible for the recipient to not receive every message the encryptor has sent).
: For someone reading this later with a similar problem, but with slightly different ciphertext sizes, there are some other standard solutions, known as Format Preserving Encryption methods, which can take arbitrary plaintext sizes (e.g. 42 bits), and map then into the exact same ciphertext size. However, there are rather more obscure, and so I do not suggest them for Nicolas.
: Using ECB mode is generally the Wrong Thing; this is one of the few cases where it makes sense