What attacks against crypto systems should i worry about?

I am currently researching a way to secure communication between devices for a company (as an internt) I've started with analyzing threats they could encounter, now i'm writing down the most used and dangerous attacks which could be preformed against an encrypted communication.

I already have a list of the following attacks:

Brute force, Man in the middle, replay, related key, Bit flipping, frequency analysis, Random number generator attack, side channel attacks such as timing, power monitor and electromagnetic

To clarify a bit more, this company makes devices which communicate with a server, these devices are placed where ever needed, so the environment isn't secure. We (the company and me) have decided we'd first make an overview of attacks which present a threat then we would find algorithms, mode operations and such to protect against this and implement it for the communication between the devices. I should note the attacks we defend against will also be based on cost analysis since adding secure SAM chips to protect against someone opening up the system and stealing the key is to costly if this needs to be done for thousands of modules.

It looks like AES-gcm is the way to go, i'm still trying to sell them on a PKI system but they are afraid the hardware can't handle those computations, they have very little ROM space left and it cannot use the entirety of the MCU since there is often software running which is in charge of life and death situations. Perhaps if I can demonstrate it can run full TLS without taking up to much resources we might go that way.

So back to my question, what other attacks should i be worried about? if you require additional information or think my approach is flawed please tell me through the comments.